The Queue ADT stores arbitrary objects and insertions and deletions of this ADT follow the first-in-first-out (FIFO) scheme i.e. insertions are at the rear of the queue and removals are from the front of the queue. As in a line or queue at a ticket stand, items are removed from the data structure in the same order that they are added.
Main stack operations:
- void enqueue(object): inserts an element at the end of the queue
- object dequeue(): removes and returns the last inserted element
Auxiliary stack operations:
- object front(): returns the front element without removing it
- integer size(): returns the number of elements stored
- boolean isEmpty(): indicates whether no elements are stored
Applications of Queue
Direct applications
- the waiting list, bureaucracy
- access to shared resources (e.g. printer)
- implementing the cache (evicting first cached element)
- OS multiprogramming
Indirect applications
- auxiliary data structures for algorithms e.g in Breadth-First search queue is to store a list of the nodes that need to be processed.
- component of other data structures
Linked List-based stack
Queue ADT implementation with Linked List is straightforward by maintaining pointers to both first and last element registered to the list.
Here is Java implementation for queue ADT.
import java.util.NoSuchElementException; public class MyQueue<T> { static class QueueNode<T> { T data; QueueNode next; QueueNode(T data) { this.data = data; this.next = null; } @Override public String toString() { return "(" + data + ")"; } } private QueueNode<T> first; private QueueNode<T> last; void enqueue(T data) { QueueNode<T> node = new QueueNode<>(data); if (last != null) { last.next = node; } last = node; if (first == null) { first = last; } } T dequeue() { if (first == null) throw new NoSuchElementException(); T data =first.data; first = first.next; if (first == null) { last = null; } return data; } T peek() { if (first == null) throw new NoSuchElementException(); return first.data; } boolean isEmpty() { return first == null; } }
Testing
The above implementation can be validated as below:
@Test public void testMyQueue() { MyQueue<Integer> queue = new MyQueue<>(); queue.enqueue(4); queue.enqueue(9); queue.enqueue(13); queue.enqueue(18); assertFalse(queue.isEmpty()); // peek assertEquals(Integer.valueOf(4), queue.peek()); assertEquals(Integer.valueOf(4), queue.peek()); // remove assertEquals(Integer.valueOf(4), queue.dequeue()); assertEquals(Integer.valueOf(9), queue.peek()); assertFalse(queue.isEmpty()); }
Performance
For n be the number of elements in the Queue
- The space used is O(n)
- Each operation runs in time O(1)
All the source code presented above is available on GitHub.