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.

The Queue ADT

The queue ADT is defined by the following operations:

Create a new, empty queue.
Add a new item to the queue.
Remove and return an item from the queue. The item that is returned is the first one that was added.
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 {

      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.

Last Update: 2005-12-05