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:
Alternative Implementation
The following implementation uses an array, which dictates the queue length. The queue grows circularly and wraps around the edge of the array as the data is enqueued and dequeued. We use to pointers, "head" and "tail", containing the indexes of the corresponding head and tail elements. The "head" pointer indicates the head element - the one that will be dequeued next, while "tail" points to the position where the next enqueued element will be placed.
An empty queue is indicated by the fact that the "head" and the "tail" pointers have the same value.
We have two choices when it comes to model a full queue. If we want to use all the n elements in the array for queue element storage, then we model the "full" position with an external boolean, because otherwise there would be no way to distinguish the "empty queue" head and tail overlap and "full queue" head and tail overlap. Another possibility is to use only n - 1 elements of the array for queue element storage, and use one array element as a "marker" that always separates the head from the tail. This way, the "head" and "tail" pointers never overlap for a full queue, just for an empty queue.
The equivalent implementations are presented below:
n element Queue
We model "full" and "empty" by allowing the "head" and "tail" markers to overlap, and we maintain an extra bit of data that tells those states apart. This way we can use all n array elements for queue element storage.
/**
* A queue of ints that uses all n storage elements for queue element storage.
* It needs an additional boolean variable to maintain whether the queue is
* full or not.
*/
public class Queue {
private int[] storage;
// this is the index of the queue head element
private int head;
// this is the index of the element where the tail *would* go
private int tail;
private boolean full;
public Queue(int capacity) {
this.storage = new int[capacity];
this.head = 0;
this.tail = 0;
this.full = false;
}
public void enqueue(int i) throws QueueOverflowException {
//
// check if the queue is full
//
if (full) {
throw new QueueOverflowException();
}
storage[tail] = i;
tail = (tail + 1) % storage.length;
//
// this is the only time we can determine the queue is full
//
if (head == tail) {
this.full = true;
}
}
public int dequeue() throws QueueUnderflowException {
if (head == tail && !full) {
throw new QueueUnderflowException();
}
int result = storage[head];
head = (head + 1) % storage.length;
full = false;
return result;
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return full;
}
}
n-1 element Queue
We model by allowing the "head" and "tail" markers to overlap, and the full queue will always have a gap between head and tail. This way we can use only n-1 array elements for queue element storage.
/**
* A queue of ints that uses just n-1 storage elements for queue element storage, and
* it can tell when it is full without maintaining an additional boolean variable.
*/
public class Queue {
private int[] storage;
// this is the index of the queue head element
private int head;
// this is the index of the element where the tail *would* go
private int tail;
public Queue(int capacity) {
this.storage = new int[capacity];
this.head = 0;
this.tail = 0;
}
public void enqueue(int i) throws QueueOverflowException {
//
// verify whether by enqueueing this element the tail will overlap with the head
// if they do, it means the queue is full
//
if ((tail + 1) % storage.length == head) {
throw new QueueOverflowException();
}
storage[tail] = i;
tail = (tail + 1) % storage.length;
}
public int dequeue() throws QueueUnderflowException {
if (head == tail) {
throw new QueueUnderflowException();
}
int result = storage[head];
head = (head + 1) % storage.length;
return result;
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return (tail + 1) % storage.length == head;
}
}
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