std::queue C++

The Standard Template Library (STL) provides a queue container that implements a First-In-First-Out (FIFO) data structure. It is similar to a real-life queue where elements are inserted at the back and removed from the front. The STL queue is a wrapper around a container adaptor that can use deque, list, or vector as its underlying container.

To use the queue class, include the <queue> header in your C++ code.

Here’s an explanation of some important functions of the queue class and their time complexities:

push()

• Adds an element to the back (end) of the queue.
• Time Complexity: O(1)

pop()

• Removes the front (first) element from the queue.
• Time Complexity: O(1)

front()

• Accesses the front (first) element of the queue without removing it.
• Time Complexity: O(1)

back()

• Accesses the back (last) element of the queue without removing it.
• Time Complexity: O(1)

empty()

• Checks if the queue is empty.
• Time Complexity: O(1)

size()

• Returns the number of elements in the queue.
• Time Complexity: O(1)

Using Queue in C++

#include <iostream>
#include <queue>

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

    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "Front element: " << q.front() << std::endl; // Output: 10
    std::cout << "Back element: " << q.back() << std::endl;   // Output: 30
    std::cout << "Queue size: " << q.size() << std::endl;     // Output: 3

    q.pop();

    std::cout << "Front element after pop: " << q.front() << std::endl; // Output: 20

    while (!q.empty()) {
        std::cout << q.front() << " "; // Output: 20 30
        q.pop();
    }

    return 0;
}

In this example, we demonstrate the use of the queue class from the STL. We create a queue of integers (std::queue<int>) and perform various operations like pushing elements, accessing front and back elements, checking size, and popping elements.

The queue class is widely used in various algorithms and scenarios, such as Breadth-First Search (BFS), task scheduling, and any situation where data needs to be processed in the order of arrival. It abstracts the complexities of managing the underlying container and provides a simple interface for FIFO operations.

Some additional details:

Queue Initialization

The queue class can be initialized using different constructors, just like other STL containers.

   #include <iostream>
   #include <queue>

   int main() {
       // Initialization using default constructor
       std::queue<int> q1;

       // Initialization using another queue (copy constructor)
       std::queue<int> q2(q1);

       // Initialization using a deque as the underlying container
       std::deque<int> dq = {10, 20, 30};
       std::queue<int, std::deque<int>> q3(dq);

       // Initialization using a list as the underlying container
       std::list<int> lst = {40, 50, 60};
       std::queue<int, std::list<int>> q4(lst);

       return 0;
   }

Swapping Queues

You can swap the contents of two queues of the same type and same underlying container using the swap() function.

   std::queue<int> q1 = {1, 2, 3};
   std::queue<int> q2 = {4, 5, 6};
   q1.swap(q2);

Queue Relational Operators

The queue class supports relational operators (==, !=, <, >, <=, >=), which compare two queues based on their content.

   std::queue<int> q1 = {1, 2, 3};
   std::queue<int> q2 = {1, 2, 3};
   if (q1 == q2) {
       std::cout << "Both queues are equal." << std::endl;
   }

Iterating through the Queue

As the queue container only supports the front and back access, there is no direct way to use iterators to traverse the elements. To access individual elements, you can pop them one by one and process them.

   std::queue<int> q = {10, 20, 30};
   while (!q.empty()) {
       std::cout << q.front() << " ";
       q.pop();
   }

Clearing Queue

To remove all elements from the queue, you can use the queue::empty() function in a loop and pop all elements.

   std::queue<int> q = {1, 2, 3, 4, 5};
   while (!q.empty()) {
       q.pop();
   }

User-Defined Objects in Queue

You can also use user-defined objects in the queue. Ensure that the class has a defined copy constructor and assignment operator for proper behavior.

   class MyClass {
   public:
       int data;
       // Constructor
       MyClass(int data) : data(data) {}
   };

   std::queue<MyClass> q;
   q.push(MyClass(10));

The queue container from the C++ STL is a versatile and powerful tool for implementing queue-like behavior in C++ programs. It abstracts the complexities of handling underlying containers and provides a simple interface for basic queue operations. Whether it’s for BFS, simulations, or any other situation requiring a FIFO data structure, the queue container is a valuable addition to any C++ programmer’s toolkit.