A Queue Class

The first order of business is to design a Queue class. First, you need to list the attributes of the kind of queue you’ll need:

• A queue holds an ordered sequence of items.

• A queue has a limit on the number of items it can hold.

• You should be able to create an empty queue.

• You should be able to check whether a queue is empty.

• You should be able to check whether a queue is full.

• You should be able to add an item to the end of a queue.

• You should be able to remove an item from the front of a queue.

• You should be able to determine the number of items in the queue.

As usual when designing a class, you need to develop a public interface and a private implementation.

The Queue Class Interface

The queue attributes listed in the preceding section suggest the following public interface for a queue class:

class Queue
{
    enum {Q_SIZE = 10};
private:
// private representation to be developed later
public:
    Queue(int qs = Q_SIZE); // create queue with a qs limit
    ~Queue();
    bool isempty() const;
    bool isfull() const;
    int queuecount() const;
    bool enqueue(const Item &item); // add item to end
    bool dequeue(Item &item);       // remove item from front
};

The constructor creates an empty queue. By default, the queue can hold up to 10 items, but that can be overridden with an explicit initialization argument:

Queue line1;                // queue with 10-item limit
Queue line2(20);            // queue with 20-item limit

When using the queue, you can use a typedef to define Item. (In Chapter 14, “Reusing Code in C++,” you’ll learn how to use class templates instead.)

The Queue Class Implementation

After you determine the interface, you can implement it. First, you have to decide how to represent the queue data. One approach is to use new to dynamically allocate an array with the required number of elements. However, arrays aren’t a good match to queue operations. For example, removing an item from the front of the array should be followed up by shifting every remaining element one unit closer to the front. Otherwise, you need to do something more elaborate, such as treat the array as circular. Using a linked list, however, is a reasonable fit to the requirements of a queue. A linked list consists of a sequence of nodes. Each node contains the information to be held in the list, plus a pointer to the next node in the list. For the queue in this example, each data part is a type Item value, and you can use a structure to represent a node:

struct Node
{
     Item item;             // data stored in the node
     struct Node * next;    // pointer to next node
};

Figure 12.8 illustrates a linked list.

Figure 12.8. A linked list.

The example shown in Figure 12.8 is called a singly linked list because each node has a single link, or pointer, to another node. If you have the address of the first node, you can follow the pointers to each subsequent node in the list. Commonly, the pointer in the last node in the list is set to NULL (or, equivalently, to 0) to indicate that there are no further nodes. With C++11, you should use the new nullptr keyword. To keep track of a linked list, you must know the address of the first node. You can use a data member of the Queue class to point to the beginning of the list. In principle, that’s all the information you need because you can trace down the chain of nodes to find any other node. However, because a queue always adds a new item to the end of the queue, it is convenient to have a data member point to the last node, too (see Figure 12.9). In addition, you can use data members to keep track of the maximum number of items allowed in the queue and of the current number of items. Thus, the private part of the class declaration can look like this:

class Queue
{
private:
// class scope definitions
    // Node is a nested structure definition local to this class
    struct Node { Item item; struct Node * next;};
    enum {Q_SIZE = 10};
// private class members
    Node * front;       // pointer to front of Queue
    Node * rear;        // pointer to rear of Queue
    int items;          // current number of items in Queue
    const int qsize;    // maximum number of items in Queue
    ...
public:
//...
};

Figure 12.9. A Queue object.

The declaration uses the C++ ability to nest a structure or class declaration inside a class. By placing the Node declaration inside the Queue class, you give it class scope. That is, Node is a type that you can use to declare class members and as a type name in class methods, but the type is restricted to the class. That way, you don’t have to worry about this declaration of Node conflicting with some global declaration or with a Node declared inside some other class. Some obsolescent compilers do not support nested structures and classes. If yours doesn’t, then you have to define a Node structure globally, giving it file scope.

After you settle on a data representation, the next step is to code the class methods.

The Class Methods

A class constructor should provide values for the class members. Because the queue in this example begins in an empty state, you should set the front and rear pointers to NULL (or 0 or nullptr) and items to 0. Also you should set the maximum queue size qsize to the constructor argument qs. Here’s an implementation that does not work:

Queue::Queue(int qs)
{
    front = rear = NULL;
    items = 0;
    qsize = qs;    // not acceptable!
}

The problem is that qsize is a const, so it can be initialized to a value, but it can’t be assigned a value. Conceptually, calling a constructor creates an object before the code within the brackets is executed. Thus, calling the Queue(int qs) constructor causes the program to first allocate space for the four member variables. Then program flow enters the brackets and uses ordinary assignment to place values into the allocated space. Therefore, if you want to initialize a const data member, you have to do so when the object is created before execution reaches the body of the constructor. C++ provides a special syntax for doing just that. It’s called a member initializer list. The member initializer list consists of a comma-separated list of initializers preceded by a colon. It’s placed after the closing parenthesis of the argument list and before the opening bracket of the function body. If a data member is named mdata and if it’s to be initialized to the value val, the initializer has the form mdata(val). Using this notation, you can write the Queue constructor like this:

Queue::Queue(int qs) : qsize(qs)   // initialize qsize to qs
{
    front = rear = NULL;
    items = 0;
}

In general, the initial value can involve constants and arguments from the constructor’s argument list. The technique is not limited to initializing constants; you can also write the Queue constructor like this:

Queue::Queue(int qs) : qsize(qs), front(NULL), rear(NULL), items(0)
{
}

Only constructors can use this initializer-list syntax. As you’ve seen, you have to use this syntax for const class members. You also have to use it for class members that are declared as references:

class Agency {...};
class Agent
{
private:
    Agency & belong;    // must use initializer list to initialize
    ...
};
Agent::Agent(Agency & a) : belong(a) {...}

That’s because references, like const data, can be initialized only when created. For simple data members, such as front and items, it doesn’t make much difference whether you use a member initializer list or use assignment in the function body. As you’ll see in Chapter 14, however, it’s more efficient to use the member initializer list for members that are themselves class objects.

The parenthesized form used in the member initializer list can be used in ordinary initializations, too. That is, if you like, you can replace code such as

int games = 162;
double talk = 2.71828;

with

int games(162);
double talk(2.71828);

This allows initializing built-in types to look like initializing class objects.

The code for isempty(), isfull(), and queuecount() is simple. If items is 0, the queue is empty. If items is qsize, the queue is full. Returning the value of items answers the question of how many items are in the queue. You’ll see the code later this chapter in Listing 12.11.

Adding an item to the rear of the queue (enqueuing) is more involved. Here is one approach:

bool Queue::enqueue(const Item & item)
{
    if (isfull())
        return false;
    Node * add = new Node;  // create node
// on failure, new throws std::bad_alloc exception
    add->item = item;       // set node pointers
    add->next = NULL;       // or nullptr;
    items++;
    if (front == NULL)      // if queue is empty,
        front = add;        // place item at front
    else
        rear->next = add;   // else place at rear
    rear = add;             // have rear point to new node
    return true;
}

In brief, the method goes through the following phases (see Figure 12.10):

1. Terminate if the queue is already full. (For this implementation, the maximum size is selected by the user via the constructor.)

2. Create a new node. If new can’t do so, it throws an exception, which is a topic taken up in Chapter 15, “Friends, Exceptions, and More.” The practical upshot is that unless one provides additional programming to handle the exception, the program terminates.

3. Place proper values into the node. In this case, the code copies an Item value into the data part of the node and sets the node’s next pointer to NULL (or 0 or, in C++11, nullptr). This prepares the node to be the last item in the queue.

4. Increase the item count (items) by one.

5. Attach the node to the rear of the queue. There are two parts to this process. The first is linking the node to the other nodes in the list. This is done by having the next pointer of the currently rear node point to the new rear node. The second part is to set the Queue member pointer rear to point to the new node so that the queue can access the last node directly. If the queue is empty, you must also set the front pointer to point to the new node. (If there’s just one node, it’s both the front and the rear node.)

Figure 12.10. Enqueuing an item.

Removing an item from the front of the queue (dequeuing) also has several steps. Here is one approach:

bool Queue::dequeue(Item & item)
{
    if (front == NULL)
        return false;
    item = front->item;     // set item to first item in queue
    items--;
    Node * temp = front;    // save location of first item
    front = front->next;    // reset front to next item
    delete temp;            // delete former first item
    if (items == 0)
        rear = NULL;
    return true;
}

In brief, the method goes through the following phases (see Figure 12.11):

1. Terminate if the queue is already empty.

2. Provide the first item in the queue to the calling function. This is accomplished by copying the data portion of the current front node into the reference variable passed to the method.

3. Decrease the item count (items) by one.

4. Save the location of the front node for later deletion.

5. Take the node off the queue. This is accomplished by setting the Queue member pointer front to point to the next node, whose address is provided by front->next.

6. To conserve memory, delete the former first node.

7. If the list is now empty, set rear to NULL. (The front pointer would already be NULL in this case, after setting front->next.) Again, you can use 0 instead of NULL, or, with C++11, you can use nullptr.

Figure 12.11. Dequeuing an item.

Step 4 is necessary because step 5 erases the queue’s memory of where the former first node is.

Other Class Methods?

Do you need any more methods? The class constructor doesn’t use new, so at first glance, it may appear that you don’t have to worry about the special requirements of classes that do use new in the constructors. Of course, that first glance is misleading because adding objects to a queue does invoke new to create new nodes. It’s true that the dequeue() method cleans up by deleting nodes, but there’s no guarantee that a queue will be empty when it expires. Therefore, the class does require an explicit destructor—one that deletes all remaining nodes. Here’s an implementation that starts at the front of the list and deletes each node in turn:

Queue::~Queue()
{
    Node * temp;
    while (front != NULL)   // while queue is not yet empty
    {
        temp = front;       // save address of front item
        front = front->next;// reset pointer to next item
        delete temp;        // delete former front
    }
}

Hmmm. You’ve seen that classes that use new usually require explicit copy constructors and assignment operators that do deep copying. Is that the case here? The first question to answer is, “Does the default memberwise copying do the right thing?” The answer is no. Memberwise copying of a Queue object would produce a new object that points to the front and rear of the same linked list as the original. Thus, adding an item to the copy Queue object changes the shared linked list. That’s bad enough. What’s worse is that only the copy’s rear pointer gets updated, essentially corrupting the list from the standpoint of the original object. Clearly, then, cloning or copying queues requires providing a copy constructor and an assignment constructor that do deep copying.

Of course, that raises the question of why you would want to copy a queue. Well, perhaps you would want to save snapshots of a queue during different stages of a simulation. Or you would like to provide identical input to two different strategies. Actually, it might be useful to have operations that split a queue, the way supermarkets sometimes do when opening an additional checkout stand. Similarly, you might want to combine two queues into one or truncate a queue.

But suppose you don’t want to do any of these things in this simulation. Can’t you simply ignore those concerns and use the methods you already have? Of course you can. However, at some time in the future, you might need to use a queue again, but with copying. And you might forget that you failed to provide proper code for copying. In that case, your programs will compile and run, but they will generate puzzling results and crashes. So it would seem that it’s best to provide a copy constructor and an assignment operator, even though you don’t need them now.

Fortunately, there is a sneaky way to avoid doing this extra work while still protecting against future program crashes. The idea is to define the required methods as dummy private methods:

class Queue
{
private:
    Queue(const Queue & q) : qsize(0) { }   // preemptive definition
    Queue & operator=(const Queue & q) { return *this;}
//...
};

This has two effects. First, it overrides the default method definitions that otherwise would be generated automatically. Second, because these methods are private, they can’t be used by the world at large. That is, if nip and tuck are Queue objects, the compiler won’t allow the following:

Queue snick(nip);     // not allowed
tuck = nip;           // not allowed

Therefore, instead of being faced with mysterious runtime malfunctions in the future, you’ll get an easier-to-trace compiler error, stating that these methods aren’t accessible. Also this trick is useful when you define a class whose objects really should not be copied.

C++11 provides an alternative way to disable a method by using the keyword delete; Chapter 18 returns to this topic.

Are there any other effects to note? Yes. Recall that a copy constructor is invoked when objects are passed (or returned) by value. However, this is no problem if you follow the preferred practice of passing objects as references. Also a copy constructor is used to create other temporary objects. But the Queue definition lacks operations that lead to temporary objects, such as overloading the addition operator.