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
dequeue methods which operate in O(1) time because our queue maintains a that references the
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
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
We remove the first item in the list.
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 (
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
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.
Table of Contents