使用Doubly Linked List，代写数据结构中的Stack和Queue的方法。
Requirement
The goal of lab 3 is to get you to utilize an already implemented structure to build another one. Given two interfaces and a doubly linked list (code provided to you in the lecture note) 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. In addition to implementing the structures you have to make sure that each collection can return an iterator. You may edit it and you may also modify it but you must include it as part of your implementation.
Implement a Stack
A Stack is a Last in First Out (LiFO) structure which translates to the processes of outputting the last element which was inputted in the collection. The Stack is based on the process of putting things on top of one another and taking the item on top (think of a stack of papers).
Operations to implement:
- 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
- GetIterator: Returns an iterator
Implement a Queue
A Queue is a First in First Out (FiFO) structure which translates to the processes of outputting the first item inputted into a collection. The Queue is based on the process of waiting in line to get serviced (bank or six flags), where those who arrive first get serviced first.
Operations to implement:
- Enqueue/push (E): Add an element to the end of the sequence
- Dequeue/pop: Remove an element from the start of the sequence
- Front/Peek: Return the first element of the sequence without removing it (what the head is pointing to)
- 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
- Back: Return what the tail is pointing to
- GetIterator: Returns an iterator
What to submit
One zip file consisting of 6 different files. A mystack interface, a myQueue Interface node class (.Java), a linked list class (.java), a Queue class (.java), and Stack class (.java).
Avoid bad naming conventions.
- DNode.java
- DoublyLinkedList.java
- myQueue.java
- myStack.java