For this projects, you want to wrap alinked list and not inherit it. The linked list has a lot of operations which can easily break your Stack or Queue. Giving others access to these code-breaking methods is not smart… not smart at all. You want to hide these methods from those who use your linked list and only offer the methods related to the stack and queue object.
Implement a Stack (3 points)
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
Implement a Queue (3 points)
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(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
Providing a data structure that is a bit persistent (4 points)
“Apersistent data structureis one in which no operations result in permanent changes to the underlying structure. It's called “persistent” because as the structure goes through successive operations, all versions of the structure persist over time. The notion of a structure with no permanent changes may sound like an oxymoron:”Source(Links to an external site.)
This is too complex and messy for a comp 182, however, you are more than free to go and read more on them.
For your structures to be considered a little persistent in this project it will need to support a few features: (Throwing all of the benefits of a linked list out of the window)
- (2 points)Your structure must beimmutable
(like a string)
You loose all points if it is mutable
- That means you will have to go back and make the linked list immutable and both your stack and queue need to be immutable as well.
- In other words, every time you make a modification to your collection, you return a completely new one.
- Hint: Think about making a .clone method or an alternative to it for your structure
- (1 point)Support proper value equality semantics in their implementation of equals
- Hint: Implement the Comparable interface for your elements
- So you can go and do: myCollection1.equals(myCollection2)
- (1point) Implement Interface Iterable
What to submit
One zip file consisting of 4different files. A Node class (.java), a MyLinkedList class (.java), a MyQueue class (.java), and MyStack class (.java).
Avoid bad naming conventions