5. Queue And Its Applications

In this lecture unit, we show:

• two methods to implement the queue class,

• applications of the queue class,

• inheritance used to derive a new data structure, called deque, or double-ended queue.

5.1 Queue Data Structure

A queue is a linear list of objects into which new objects can be inserted at one end called the back, and from which objects can be removed at the other end called the front of the queue.
• The queue is a FIFO (First-In-First-Out) data structure.

5.2 Linked List Implementation (1)

template <class T>
class Queue
{
public:
  Queue() : front(NULL), back(NULL) {}
  Queue(const Queue &rhs) { *this = rhs; }
  ~Queue() { makeEmpty(); }
  const Queue &operator=(const Queue &rhs);

  bool isEmpty() const { return front == NULL; }
  const T &getFront() const;
  void makeEmpty();
  T dequeue();
  void enqueue(const T &x);

private:
  struct ListNode
  {
    T element;
    ListNode *next;

    ListNode(const T &theElement, ListNode *n = NULL)
      : element(theElement), next(n) {}
  };

  ListNode *front;
  ListNode *back;
};

5.3 Linked List Implementation (2)

#include "Queue.h"

template <class T>
const Queue<T> &
Queue<T>::operator=(const Queue<T> &rhs)
{
  if (this != &rhs)
  {
    makeEmpty();
    ListNode *rp;
    for (rp = rhs.front; rp != NULL; rp = rp->next)
      enqueue(rp->element);
  }
  return *this;
}

template <class T>
void Queue<T>::enqueue(const T &x)
{
  if (isEmpty())
    back = front = new ListNode(x);
  else
    back = back->next = new ListNode(x);
}

template <class T>
T Queue<T>::dequeue()
{
  T frontItem = getFront();

  ListNode *old = front;
  front = front->next;
  delete old;
  return frontItem;
}

template <class T>
const T &Queue<T>::getFront() const
{
  if (isEmpty())
    throw UnderflowException();
  return front->element;
}

template <class T>
void Queue<T>::makeEmpty()
{
  while (!isEmpty())
    dequeue();
}

5.4 Array-Based Implementation (1)

// Array based Queue

template <class T>
class Queue
{
public:
  Queue() : theArray(1), front(0), back(0) {}

  bool isEmpty() const { return front == back; }
  const T &getFront() const;

  void makeEmpty() { front = back = 0; }
  void enqueue(const T &x);
  T dequeue();

private:
  int increment(int &x) const
    { if (++x == theArray.capacity()) x = 0;
      return x;
    }

private:
  vector<T> theArray;
  int front;
  int back;
};

5.5 Array-Based Implmentation (2)

#include "Queue.h"

template <class T>
void Queue<T>::enqueue(const T& x)
{
  theArray[back] = x;
  if (increment(back) == front) // Queue is full
  {
    int oldSize = theArray.capacity();
    theArray.resize(oldSize * 2 + 1);
    // Copy wrapped-around portion.
    for (int i = 0; i < front; ++i)
      theArray[i + oldSize] = theArray[i];
 
    back += oldSize;
  }
}

template <class T>
const T& Queue<T>::getFront() const
{
  if (isEmpty())
    throw UnderflowException();
  return theArray[front];
}

template <class T>
T Queue<T>::dequeue()
{
  if (isEmpty())
    throw UnderflowException();
  T frontItem = theArray[front];
  increment(front);
  return frontItem;
}

5.6 Array-Based Implmentation (3)

• Unlike stack, after many enqueue and dequeue operations, a queue migrates to the upper end of the array. It is necessary to view the array as circular so that if the queue reaches the upper end of the array, items can be wrapped around to the lower end.

• Two indexes are maintained: front -- position of the front item, and back -- next available cell, i.e. where the next enqueue operation will take place.

• In order to differentiate the full-queue and empty-queue conditions, we require that there is at least one empty cell in the array. The queue is considered full if only one empty cell remains.

5.7 Queue Application 1: Radix Sort

Let x[0], x[1], ... x[n-1] be a list of numbers in radix r. Assume each number has at most m digits. Let getDigit(x[i], k) return the value of the k-th least significant digit of x[i].

void radixSort(int x[], int n)
{
  Queue<int> Q[r];
  int i, j, k;
  for (k = 0; k < m; ++k)
  {
    // distribution phase
    for (i = 0; i < n; ++i)
      Q[getDigit(x[i], k)].enqueue(x[i]);

    // merge phase
    i = 0;
    for (j = 0; j < r; ++j)
      while (!Q[j].isEmpty())
        x[i++] = Q[j].dequeue();
  }
}

Example: Consider the array x of ternary numbers:

 x: 110  021  120  211  220  111  002  010  001  222

Radix sort produces the following snapshots of the queues and array x in each stage:

First stage:

  Q[0] : 110  120  220  010
  Q[1] : 021  211  111  001
  Q[2] : 002  222
  x    : 110  120  220  010  021  211  111  001  002  222

Second stage:

  Q[0] : 001  002
  Q[1] : 110  010  211  111
  Q[2] : 120  220  021  222
  x    : 001  002  110  010  211  111  120  220  021  222

Third stage:

  Q[0] : 001  002  010  021
  Q[1] : 110  111  120
  Q[2] : 211  220  222
  x    : 001  002  010  021  110  111  120  211  220  222

5.8 Queue Application 2: Breadth-First Search

A binary tree T is defined as a finite set of elements, called nodes, such that:

• T is empty (called the empty tree), or

• T contains a distinguished node r, called the root of T, and the remaining nodes form an ordered pair of disjoint binary trees T1 and T2.

Referring to the above definition, T1 is the left subtree and T2 is the right subtree of T (or of the root r). A node v of a binary tree has two children, denoted by lchild(v) and rchild(v), which are defined as follows:

• If the left [right] subtree of T is empty, then lchild(v) [rchild(v)] is empty, or

• lchild(v) [rchild(v)] is the root of the left [right] subtree of v.

A binary tree is usually represented by a diagram with the root at the top, and a slanted line (an edge) is extended from a parent to each of its children, with the left child to its left and the right child to its right. The following diagram is an example of binary tree.

                         A
                       /   \
                     B       C
                    / \     / \
                   D   E   F   G
                  / \     /
                 H   I   J

A breadth-first search in a binary tree is a traversal scheme that visits the nodes level by level, starting from the root level. It can be implemented using a queue as follows:

template <class T>
class Node
{
public:
  Node() : lchild(NULL), rchild(NULL) {}
  T &data() { return data; }
  Node *&lchild() { return lchild; }
  Node *&rchild() { return rchild; }
private:
  T data;
  Node *lchild;
  Node *rchild;
};

template <class T>
void breadthFirstSearch(Node<T> *root)
{
  Queue<Node<T> *> Q;
  Q.enqueue(root);
  while (!Q.isEmpty())
  {
    Node<T> *p = Q.dequeue();
    cout << p->data() << endl;
    if (p->lchild() != NULL)
      Q.enqueue(p->lchild());
    if (p->rchild() != NULL)
      Q.enqueue(p->rchild());
  }
}

5.9 Double-Ended Queue

A double-ended queue, or deque, is like a queue, except that access is allowed at both ends.

template <class T>
class Deque : private Queue<T> // privately inherited
{                                // from array-based Queue
public:
  void addFront(const T &x);
  void addBack(const T &x) { enqueue(x); }

  void removeFront() { dequeue(); }
  void removeBack();

  const T &getFront() const
    { return Queue::getFront(); }
  const T &getBack() const;

  bool isEmpty() const { return Queue::isEmpty(); }
  void makeEmpty() { Queue::makeEmpty(); }
}; 

Question: Is it possible to implement the other methods of the Deque class without changing the Queue class?