5.0 Data Structures – Queues

Queues !! A word that we hear every day. Not only we hear that word, but also we do live it. How can a queue then be a data structure that is used in computer programming ?! Let’s See.

In the last post, we have wrapped up talking about lists. We saw how they are very useful manipulating data in memory. In this post, I will follow the same steps I used to present lists. That is, I will talk about Queues Specifications, Implementations and writing a Test Driver.

Queues Specification

– We want to group some items together.
– The order of the items in the data structure is very important. We want the first element we insert to be the first element I can get out of the Queue.
– The queue must provide a way to insert items at the end of the queue and retrieve items from the front of the queue.
– We don’t sort items inside the queue (e.g. alphabetical sorting like lists). We just insert and retrieve.
Example: you are in a shopping market and waiting for your turn to check and pay for items you have picked up. You are standing in a queue. The cashier man serve the first one standing in the queue. After that, the first one takes his items and go away. The second person is now being served by the cashier man, and so on. This approach is called First Come .. First Served. In computer science world, we call the queue data structure a First-In First-Out (FIFO).

First, have a look at the specs written in code.

template <class ItemType>
class Queue{
public:
    Queue(int max);
    bool IsEmpty()const;
    bool IsFull()const;
    void DeQue(ItemType &item);
    void EnQue(ItemType item);
}

Looking at the above functions prototype, we can notice their role from their name. We have a constructor that specifies the maximum number of elements in the queue, two functions that show us the state of the queue and two functions to insert and retrieve from the queue.

Queues Implementation

As we have stated before that we have two approaches to implement any data structure (arrays and pointers), we will present both approaches also for the queues implementation.

— Using Arrays —

The private data members we will have will be as follows.

class Queue{
private:
    int front;
    int rear;
    ItemType *items;
    int maxQue;
}

The front and rear data types maintain the indexes of the first and last elements in the queue respectively. items is the pointer that will point to the array containing queue elements (dynamic allocation). maxQue stores the maximum number of elements the queue can save.
We can see that there no great difference from the way we implemented lists. (Remember that the magic is in the implementation of the above functions prototypes). So let’s see how they are implemented.

Queue<ItemType>::Queue(int max){
    maxQue = max + 1;
    front = maxQue - 1;
    rear = maxQue - 1;
    items = new ItemType[maxQue];
}

In the above constructor, we initialize the private data members. We set the maxQue to max+1, and make the front and rear points to the same index which is maxQue-1. And then, we initialize our array dynamically . Let’s clarify these initializations using numbers.
Suppose that the user instantiates the queue with max = 500. Behind the scene, we initialize the array with 501 elements and the front and rear indexes will both have the value of 500, which is the last element in the array. But why have we initialized it in this way ?!! We will see that when we EnQue a new element we first increase the value of the rear and take the module on maxQue. Details are coming, don’t rush the lines.

bool Queue<ItemType>::IsEmpty()const{
    return (rear == front);
}

To check whether the queue is empty or not, we implement the function IsEmpty(). It simply checks if the rear and front elements have the same values. This means that we retrieved as many items as we inserted.

bool Que<ItemType>::IsFull()const{
    return ((rear + 1) % maxQue == front);
}

How do we know that the queue is full ?! Simply, if the front has points to the first element and rear points to the last element. But this is now the only case (if this, we check front against the value of zero and rear against the value of maxQue). The general case is that front points to an element and rear points to the element just before it in the array (for example: front=100, rear=99).
If you feel confused now, just hold read the following lines and come back here again.

void Queue<ItemType>::EnQue(ItemType item){
    if(IsFull())
        throw FullQueue();
    else{
        rear = (rear + 1) % maxQue;
        items[rear] = item;
    }
}

From the definition of the queue, we insert elements at the end of the queue. So, to insert a new item we increase the rear value by one and take the modulo on maxQue (we will see why take the modulo shortly). Then, we add the item.
To simulate what is happening, let it be the first time we add items. rear=500 from the constructor. We increase it by one and take the modulo on maxQue, that is (500+1)%501 which results in rear=0 and so this is the first element in the array. The second time we add items, we repeat the same steps, increasing the value of rear and take the modulo on maxQue. (0+1)%501 which results in rear=1. We continue inserting in the queue until we have rear=500 which is the last element of the array (remember array size is 501). If we tried to insert a new item, the IsFull() function will return true. This is because (rear+1)%maxQue = 0 = front. front value hasn’t yet been changed. In this case we throw the exception FullQueue (Exception is a run-time error). This exception is defined before the class definition as follows

class FullQueue{};

You can refer to exception handling in C++ for more information. But this is not the case, we can print a warning message instead to indicate that the queue is full.

void Queue<ItemType>::DeQue(ItemType &item){
    if(IsEmpty())
        throw EmptyQueue();
    else{
        front = (front + 1) % maxQue;
        items = items[front];
    }
}

Again, from the definition of the queue, we retrieve elements from the front of it. So, to retrieve the elements we increase the value of front and take the modulo on maxQue. Then we get the value of the item.
Let’s simulate what is happening. Suppose that the queue is filled with some items which we want to retrieve one after the other. The first time front=500from the constructor definition. We increase its value and take the modulo on maxQue, (500+1)%501=0.Now, front=0 which is the first element we have inserted. The second time we retrieve elements, front=0 which results in (0+1)%501=1that is the second element., and so on. At some time, the value of front will be the same as the value of rear, which means that we have retrieved all items we haveinserted. Attempting to retrieve more items will result in exception of EmptyQueue. This is done through the check of the IsEmpty() function. This exception is defined before the class definition as follows

class EmptyQueue{};

Now, go back to the implementation of IsFull() and IsEmpty() functions to understand them well. I have some notes here:
– If you looked carefully at the two functions of EnQue() and DeQue(), you will get the feeling that rear and front are in a race. Each time we insert new item, rear is increased until it reaches a maximum allowed limit. Each time we retrieve an item,  front tries to reach the rear value until they are the same. In this case, the queue is empty.
– Why using the modulo arithmetic ?!
The best way to illustrate that is to suppose that they are not computed. For example: in the EnQue, we let rear=rear+1 only. The problem with this line is when we fill in the whole values of the queue and then retrieves all the values again. rear will have the value of 500. In which case, if we want to add more items (remember that we have just retrieved all items, so it’s supposed that the queue is empty), rear will have a value of 501 after the addition which will fire exception that the index is out of bound of the array. So, we have to use modulo arithmetic to guarantee that both values of rear and front will be in the allowed range of the array indices.

To get the big picture now, download the code file here, and review what we have come up to.
This is how we implemented queues using the array approach. Let’s see implementation using linked nodes.

— Using Linked Nodes —

In the linked nodes approach, we represent the queue as group of nodes in which every one points to its successor. The node is a structure as follows

struct Node{
    ItemType info;
    Node<ItemType>* next;
};

It’s clear that every node holds the data in the info field and point to the next node through the next pointer. The private data members of the Queue class will be simpler than that is used in the approach of using arrays.

class Queue{
private:
    Node<ItemType>* front;
    Node<ItemType>* rear;
};

Simply, the class has two pointers: front that points to the first element in the queue and rear that points to the last element. This implementation is simpler as we just care about the head (to DeQue) and the tail (to EnQue) of any queue.

Queue<ItemType>::Queue(){
    front = NULL;
    rear = NULL;
}

The constructor is straight-forward. It initializes the private members to null. This indicates that the queue contains no element.

bool Queue<ItemType>::IsEmpty()const{
    return (front == NULL);
}

The above function checks whether the queue is empty or not. By logic, the queue is empty when there is no head element. That is,  front is null. The question now is: how do we know that the queue is full ?! In other word, what is the situation that prevent us from adding new elements. In the arrays approach, the array maximum capacity was the main factor the indicates whether we have consumed all empty slots or there still free spaces to insert new items. But in linked nodes, how can we judge on this issue ?! The answer is: a queue will never be full, as we insert new nodes in the memory (heap) without restrictions. So, we can insert as many as we need. The only exception case is when memory allocation fails to allocate a new memory space (in the heap) . This is written in code as follows:

bool Queue<ItemType>::IsFull()const{
    Node<ItemType>* location;
    try{
        location = new Node<ItemType>;
        delete location;
        return false;
    }
    catch(std::bad_alloc exception){
        return true;
    }
}

We try to add a new node (dummy node not to be inserted in the queue). If the operation succeeded, we delete that temporary node and return false (i.e. it’s not full). Otherwise, an exception occurs and we return true (i.e. it’s full).

void Queue<ItemType>::EnQue(ItemType item){
    if(IsFull())
        throw FullQueue();
    else{
        Node<ItemType>* newNode;
        newNode = new Node<ItemType>;
        newNode->info = item;
        newNode->next = NULL;
        if(rear == NULL)
            front = newNode;
        else
            rear->next = newNode;
        rear = newNode;
    }
}

To insert a new node into the queue, we append it to the end of the queue. In the EnQue operation, we have two different cases. The first one is when the queue is empty. If rear points to null, we conclude that the queue is empty. In this case, we make front points to that newly added node (by the definition of the queue) and also make rear points to it (as it’s the only element in the queue). The second case is when the queue is already filled with some elements. In this case, we make the last element (pointed to by rear) points to the new added node. That is, we append the new node to the queue. After that, we make rear points to that new node, which is then the last element. The below figure shows this operation.

void Queue<ItemType>::DeQue(ItemType &item){
    if(IsEmpty())
        throw EmptyQueue();
    else{
        Node<ItemType>* temp;
        temp = front;
        item = front -> info;
        front = front -> next;
        if(front == NULL)
            rear = NULL;
        delete temp;
    }
}

To retrieve elements from the queue, we get them from the front one by one. We first check if the queue is empty (if we eliminate this check, run-time errors occurs). After that, the delete operation starts. The first step is to hold a temporary pointer to that first node (to be deleted). Then, we get the value of the node pointed to by front and makes it points to the successor node. After that, we delete that node, which is now pointed to by temp (not front). We have a special case. If the queue contains one element, there is no successor nodes to the first one. So, when setting front to point to the successor node, it will be null. We make rear also equal to null, to mark the queue as empty (front and rear). The figure shows this operation.

You can download the full linked queue implementation here.

Test Driver

void main(){
    Queue<int> x;

    //EnQue()  function 
    x.EnQue(5);
    x.EnQue(7);
    x.EnQue(2);
    x.EnQue(14);

    //DeQue function
    while(!x.IsEmpty()){
        int temp;
        x.DeQue(temp);
        cout<<temp<<endl;
    }
}

The test driver is straight forward. You can download a more advanced features added to it from here.

Conclusion

A very long post, haa !! :D. By now, we have covered most aspects of the queues data structure. We use queues in applications when we want to insert and retrieve items in a first-in first-out manner. The most common situation a queue is used is in operating systems implementation for multi-tasking. If we initialized many programs to be launched, the operating system pushes these processes in a queue and the first process requested is the first one served by the OS. There are many other techniques used by the OS rather than a queue, but the queue is a data structure used in same cases. There are many other examples regarding queues. Search for them and try to test them!

In the next post, we will discuss Stacks. So, stay tuned!

I’ll be very grateful to receive your feedback in a comment :).

2 thoughts on “5.0 Data Structures – Queues

leave your feedback

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s