Queue is a First In First Out (FIFO) data structure. For example, job queue is used to decouple producer and worker threads, producer threads put tasks to the head of the queue, while worker threads take the task at the end of the queue. The consumer and producer are decoupled, yet they are communicating through the tasks in the queue. Worker threads take task from the queue one by one until getting a poison pill task put by the producer, then invoke the exiting procedure.
The basic operations are enqueue and dequeue.
Like Stack, queue can also be implemented with linked list or array.
Stack and queue interfaces have one thing in common -- they don't require random access node, they always add or remove elements from the ends. Stack adds and removes at head, while queue adds at head but removes at tail. Linked list has a header pointer, we can add a tail pointer as well to mark the two special position in the link chain -- start and end. Implementing FIFO queue with linked list again is quite natural.
 |
| linked list as FIFO queue |
If implemented with linked list, we need an extra variable to store the tail node, then the enqueue can be implemented by adding a new node behind the tail node; while the dequeue can be implemented by removing the node behind the header node. Both enqueue and dequeue have time complexity O(1). We need a N node linked list to implement a size N queue, the space complexity is O(N).
If implemented with ArrayList, we need an extra variable to store the head index of the queue, then the enqueue can be implemented by delegating to ArrayList's add method; while the dequeue can be implemented by delegating to ArrayList's get method, then move head index one position right-ward.
Both enqueue and dequeue have time complexity O(1).
Each dequeue operation will move the header index rightward, so after a while, the head index has to be reset to 0 in order to reuse the space in the ArrayList (indexes smaller than head index). That operation needs to move all the queue elements leftward, which has time complexity O(N).
We need an ArrayList of size bigger than N to implement the size N queue, the space complexity is O(N).
Sample Code (not thread safe):
LNode.java
QueueImplLinkedList.java
QueueImplList.java
