Queue

Internal

• Data Structures
• Stack
• Deque

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

https://github.com/ovidiuf/playground/blob/master/algorithms/graphs/adjacency-list/src/main/java/playground/graphs/adj/Q.java

Alternative Implementations

Alternative implementations that keep track of head and the tail explicitly, instead of size and tail, are provided below:

Queue Alternative Implementations

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