Need help with making a persistent stack and a Queue in Java. Given two interfaces and a doubly linked list, implement a Stack and a Queue. You must use the doubly link list class and utilize it as an object in your implementation of the stack and queue. You may edit the linked list and you may also modify it but you must include it as part of your implementation. For this you want to wrap your linked list and not inherit it. The linked list has a lot of operations which can easily break your Stack or Queue. Should be 6 files in total: stack, queue, DNode, linkedList, myStack Interface, and myQueue Interface

Implement a Stack:

push (E): Add an element to the start of the sequence

pop: Remove an element from the start of the sequence

Peek: Return the first element of the sequence without removing it

atIndex(x): Return the element at the given index (x) Or throw an exception if it is out of bound (if you can control the user input then do that instead)

Size: Return the size of the Stack

isEmpty: Boolean, returns true if the Stack is empty

Empty: Empty the Stack

Implement Queue:

Enqueue(E): Add an element to the end of the sequence

Dequeue: Remove an element from the start of the sequence

atIndex(x): Return the element at the given index (x) Or throw an exception if it is out of bound (if you can control the user input then do that instead)

Size: Return the size of the Queue

isEmpty: Boolean, returns true if the Queue is empty

Empty: Empty the Queue

Here is what is given:

//

//

public class DNode { private Object e; // place holder for the type of object the //collection is storing private DNode next; // reference to the next node in the sequence // of nodes making up the linked list. Remember // that even though Java passes Objects by value // an object consisting of reference will behave // the same as an object passed by reference unless // a deep copy was made. private DNode prev; public DNode (Object e) // Constructor for implementing a single node { this.e = e; // The value of the element to be assigned to // this particular instance of node this.next = null; // An empty reference since there is no node // to follow. this.prev = null; } public DNode (Object e, DNode next, DNode prev) // Constructor for implementing a // node that comes after another // node { this.e = e; // The value of the element to be assigned to // this particular instance of node this.next = next; // reference to the subsequent node to follow this.prev = prev; } public void changeNext (DNode next) // Changes the link to the next node { this.next = next; } public void changePrev (DNode prev) // Changes the link to the next node { this.prev = prev; } public DNode getNext() // Returns the node next in the sequence { return this.next; } public Object getValue() // Returns the value a node is holding { return this.e; } public Boolean hasNext() // Returns a boolean determining regarding // the status of subsequent nodes after // the current node { return !(this.next.getValue() == null || this.next == null); } public Boolean hasprev() // Returns a boolean determining regarding // the status of subsequent nodes after // the current node { return !(this.prev.getValue() == null || this.prev == null); } public void insertAfterNode( Object input) { this.changeNext(new DNode (input, this.getNext(), this)); } public void insertAfterNode (DNode input) { this.changeNext(input); input.changeNext(this.next); input.changePrev(this); } public void insertbeforeNode (DNode input) { this.changeNext(input); } public void insertBetweenNodes(DNode before, DNode after) { this.changeNext(after); this.changePrev(before); before.changeNext(this); after.changePrev(this); }

public DNode getPrev() { return this.prev; } }

//

//

public class DoublyLinkedList

{ private DNode head; private DNode tail; private int size; public DoublyLinkedList () // construct an empty list { this.tail = new DNode (null, null, null); this.head = new DNode (null, this.tail, null); this.tail.changePrev(this.head); this.size = 0; } public DoublyLinkedList (DNode next) // constructs a list // out of a single node { this.tail = new DNode (null, null, next); this.head = new DNode (null, next, null); next.changeNext(this.tail); next.changePrev(this.head); this.size = 1; } public DoublyLinkedList(Object [] objectArray) // construct a list out of // an array { this.tail = new DNode (null, null, this.head); this.head = new DNode (null, this.tail, null); DNode temp = this.head; for (Object e : objectArray) { //Anonomus function new DNode (e, temp.getNext(),temp).insertBetweenNodes(temp, temp.getNext()); temp = temp.getNext(); this.size += 1; } } public void addToFrontofList (Object toAdd) // Appends the begining // of the list { DNode temp = new DNode (toAdd, this.head.getNext(), this.head); this.head.getNext().changePrev(temp); this.head.changeNext(temp); this.size += 1;

} public void addToendofList (Object toAdd) // appends the end of the list // with a node { DNode temp = new DNode (toAdd, this.tail, this.tail.getPrev()); this.tail.getPrev().changeNext(temp); this.tail.changePrev(temp); this.size += 1; } public void insertAfterNode(DNode current, Object input)// Inserts a new // a new node after // current node { current.insertAfterNode(input); this.size += 1; } public int getSize() // returns the size of the list { return this.size; }

@Override public String toString() { String result = ""; for (DNode temp = this.head.getNext(); temp.hasNext(); temp = temp.getNext()) { result += temp.getValue(); result += " -> "; } result += "End of list"; return result; } }

//

//

public interface myStack { /** * push (E): Add an element to the start of the sequence * @param element an element that you are to push on to the stack */ public void push (E element); /** * pop: Remove an element from the start of the sequence * @return returns the element that has been popped */ public E pop (); /** * Peek: Return the first element of the sequence without removing it * @return the first element of the sequence */ public E peek(); /** * atIndex(x): Return the element at the given index (x) * Or throw an exception if it is out of bound * (if you can control the user input then do that instead) * @param x the index of the Element within the sequence * @return the Element being returned */ public E atIndex(int x); /** * Size: Return the size of the Stack * @return the size of the object */ public int size(); /** * isEmpty: Boolean, returns true if the Stack is empty * @return a boolean which states if the collection is * empty or populated */ public boolean isEmpty(); /** * Empty: Empty the Stack */ public void Empty(); //Empty the stack }

//

//

public interface myQueue { /** * Enqueue/push (E): Add an element to the end of the sequence * @param element the element to be added to the Queue */ public void enqueue(E element); /** * Dequeue/pop: Remove an element from the start of the sequence * @return removes and returns the element at the start of the sequence */ public E dequeue(); /** * Front/Peek: Return the first element of the * sequence without removing it (what the head is pointing to) * @return returns the first element in the sequence */ public E front(); /** * Back: Return what the tail is pointing to * @return returns the last element in the sequence */ public E Back(); /** * atIndex(x): Return the element at the given index (x) Or * throw an exception if it is out of bound * (if you can control the user input then do that instead) * @param x the index of the element within the sequence * @return returns the element at the given index */ public E atIndex(int x); /** * Size: Return the size of the Queue * @return size of the queue */ public int size (); /** * isEmpty: Boolean, returns true if the Queue is empty * @return false if empty, true if populated */ public boolean isEmpty(); /** * Empty: Empty the Queue */ public void empty(); //Empty the Queue }