part a) Create 2 classes, DynamicStack and DynamicQueue, both of which will inhe
ID: 3559608 • Letter: P
Question
part a)
Create 2 classes, DynamicStack and DynamicQueue, both of which will inherit from class LinkedList that we created together in class. (It is posted here on blackboard)
Here is what you I want you to do:
In LinkedList:
1) add a variable of type int called count, which will keep track of how many nodes are in the list.
2) make both variables count and head protected scope
****For DynamicStack and DynamicQueue , the order is based on the order in which they were added. These lists should not be sorted based on any value.
Therefore, the insert and delete methods must be overridden.
In both DynamicStack and DynamicQueue :
1)Create one constructor that takes in a parameter of type int.
The constructor should create a node with that int, and have the head variable point to it.
2)Create a method to override the parent classes insert method
3) Create a method to override the parent classes delete method. **** Note: see bottom****
4) Remember to update the count variable in all 3 of these methods.
5) Create method clearAll in both classes. The method should look at the node at the top or front and print out to the console its int value, and then delete that node from the list, calling method delete. Continue printing and deleting until the structure (stack or queue) is empty. Use the count variable to determine when the structure is empty.
For class DynamicStack, the head variable should point to the node at the top of the stack.
For class DynamicQueue, the head variable should point to the node at the front of the queue. In addition, I recommend that you have a variable called "back" or "last" to point to the last node in the list.
****Note 1****
The delete method in class LinkedList took in an int as a parameter. In order for the children classes to override the parent classes' method, the method signature must match EXACTLY, including the parameter list. Therefore, the delete method of the children classes must take in an int value. The int taken as a parameter is NOT the value of the node to be deleted, since only one node could possibly be deleted in these structures (either the top or the front). Instead the int value is the number of nodes that should be deleted from the stack or queue. If the int passes as a parameter is greater than the number of nodes in the list, then the list should be completely emptied. Be careful to avoid null pointer exceptions.
****Note 2****
If all of the Nodes are removed from the list, then the head pointer will point to null. If you then try to insert a Node, you will cause a NullPointerException. Therefore, you must check if head is null before calling any methods on it.
part b)
Create 2 classes, StaticStack and StaticQueue, both of which will inherit from class GSSArray that you created in assignment 2.
For this part of the assignment, I am leaving it up to you to determine what variables you need for these classes. You also are to determine if you want to use the variables of the parent class or redefine them in this class.
Create a constructor that calls the parent class's constructor.
Methods insert and delete have to be overridden for the same reason as in part a. Just like in part a, The delete method should delete as many values as the paramter passed to it and the insert method should insert the parameter passed either at the front or on top (depending on if it is class StaticStack or StaticQueue)
Do not override method increaseSize.
Create a method clearAll() that will look at the location at the top or front and print out to the console its int value, and then delete that value from the list, calling method delete. Continue printing and deleting until the structure (stack or queue) is empty.
HINT:
for the queue, use a variable to keep track of which index is the front of the queue and another variable for the back of the queue. Otherwise, you will have to perform a lot of shifting.
part c)
Create an instance method called print() in each of your 4 classes. The method should print out to the console all of the int values, in order
I want you to create a main method in another class called Assignment4.
The main method should create an instance of each of your 4 new classes. Their starting size for the StaticQueue and StaticStack should be 4.
For each structure:
Insert the numbers: 18, 3, 7, 36, 9, 14
call method delete 2 times
Then call method clearAll()
Insert the number 1.
After each method call, call method print (how else could you know if the code is doing what it is suppossed to do)
Then call method clearAll from both the queue and the stack.
Explanation / Answer
LinkedList.java
public class LinkedList<E> {
protected int count;
protected Node<Integer> head, tail;
public LinkedList() {
head = tail = null;
}
protected static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
public void insert(int num){}
public void delete(int num){}
}
DynamicStack.java
public class DynamicStack extends LinkedList{
Node<Integer> node;
public DynamicStack(int num){
node = new Node<Integer>(num);
tail = head = node;
count = 1;
}
public void insert(int num){
Node<Integer> newNode;
if(head != null){
newNode = new Node<Integer>(num);
tail.next = newNode;
tail = newNode;
count++;
}
else
{
System.out.println("DynamicStack doesn't exists");
}
}
public void delete(int num){
int i = num;
if(num > count){
num = count;
}
while(i > 0){
delete();
i--;
}
}
public void delete(){
if(count == 1)
{
count = 0;
tail = head = null;
}
else{
node = tail;
tail = head;
for(int i = 0;i<count-2;i++){
tail = tail.next;
}
node = null;
count--;
}
}
public void clearAll(){
int i = count;
System.out.print(" ");
while(i > 0){
node = tail;
System.out.println(node.element);
delete();
i--;
}
}
public void print()
{
node = tail;
int j = count;
while(j > 0){
System.out.print(node.element+ " ");
Node<Integer> newnode = head;
for(int i = 0; i < j-2;i++){
newnode = newnode.next;
}
j--;
node = newnode;
}
}
}
DynamicQueue.java
public class DynamicQueue extends LinkedList{
Node<Integer> node;
public DynamicQueue(int num){
node = new Node<Integer>(num);
tail = head = node;
count = 1;
}
public void insert(int num){
Node<Integer> newNode;
if(tail != null){
newNode = new Node<Integer>(num);
tail.next = newNode;
tail = newNode;
count++;
}
else
{
System.out.println("DynamicStack doesn't exists");
}
}
public void delete(int num){
int i = num;
if(num > count){
num = count;
}
while(i > 0){
delete();
i--;
}
}
public void delete(){
if(count == 1)
{
count = 0;
tail = head = null;
}
else{
node = head;
head = head.next;
node = null;
count--;
}
}
public void clearAll(){
int i = count;
System.out.print(" ");
while(i > 0){
node = head;
System.out.println(node.element);
delete();
i--;
}
}
public void print()
{
node = head;
int j = count;
while(j > 0){
System.out.print(node.element+ " ");
node = node.next;
j--;
}
}
}
TestClass.java
public class TestClass {
public static void main(String[] args) {
//18, 3, 7, 36, 9, 14
DynamicStack ds = new DynamicStack(18);
System.out.print("[1] :");
ds.print();
ds.insert(3);
System.out.print("[2] :");
ds.print();
ds.insert(7);
System.out.print("[3] :");
ds.print();
ds.insert(36);
System.out.print("[4] :");
ds.print();
ds.insert(9);
System.out.print("[5] :");
ds.print();
ds.insert(14);
System.out.print("[6] :");
ds.print();
ds.delete(2);
System.out.print("[7] :");
ds.print();
ds.clearAll();
System.out.print("[8] :");
ds.print();
//dynamic queue
System.out.print(" Dynamic Queue");
DynamicQueue dq = new DynamicQueue(18);
System.out.print("[1] :");
dq.print();
dq.insert(3);
System.out.print("[2] :");
dq.print();
dq.insert(7);
System.out.print("[3] :");
dq.print();
dq.insert(36);
System.out.print("[4] :");
dq.print();
dq.insert(9);
System.out.print("[5] :");
dq.print();
dq.insert(14);
System.out.print("[6] :");
dq.print();
dq.delete(2);
System.out.print("[7] :");
dq.print();
dq.clearAll();
System.out.print("[8] :");
dq.print();
//Static Queue
System.out.print(" Static Queue");
StaticQueue sq = new StaticQueue(18);
System.out.print("[1] :");
sq.print();
sq.insert(3);
System.out.print("[2] :");
sq.print();
sq.insert(7);
System.out.print("[3] :");
sq.print();
sq.insert(36);
System.out.print("[4] :");
sq.print();
sq.insert(9);
System.out.print("[5] :");
sq.print();
sq.insert(14);
System.out.print("[6] :");
sq.print();
sq.delete(2);
System.out.print("[7] :");
sq.print();
sq.clearAll();
System.out.print("[8] :");
sq.print();
//Static Stack
System.out.print(" Static Stack");
StaticStack ss = new StaticStack(18);
System.out.print("[1] :");
ss.print();
ss.insert(3);
System.out.print("[2] :");
ss.print();
ss.insert(7);
System.out.print("[3] :");
ss.print();
ss.insert(36);
System.out.print("[4] :");
ss.print();
ss.insert(9);
System.out.print("[5] :");
ss.print();
ss.insert(14);
System.out.print("[6] :");
ss.print();
ss.delete(2);
System.out.print("[7] :");
ss.print();
ss.clearAll();
System.out.print("[8] :");
ss.print();
}
}
StaticQueue.java
public class StaticQueue extends GSSArray{
public StaticQueue(int num){
super();
arr[0] = num;
count = 1;
bottom = 0 ;
}
public void insert(int num){
if(count != 0 && count < 10){
arr[count] = num;
count++;
}
else{
System.out.print("Queue is empty or full");
}
}
public void delete(int num){
int i = num;
if(num > count){
i = count;
}
while(i > 0){
delete();
i--;
}
}
public void delete(){
count--;
arr[bottom] = -1;
bottom++;
}
public void clearAll(){
int i = count;
while(i > 0){
delete();
i--;
}
}
public void print(){
int i = bottom;
while(i < count){
System.out.print(arr[i]+ " ");
i++;
}
}
}
StaticStack.java
public class StaticStack extends GSSArray{
public StaticStack(int num){
super();
arr[0] = num;
count = 1;
bottom = 0;
}
public void insert(int num){
if(count != 0 && count < 10){
arr[count] = num;
count++;
}
else{
System.out.print("Stack is empty or full");
}
}
public void delete(int num){
int i = num;
if(num > count){
i = count;
}
while(i > 0){
delete();
i--;
}
}
public void delete(){
count--;
arr[count] = -1;
}
public void clearAll(){
int i = count;
while(i > 0){
delete();
i--;
}
}
public void print(){
int i = bottom;
while(i < count){
System.out.print(arr[i]+" ");
i++;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.