Queue is a datastructure commonly used in procressing work in defined order. Queues are First-in-First-out (FIFO), meaning that elements first stored in the queue are also the first elements to be removed from the queue. This is different to a First-in-Last-out datastrcture (Stack).
Queues can be implemented with both an internal array or a list. When using an internal array, the elements in the array needs to be rearranged when an element in the queue is removed. A Linked list implementation of a queue updates the reference of the element in the queue.
Queue Array Implementation
Image shows an example of an array implementation of a queue:
Queues can be represented by a linked list implementation. The implementation maintains two pointers:
head - Item that dequeues first
tail - Item that updates reference to the newly added item.
These pointers in the linked list implementation keeps reference of the item to dequeue and the item to enqueue onto, there is no need to maintain/ reorganize existing elements in the queue. The operation of updating the references has a time and space complexity of O(1) when we ignore the need to traverse through the queue.