The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Queues and Priority Queues The Queue ADT
See also: Queues and Priority Queues 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

The Queue ADT

The queue ADT is defined by the following operations:

constructor
Create a new, empty queue.
insert
Add a new item to the queue.
remove
Remove and return an item from the queue. The item that is returned is the first one that was added.
empty
Check whether the queue is empty.

To demonstrate a queue implementation, I will take advantage of the LinkedList class from Chapter 18. Also, I will assume that we have a class named Customer that defines all the information about each customer, and the operations we can perform on customers.

As far as our implementation goes, it does not matter what kind of object is in the Queue, so we can make it generic. Here is what the implementation looks like.

class Queue {
    public:

      LinkedList list;

      Queue () {
        list = new List ();
      }

      bool empty () {
        return list.empty ();
      }

      void insert (Node* node) {
        list.addLast (node);
      }

      Node* remove () {
        return list.removeFirst ();
      }
};

A queue object contains a single instance variable, which is the list that implements it. For each of the other methods, all we have to do is invoke one of the methods from the LinkedList class.
Home Queues and Priority Queues The Queue ADT

Last Update: 2005-12-05