Queue in C++ (STL)

In this Lecture, we will learn about Queue Container in C++ Standard Template Library (STL).

What is a Queue?

A queue is a data structure that adheres to the First-In-First-Out (FIFO) principle. This means that the element added first will be the first one to be removed.

For instance, suppose we have a queue and we add three elements: first is ‘A’, second is ‘B’, and third is ‘C’. The queue will be represented as follows:

The element ‘A’ is at the front of the queue because it was added first. Following that, ‘B’ was added, and lastly, ‘C’ was added, placing ‘C’ at the back of the queue. If you wish to remove an element from this queue, the removal will take place from the front. This removal operation is termed ‘pop’. Thus, if we perform a ‘pop()’ operation, ‘A’ will be removed, leaving ‘B’ at the front and ‘C’ at the back. After removing ‘A’ from the front of queue, it will look like this,

If you want to insert a new element into the queue, it will be added to the back. This addition operation is known as ‘push’. So, if you push an element, say ‘D’, into the queue, the queue will now contain ‘B’, ‘C’, and ‘D’ with ‘B’ at the front and ‘D’ at the back. Queue will look like this now,

If another ‘pop’ operation is performed, ‘B’ will be removed, leaving ‘C’ at the front.

Queue will look like this now,

Queue Container in Standard Template Library

C++ offers a class called queue to provide queue functionality to developers. To utilize the queue class, one must first include the ‘queue’ header file i.e.

#include <queue>

Here’s the polished version of your text:

Syntax to Declare an Queue

std::queue<data_type> queueObj;

It will create a queue object queueObj. The data_type specifies the type of elements that the queue object queueObj can store.

For instance:

To create a queue of integers, we use ‘int’ as the template parameter:

std::queue<int> queueOfNumbers;

Similarly, to create a queue of strings, we use ‘string’ as the template parameter:

std::queue<std::string> queueOfMessages;

How to Add Elements into the Queue?

To insert elements into the queue, the C++ ‘queue’ class provides a member function named ‘push()’. This function adds elements to the end of the queue.

For example, to create a queue of integers and insert three elements (11, 12, and 30), the queue will look as follows after these insertions:

// Create a queue of numbers
std::queue<int> queueObj;

// Add number 11 at the end of queue
queueObj.push(11);

// Add number 12 at the end of queue
queueObj.push(12);

// Add number 30 at the end of queue
queueObj.push(30);

Here, the front of the queue has the element ’11’, while the end of the queue contains the element ’30’, as ’11’ was added first and ’30’ last.
Queue will look like this,

Now, we have added three elements in the queue. Let’s see how to count number of elements in queue.

How to Get the Size of a Queue?

The ‘queue’ class in C++ offers a ‘size()’ function. It returns the count of elements currently stored in the queue. For instance, after inserting five elements into a queue:

#include <iostream>
#include <queue>

int main() 
{
    // Create a queue of numbers
    std::queue<int> queueObj;

    // Add number 11, 12, and 30 at the end of queue
    queueObj.push(11);
    queueObj.push(12);
    queueObj.push(30);

    std::cout<< "Number of elements in Queue: "
             << queueObj.size()
             << std::endl;

    return 0;
}

Output:

Number of elements in Queue: 3

How to Check if a Queue is Empty?

To determine whether a queue is empty, the C++ ‘queue’ class offers a member function named ’empty()’. This function returns ‘true’ if the queue has no element and ‘false’ otherwise.

For instance:

#include <iostream>
#include <queue>

int main()
{
    // Create a queue of numbers
    std::queue<int> queueObj;

    if (queueObj.empty())
    {
        std::cout << "The queue is empty." << std::endl;
    }
    else
    {
        std::cout << "The queue is not empty." << std::endl;
    }

    return 0;
}

In this example, since we haven’t inserted any elements into queueObj, the output will be:

The queue is empty.

How to Access Elements in a Queue?

In C++, the queue does not support random access. Instead, it provides two specific functions to access the front and back elements of the queue. Let’s explore these functions:

Accessing the Element from front:

The queue class has a front() function that returns a reference to the foremost element without removing it.

For example:

#include <iostream>
#include <queue>

int main() 
{
    // Create a queue of numbers
    std::queue<int> queueObj;

    // Add number 11, 12, and 30 at the end of queue
    queueObj.push(11);
    queueObj.push(12);
    queueObj.push(30);

    // Get element at the front of queue
    int elem = queueObj.front();

    std::cout<< "Element at Front: "
             << elem
             << std::endl;

    return 0;
}

Output:

Element at Front: 11

In the above code, after adding three elements, when we call queueObj.front(), it returns the element ’11’ since that was the first element added to the queue.

Accessing the Element from back of Queue:

To get a reference to the last element in the queue, the queue class provides a function called back().

For instance:

#include <iostream>
#include <queue>

int main() 
{
    // Create a queue of numbers
    std::queue<int> queueObj;

    // Add number 11, 12, and 30 at the end of queue
    queueObj.push(11);
    queueObj.push(12);
    queueObj.push(30);

    // Get element at the back of queue
    int elem = queueObj.back();

    std::cout<< "Element at Back: "
             << elem
             << std::endl;

    return 0;
}

Output:

Element at Front: 30

In this example, after pushing three integers, calling queueObj.back() will return ’30’ — the most recent element added to the queue.

How to Remove Elements from a Queue?

The queue in C++ operates on a First In, First Out (FIFO) principle, which means that the element added first will be the one removed first.

The queue class in C++ provides a pop() function, which is responsible for removing the element from the front of the queue. Crucially, this function does not return the removed element; it just performs the removal.

Let’s demonstrate this with an example:

#include <iostream>
#include <queue>

int main() 
{
    // Create a queue of numbers
    std::queue<int> queueObj;

    // Add number 11, 12, and 30 at the end of queue
    queueObj.push(11);
    queueObj.push(12);
    queueObj.push(30);

    int elem = queueObj.front();

    std::cout<< "Element at Front: "
             << elem
             << std::endl;

    // Remove element fron the front of queue
    queueObj.pop();


    elem = queueObj.front();

    std::cout<< "Element at Front: "
             << elem
             << std::endl;

    return 0;
}

Output:

Element at Front: 11
Element at Front: 12

We initialy added 3 elements into the queue i.e. 11, 12 and 13. The value 11 was at the front of queue. Then we removed the value from the front of queue using pop() function. After that value 12 was at the front of queue.

An important aspect to remember is that the pop() function doesn’t return the removed element. If you wish to access the front element before removing it, you should use the front() function.

How to Iterate Over All Elements of a Queue?

Unlike certain other containers in C++, a queue does not support random access. Therefore, to iterate over all its elements, a sequential approach is used. The simplest way to do this is by utilizing a loop that continues until the queue is empty. During each iteration, we access the front element, process it, and then pop it off.

Example:

#include <iostream>
#include <queue>

int main()
{
    // Create a queue of numbers
    std::queue<int> queueObj;

    // Add number 11, 12, and 30 at the end of queue
    queueObj.push(11);
    queueObj.push(12);
    queueObj.push(30);

    while (!queueObj.empty())
    {
        // Access the front element
        int elem = queueObj.front();

        // Process the element (e.g., print it)
        std::cout << elem << " ";

        // Remove the front element
        queueObj.pop();
    }
    return 0;
}

Output:

11 12 30

This method allows for sequential access to every item in the queue. Remember that each pop operation reduces the size of the queue by one, ensuring the loop won’t run indefinitely.

Important Considerations:

1. If a queue is empty and you attempt to invoke front(), back(), or pop(), it can lead to undefined behaviour. Hence, it’s crucial to first ensure that the queue isn’t empty before making such calls.
2. Once the above loop completes, the queue will be empty, so all its elements will have been removed.

Summary

In this article, we’ve delved into the functionality of the STL queue container adapter. It’s an essential tool for handling data in a first-in-first-out manner. By understanding its primary operations and potential pitfalls, we can use the queue effectively in various programming scenarios.