std::queue

Standard Template Library (STL) provides a versatile set of container classes that simplify data manipulation. One of the fundamental containers is std::queue, which implements a First-In-First-Out (FIFO) data structure.

In this blog, we will explore std::queue in detail, including its important functions, time complexity, and space complexity.

What is a Queue?

A queue is a linear data structure that follows the FIFO principle.

In a queue, elements are inserted at the back and removed from the front.

It is analogous to a real-life queue, like customers waiting in line to be served. The first customer who joined the queue is the first to be served.

std::queue Class in C++

To work with queues in C++, you can use the std::queue class from the <queue> header. The std::queue class template has the following syntax:

#include <queue>

std::queue<T, Container> myQueue;

Here, T is the type of elements to be stored in the queue, and Container is the underlying container that holds the elements. By default, std::deque<T> is used as the container, but you can choose other containers like std::vector<T> or std::list<T>.

Functions in std::queue

Let’s create a std::queue and explore its important functions with code examples:

push():

Inserts a new element at the back of the queue.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    return 0;
}

pop():

Removes the front element from the queue.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    myQueue.pop();

    return 0;
}

front():

Accesses the front element of the queue (without removing it).

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    std::cout << "Front element: " << myQueue.front() << std::endl;

    return 0;
}

back():

Accesses the back element of the queue (without removing it).

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    std::cout << "Back element: " << myQueue.back() << std::endl;

    return 0;
}

empty():

Checks if the queue is empty.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    if (myQueue.empty()) {
        std::cout << "Queue is empty." << std::endl;
    } else {
        std::cout << "Queue is not empty." << std::endl;
    }

    return 0;
}

size():

Returns the number of elements in the queue.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    std::cout << "Number of elements in the queue: " << myQueue.size() << std::endl;

    return 0;
}

Iterating through the queue:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    while (!myQueue.empty()) {
        std::cout << "Front element: " << myQueue.front() << std::endl;
        myQueue.pop();
    }

    return 0;
}

Time Complexity and Space Complexity

The time complexity of the essential queue operations is as follows:

• push(): O(1)
• pop(): O(1)
• front(): O(1)
• back(): O(1)
• empty(): O(1)
• size(): O(1)

The space complexity of a queue is the space required to store its elements. For a std::queue using std::deque as the underlying container, the space complexity is O(N), where N is the number of elements in the queue.

std::queue is a useful container in C++ that allows easy implementation of the FIFO concept. It offers essential operations for insertion, deletion, and accessing elements at both ends. Understanding the functions and their time complexity helps to optimize your code efficiently. Whether it’s managing tasks in an operating system or implementing a breadth-first search algorithm, std::queue plays a crucial role in various applications.