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 Linked Queue
See also: Queues and Priority Queues 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Linked Queue

We would like an implementation of the Queue ADT that can perform all operations in constant time. One way to accomplish that is to implement a linked queue, which is similar to a linked list in the sense that it is made up of zero or more linked Node objects. The difference is that the queue maintains a reference to both the first and the last node, as shown in the figure.

Here's what a linked Queue implementation looks like:

class Queue {
    public:
       Node *first, *last;

    Queue () {
        first = null;
        last = null;
    }

    boolean empty () {
        return first == null;
    }
};

So far it is straightforward. In an empty queue, both first and last are null. To check whether a list is empty, we only have to check one of them.

insert is a little more complicated because we have to deal with several special cases.

    void insert (Node* node) {
        Node* node = new Node (node->cargo, null);
        if (last != null) {
            last->next = node;
        }
        last = node;
        if (first == null) {
            first = last;
        }
    }

The first condition checks to make sure that last refers to a node; if it does then we have to make it refer to the new node.

The second condition deals with the special case where the list was initially empty. In this case both first and last refer to the new node.

remove also deals with several special cases.

    Node* remove () {
        Node* result = first;
        if (first != null) {
            first = first.next;
        }
        if (first == null) {
            last = null;
        }
        return result;
    }

The first condition checks whether there were any nodes in the queue. If so, we have to copy the next node into first. The second condition deals with the special case that the list is now empty, in which case we have to make last null.

As an exercise, draw diagrams showing both operations in both the normal case and in the special cases, and convince yourself that they are correct.

Clearly, this implementation is more complicated than the veneer implementation, and it is more difficult to demonstrate that it is correct. The advantage is that we have achieved the goal: both insert and remove are constant time.
Home Queues and Priority Queues Linked Queue

Last Update: 2005-12-05