part a) Create 2 classes, DynamicStack and DynamicQueue, both of which will inhe
ID: 3559583 • 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. (posted here after the program)
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.
LinkedList class as reference for this program.
public class LinkedList {
private Node head;
public LinkedList(Node n){
head =n;
}
public LinkedList(int x){
head = new Node(x);
}
public void append(int x) {
Node current = head;
while (current.getNext()!=null){
current = current.getNext();
}
current.setNext(new Node(x));
}
public void insert(int x) {
if(head.getData()>x){ // case 1: insert before head
head = new Node(x, head);
} else {
Node current = head;
Node previous = head;
while (current!=null){
if (current.getData()>x){ // case 2: insert into the middle of the list
previous.setNext(new Node(x, current));
// Node temp = new Node(x, current);
// previous.setNext(temp);
break;
} else {
previous = current;
current = current.getNext();
} // else
} // end of while
if(current == null){ // case 3: insert after list
previous.setNext(new Node(x));
} // if
} // else
} // insert method
public boolean delete(int x){
if(x==head.getData()){
head = head.getNext();
return true;
}
Node current = head;
Node previous = head;
while (current!=null){
if (current.getData()==x){ // case 2: delete from the middle or from the end
previous.setNext(current.getNext());
return true;
} else if(current.getData()>x) {
return false;
} else {
previous = current;
current = current.getNext();
}
}// while
return false;
} // delete method
}
Explanation / Answer
please rate
Here is the answer for PART A. PART B is not implemented because GSSArray implementation is not given. If you want post that as a separate question.
class DynamicStack extends LinkedList{
public DynamicStack(int data){
super(new Node(data));
count = 1;
}
public void insert(int data){
Node n = new Node(data);
n.setNext(head);
head = n;
count ++;
}
public boolean delete(int data){
while(count>0){
head = head.getNext();
count --;
}
return true;
}
public void clearAll(){
Node current = head;
while(count>0){
head = current;
System.out.println(current.getData());
current = current.getNext();
}
}
}
class DynamicQueue extends LinkedList{
private Node last;
public DynamicQueue(int data){
super(new Node(data));
last = head;
count = 1;
}
public void insert(int data){
if(head==null){
last = head = new Node(data);
count = 1;
return;
}
last.setNext(new Node(data));
count ++;
}
public boolean delete(int data){
while(count>0){
head = head.getNext();
count --;
}
return true;
}
public void clearAll(){
Node current = head;
while(count>0){
head = current;
System.out.println(current.getData());
current = current.getNext();
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.