10.3.2. Linked Queues

Representing a FIFO queue

---

Now let's turn to the issue of implementing FIFO queues. Our goal is to make each operation on a queue to take a constant amount of time, independent of the length of the queue. That is, each operation should take O(1) time.

The first concern is how to represent the information in a queue. A reasonable choice is a linked list, in order from the first item in the queue to the last item. But that has a difficulty. To add an item to the end requires traversing the entire list to find the end, which does not meet our constant time requirement.

We can improve on that by keeping two pointers, one to the first cell and one to the last cell. For example, if q holds [2,4,6] (from front to back), then we keep a structure holding two pointers, front and back, such as the following.

         ____       ____       ____       ____
        |    |     |    |     |    |     |    |
  front | -------->| -------->|  ------->|  -----\
        |----|     |----|     |----|     |----|
   back | ------   | 2  |     | 4  |     | 6  |
        |____|  |  |____|     |____|   ->|____|
                |                     |
                |_____________________|

But notice that the last list cell holds a null pointer. We don't really need that; we can recognize the last cell because its address is the same as the back pointer. Can we put that pointer to use? If it points to the front of the list, then we can dispense with the front pointer, keeping only the back pointer. The front pointer is just back->next. So our diagram looks like this.

                 ---------------------------------
                |   ____       ____       ____    |
                |  |    |     |    |     |    |   |
         ____    ->| -------->|  ------->|  ------
        |    |     |----|     |----|     |----|
   back | ------   | 2  |     | 4  |     | 6  |
        |____|  |  |____|     |____|   ->|____|
                |                     |
                |_____________________|

There is still the matter of an empty queue to consider. An obvious way to represent an empty queue is using a null back pointer, and that is what we do.

Shrink-wrapping the queue

---

Our goal is to implement an abstract data type. Only the module that implements this type should be aware of how the information is represented. It would not be possible for another module to say

  Queue q = NULL;

A header file

---

File queue.h holds the required types and prototypes for the functions. Notice that it is not necessary to say what a QueueCell looks like, so we move that information into the implementation file, queue.cpp.

To understand the functions, work them through by hand on a drawing of an example queue.

  struct QueueCell;

  struct Queue
  {
    QueueCell* back;

    Queue()
    {
      back = NULL;
    }
  };

  bool isEmpty     (const Queue& q);
  void insertAtEnd (int x, Queue& q);
  int  removeFirst (Queue& q);
  int  peek        (const Queue& q);

Implementation

---

  #include "queue.h"

  struct QueueCell
  {
    int        item;
    QueueCell* next;

    QueueCell(int it, QueueCell* nx)
    {
      item = it;
      next = nx;
    }
  };

  // The front of the queue is found in the 'next'
  // pointer of the back cell.

  #define FRONT back->next

  //=====================================
  //          isEmpty
  //=====================================
  // Return true if q is an empty queue.
  //=====================================

  bool isEmpty(const Queue& q)
  {
    return q.back == NULL;
  }

  //=====================================
  //          insertAtEnd
  //=====================================
  // Insert x at the back of queue q.
  //=====================================

  void insertAtEnd(int x, Queue& q)
  {
    if(q.back == NULL)
    {
      QueueCell* p = new QueueCell(x, NULL);
      p->next = p;
      q.back  = p;
    }
    else
    {
      QueueCell* p = new QueueCell(x, q.FRONT);
      q.back->next = p;
      q.back = p;
    }
  }

  //=====================================
  //          peek
  //=====================================
  // Return the first item in queue q.
  // If q is empty, return -1.
  //=====================================

  void peek(const Queue& q)
  {
    if(isEmpty(q))
    {
      return -1;
    }
    else
    {
      return q.FRONT->item;
    }
  }

  //=====================================
  //          removeFirst
  //=====================================
  // Remove and return the first item in
  // queue q.  If q is empty, return -1
  // and do not modify q.
  //=====================================

  void removeFirst(Queue& q)
  {
    if(isEmpty(q))
    {
      return -1;
    }
    else 
    {
      QueueCell* f      = q.FRONT;
      int        result = f->item;

      if(q.back == f)  // Removing last item
      {
        q.back = NULL;
      }
      else
      {
        q.FRONT = f->next;
      }

      delete f;
      return result;
    }
  }

Exercises

---

1. Why can't type Queue be defined more simply by

     typedef QueueCell* Queue;
   

   instead of creating a structure type that contains a pointer? Answer

2. Would it be reasonable to represent a queue as a linked list of its members from back to front, with a pointer to he first cell and a pointer to the last cell? Answer

3. A doubly-linked list has two pointers in each cell, one to the next cell and one to the previous cell. Would a doubly-linked list work for representing a queue? Answer

4. A deque is like a queue except that you can remove from either end and add a new value to either end. So you might have functions insertAtFront, insertAtEnd, removeFromFront and removeFromEnd. Does the representation used here allow all of those operations to be done in constant time per operation? Answer

5. See the previous two questions for descriptions of doubly linked lists and deques. Does use of a doubly-linked list allow for efficient implementation of a deque? Answer