C++ queue tutorial

C++ queue tutorial for newbies

Introduction

This tutorial introduces the C++ queue data structure. I will describe what a queue is and create a simple example for you to follow along with.

What is a queue?

A queue is a waiting line. Like a line of people at a movie theatre waiting to buy tickets. The first person in the line is the first person to be served. In other words: first-in, first-out or FIFO.

Basic C++ queue operations

Queue :: Queue( ); A queue is created and initialised to be empty

Error_code Queue :: append(const Queue_entry &x); If there is space, x is added to the Queue at its rear. Otherwise
an Error_code of overflow is returned.

Error_code Queue :: serve( ); If the Queue is not empty, the front of the Queue is removed.
Otherwise an Error_code of underflow is returned.

Error_code Queue :: retrieve(Queue_entry &x) const; If the Queue is not empty, the front of the Queue is
recorded as x. Otherwise an Error_code of underflow is returned.

bool Queue :: empty( ) const; Returns true if Queue is empty, otherwise return false.

Extended queue operations

In addition to the fundamental operations; serve, retrieve, append & empty, there are several other useful methods we could use. From our base class Queue we shall inherit these basic methods and add a few new ones in our new class Extended_queue. The new methods are:

bool Extended_queue :: full( ) const; Returns true if Extended_queue is full. Otherwise it returns false.

void Extended_queue :: clear( ); Remove all entries in Extended_queue

int Extended_queue :: size( ) const; Return the number of entries in the Extended_queue.

Error_code Extended_queue :: serve_and_retrieve(Queue_entry &item); Return underflow if the Extended_queue is empty. Otherwise
remove and copy the item at the front of the Extended_queue to
item and return success.

Implementation of queues

We will implement a circular queue. To illustrate look at the following diagrams(courtesy of Wikipedia)

 

The oldest element in the queue is labelled ‘1’ and the newest element is labelled ‘3’. This queue is 7 elements large. All new elements are added to the left of the last element. When the queue fills up, new elements overwrite the oldest element in the queue. Using the example above, assuming we follow the numerical order, we add 4 then 5 then 6 then 7. Then the queue is full. If we were to add 8 into the queue, then the 1st element 1 will be overwritten and the new head of the queue will point to the value 2. Kind of like a 12-hour clock. After 12, it starts back at 1.

 

In our case, instead of overwriting the older elements in the queue, we throw an overflow error.

Source code

The Error_code type is declared in utility.h, which is declared below

We will have a queue consisting of single-character elements. The element class, entry.h is declared below

The header file for the queue class is declared below. A brief explanation of its methods has already been given

queue.cpp is shown below

A brief explanation follows:

Lines 6-8: front & rear point to the first and last elements of the queue. count gives the number of elements in the queue. maxqueue is the maximum number of elements the queue can have in it.

Lines 18-23: If the number of elements exceeds the maximum allowd size, return an error. Else increment the element counter.

Next we look for the last queue element; rear. If we increment rear by 1 and this value exceeds maxqueue then we start again from the beginning of the queue(recall the example of a 12-hour clock given earlier!). Else if rear < maxqueue we increment it by one and add a new element to our queue.

Similar logic is applied in Queue::serve() except this time we decrease by one instead of incrementing.

A program implementing the above classes is shown below. It’s not formatted perfectly, but it should give the reader a rough idea about how to work with queues.

Conclusion

Hope you find this short C++ queue tutorial useful!

References

Data Structures and Program Design in C++ by Kruse & Ryba