Queues are another restricted access data structure, much like stacks.  A queue is like a one-way line where data enters the end of the line and exits from the front of the line.  The apqueue class will support operations similar to but different from stacks.

The key topics for this lesson are:

A.  Queues

B.   Operations on Queues

C.  Implementing Queues as a Linked List

VOCABULARY:                   QUEUE                                   ENQUEUE

                                                DEQUEUE

  DISCUSSION:                       A.  Queues

 1.   A queue is a linear data structure which simulates waiting in line.  A queue has two ends, a front and a (rear) end. 

2.   Data must always enter the queue at the end and leave from the front of the line.  This type of action can be summarized as FIFO (first-in, first-out).

3.   All the data stored in a queue must be of the same type.

4.   A queue is the appropriate data structure when simulating waiting in line.  A printer which is part of a multi-user network must process print commands on a first-come, first-served basis.  A queue would be used to store the jobs in a line.

B.   Operations on Queues

1.   The following operations are supported by the apqueue class:

  Constructors

      apqueue(); // default constructor

      apqueue (const apqueue & q);      // copy constructor

      ~apqueue ();          // destructor

Assignment

      const apqueue & operator= (const apqueue &rhs);

Accessors

      const itemType & front() const;  // return front, no dequeue

      bool isEmpty() const;        // return true if empty, else false

      int  length() const; // return number of elements in queue

Modifiers

      void enqueue (const itemType &item);     // insert item at rear

      void dequeue ();                // remove first element

      void dequeue (itemType & item);  // combine front and dequeue

      void makeEmpty ();          // make queue empty

2.   Using the templated apqueue class is very similar to using the apstack class.  Here is a sample program which uses some of the key operations provided by the apqueue class.

      Program 42-1

#include <iostream.h>

#include <apqueue.cpp>

main()

{

        apqueue <int> queue;

        int k;

        for (k=1; k<=5; k++)

                queue.enqueue(k);

        while (!queue.isEmpty())

        {

                queue.dequeue(k);

                cout << k << " ";

        }

        return 0;

}

Run output:

1 2 3 4 5

C.  Implementing Queues as a Linked List

1.   A queue can be implemented as a vector or a linked list.  The author of the apqueue class chose to use an apvector.  If we use a linked list to implement a queue we must deal with the following issues.

  2.   Two external pointers must be used to keep track of the front and end of the queue.  When discussing a queue it is traditional to add new data at the end of the queue, as in "get in at the end of the line."   The term enqueue is used to describe this operation.

3.   Data will be removed from the "front" of the queue.  This operation is called dequeue. 

4.   A queue can be implemented as a singly-linked list if the two external pointers are appropriately placed.

5.   When a new piece of data is added to the tail of the queue (enqueue), the external pointer myEnd must be moved to point to the new node added to the list.

6.   When an old piece of data is extracted from the queue (dequeue), the external pointer myFront must be advanced to the appropriate node after the data has been removed.  The delete operation should be applied to the unwanted node of information.

SUMMARY/REVIEW:         Queues serve a very useful function whenever a program needs to simulate waiting in line.  One of the lab exercises will require queues to solve an intriguing problem regarding binary trees.

  ASSIGNMENT:                    Lab Exercise L.A.42.1, Printbylevel

                                                Lab Exercise L.A.42.2, RPN