Implement a Queue
With a queue, we need fast operations at both ends because we will enqueue the last item at the back and dequeue first item from the front.
This makes a linked list the perfect data structure to implement a queue because we can achieve operations at the ends in O(1) time.
Unlike stacks, queues cannot be implemented using a dynamic array because adding an item at the front of the array would require O(n) time for re-indexing.
Our linked list will be built using Node objects that store data and use the prev attribute to reference the node behind it in the queue.
We will implement a peek, enqueue, and dequeue methods which operate in O(1) time because our queue maintains a that references the first and last item.
peek()
Peek allows us to view the first item that is at the front of the queue.
This is the oldest item that has been in the queue the longest.
We just return the value in our first pointer.
enqueue(item)
This method adds an item to the back of the queue.
The item that was previously at the end sets its prev pointer to reference the new item on the end.
Then we update the last pointer of the queue object to reference this new node since it is now at the back.
If an item is the first to be added (the queue was previously empty), we set it to be both the first and last item.
dequeue()
We remove the first item in the list.
The queue's first pointer is now set to the item after the one that was removed by setting this.first = removedItem.prev which sets a new front item.
If we only have one item remaining in the queue (first and last reference the same node), we also need to make sure that we set the last pointer to null to empty out the queue.
In the case of an empty queue, the first pointer will be set to null automatically because removedItem.prev is null.
Complete Queue Implementation
Putting it all together, we have the following implementation. If you want to see it in action, you can use it in this REPL.