Queue
Internal
Overview
A queue is a dynamic set whose DELETE operation, which does not have any argument, removes the oldest element in the queue. The queue implements the first-in-first-out, or FIFO, policy. The queue has a head and a tail. The INSERT operation for a queue is called ENQUEUE and places the new element at the tail. The DELETE operation is called DEQUEUE, and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue underflows. If we attempt to enqueue an element on a full queue, it is said that the queue overflows.
The queue is an essential component in implementing the Breadth-First Search (BFS) algorithm in graphs.
Implementation
The implementation maintains the content into an n element array a
, which establishes the queue capacity. We also maintain two variables: the current size of the queue as s
, and the position where to insert a new element as t
or "tail". Both are initialized to 0.
public class Queue<T> {
private final Object[] a;
private int s; // size
private int t; // tail, the index of the location where to insert next element
public Queue(int capacity) {
this.a = new Object[capacity];
this.s = 0;
this.t = 0;
}
}
Enqueueing verifies whether the queue still has capacity, and if it does, stores the element on position t
, advances the tail with one position, wrapping around if necessary, and updates the size s
.
public void enqueue(T e) {
if (s == a.length) {
// queue full
throw new QueueOverflowException();
}
a[t] = e;
t = (t + 1) % a.length;
s++;
}
Dequeueing verifies whether the queue has elements, and if it does, computes the head of the queue from t
and s
, wrapping around if necessary, saves the element, updates the size and returns the element:
public T dequeue() {
if (s == 0) {
// queue empty
throw new QueueUndeflowException();
}
// compute head
int h = (a.length + t - s) % a.length;
T e = (T)a[h];
s--; // update size
return e;
}
Playground Implementation
Alternative Implementations
Alternative implementations that keep track of head and the tail explicitly, instead of size and tail, are provided below:
Miscellaneous
- Example of a queue implemented using two stacks: Playground - Queue implemented with Two Stacks
- TODO Example of a stack implemented using two queues. CLRS page 236.
- Process this: https://github.com/jwasham/coding-interview-university#queue