C++ Queue

In C++, Queues serve as essential data structures following the first-in-first-out (FIFO) principle. The Standard Template Library (STL) in C++ provides a queue class as part of its pre-built elements, improving the efficiency of queue operations.

A queue represents a linear data structure that operates on a first-in, first-out mechanism by adding elements at the rear and removing them from the front. The behavior of queues is akin to a line at a ticket counter, where patrons are served in the sequence they joined.

Queues play a crucial role in programming as they are essential for managing task scheduling, emulating services based on lines, and conducting traversals in trees following the level-order approach.

Operations of the Queue

Several operations of the queue in C++ are as follows:

• ✅ Enqueue: It is used to insert an element at the end of the queue.
• ✅ Dequeue: it is used to remove an element from the front end of the queue.
• ✅ Front: It returns the first element of the queue.
• ✅ Rear: It returns the last element of the queue.

Syntax

It has the following syntax:

template<class Obj, class Container = deque<Obj> > class queue;

In this particular structure,

• ✅ Obj: Denotes the category of the element within the queue.
• ✅ Container: Represents the category of the container object.

Example of Queue

Let's consider an example to demonstrate the concept of Queues in C++.

Example

#include <iostream>

#include <queue>   // Required for queue

using namespace std;  //using standard namespace

int main() {  //Main Function

    queue<int> q;  // Declare a queue of integers

    q.push(25);    // Add element

    q.push(37);

    q.push(41);

    cout << "The Front element of the Queue is: " << q.front() << endl;  // 10

    cout << "The Rear element of the Queue is: " << q.back() << endl;    // 30

    q.pop();  // Remove front element from queue

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

    return 0;

}

Output:

The Front element of the Queue is: 25

The Rear element of the Queue is: 41

The Front element after pop: 37

Explanation

In this instance, we showcase fundamental queue functions employing the STL queue container. We insert three integers into the queue, exhibit the first and last elements, eliminate the initial element with pop, and then exhibit the revised initial element. Following that, the queue adheres to the FIFO concept.

Key Characteristics of Queues:

Several attributes of Queues in C++ include:

• ✅ First In First Out Principle: Queues follow the FIFO principle, ensuring elements are processed based on their order of arrival.
• ✅ Flexible Structure: The queue's structure supports efficient addition and removal operations that occur in constant time.

These systems play an active role in job scheduling, customer service management, and enhancing the efficiency of data buffering.

Declaration and Initialization of Queues in C++

Queue items are initialized by employing the push method to add elements individually following declaration. In the C++ programming language, there are multiple methods available to declare and set up a queue.

Syntax

It has the following syntax:

#include <queue>

std::queue<datatype> queue_name; // Declaration

• ✅ datatype: The type of elements the queue will store (e.g., int, string, float).
• ✅ queue_name: It represents the identifier for the queue.

Example to Declare and Initialize the Queue

Let's consider a scenario to demonstrate the process of declaring and initializing a queue in the C++ programming language.

Example

#include <iostream>

#include <queue>

using namespace std;  //using standard namespace

int main() {  //Main Function

    // Declaration of a queue of integers

    queue<int> q;

    // Initialization (inserting elements into the queue)

    q.push(10);

    q.push(20);

    q.push(30);

    // Accessing front and back elements

    cout << "Front: " << q.front() << endl;

    cout << "Back: " << q.back() << endl;

    return 0;

}

Output:

Front: 10

Back: 30

Explanation

In this instance, we showcase the application of the STL queue data structure. Initially, we define a queue containing integer values and add three elements utilizing the push method. Subsequently, the front operation accesses the initial inserted element, whereas the back operation fetches the latest addition.

Member Types

Listed here are the various types of queue members along with brief explanations for each.

Functions

By leveraging functions, an object or variable can be manipulated within the realm of programming. Queues offer a wide array of functions that are available for utilization or integration into programs. The following is a compilation of these functions:

Example to Perform Basic Queue Function

Let's consider a straightforward program to demonstrate the application of fundamental queue operations in C++.

Example

#include <iostream>  

#include <queue>  

using namespace std;   //using standard namespace

void showsg(queue <int> sg)  

{  

    queue <int> ss = sg;  

    while (!ss.empty())  

    {  

        cout << '\t' << ss.front();  

        ss.pop();  

    }  

    cout << '\n';  

}    

int main()  //Main Function

{  

    queue <int> fquiz;  

    fquiz.push(10);  

    fquiz.push(20);  

    fquiz.push(30);   

    cout << "The queue fquiz is : ";  

    showsg(fquiz);    

    cout << "\nfquiz.size() : " << fquiz.size();  

    cout << "\nfquiz.front() : " << fquiz.front();  

    cout << "\nfquiz.back() : " << fquiz.back();    

    cout << "\nfquiz.pop() : ";  

    fquiz.pop();  

    showsg(fquiz); 

    return 0;  

}

Output:

The queue fquiz is : 10 20 30

fquiz.size() : 3

fquiz.front() : 10

fquiz.back() : 30

fquiz.pop() : 20 30

Explanation

In this illustration, we showcase the utilization of the queue container along with its methods like push, pop, front, back, and size. Initially, it defines a supporting function named showsg to exhibit the queue's elements. Following that, the script inserts elements into the queue, showcases them, indicates its size, front and back elements, and subsequently eliminates the front element by employing the pop function.

Basic Operations on Queue

In C++, various operations can be executed on a Queue. Some of these include:

1) Insertion (push)

In C++, the addition operation appends the new item after the existing final entry in a queue setup. This addition procedure doesn't alter items positioned at the queue's front. The act of adding elements in a queue is commonly referred to as Enqueue. Multiple items can be sequentially appended to the queue.

Syntax

It has the following syntax:

queue_name.push(value);

C++ Example for Inserting Element in Queue

Let's examine the code example showcasing the process of adding elements to a Queue data structure.

Example

#include <iostream>

#include <queue>

using namespace std;  //using standard namespace

int main() {  //Main Function

    queue<int> q;

    q.push(10);

    q.push(20);

    q.push(30);

    cout << "Queue after insertion: ";

    cout << q.front() << " <- " << q.back() << endl;

    return 0;

}

Output:

Queue after insertion: 10 <- 30

Explanation

In this instance, the push method inserts items at the end of the collection. For example, a queue with elements 10 <- 20 <- 30, the front function displays the initial element (10), while back reveals the final element (30).

2) Deletion (pop)

The initial element in the queue becomes the primary item to be dequeued in this process. It adheres to the First-In-First-Out principle. Each operation involves processing and dequeuing one element using the pop method.

Removing an element from a queue does not return the removed value automatically. Users need to first access the front element using the front function before dequeuing. The action of removing elements from a queue is commonly referred to as dequeuing.

Syntax

It has the following syntax:

queue_name.pop();

Example for Deleting the Elements

Let's examine the code snippet showcasing the process of removing elements from a Queue.

Example

#include <iostream>

#include <queue>

using namespace std;

int main() {

    queue<int> q;

    q.push(10);

    q.push(20);

    q.push(30);

    cout << "Before pop, front = " << q.front() << endl;

    q.pop(); // Removes 10

    cout << "After pop, new front = " << q.front() << endl;

    return 0;

}

Output:

Before pop, front = 10

After pop, new front = 20

Explanation

In this instance, the pop method eliminates the initial element located at the front. Subsequent to the removal of 10, the succeeding element (20) transitions to the new front position.

3) Access Front Element (front)

This function allows retrieval of the element at the front of the queue that is scheduled for removal next.

Syntax

It has the following syntax:

queue_name.front();

C++ Example to Access Front Element

Let's examine the code snippet that illustrates how to retrieve the front elements in a Queue data structure.

Example

#include <iostream>

#include <queue>

using namespace std;  //using standard namespace

int main() {  //Main Function

    queue<string> q;

    q.push("Alice");

    q.push("Bob");

    cout << "Front of the queue: " << q.front() << endl;

    return 0;

}

Output:

Front of the queue: Alice

Explanation

In this instance, the front method displays the initial inserted element.

4) Access Rear Element (back)

The method allows retrieval of a reference to the most recently added item in the queue.

Syntax

It has the following syntax:

queue_name.back();

Let's examine the code snippet that illustrates how to retrieve elements from the rear of a Queue.

Example

#include <iostream>

#include <queue>

using namespace std;  //using standard namespace

int main() {  //Main Function

    queue<string> q;

    q.push("Alice");

    q.push("Bob");

    cout << "Back of the queue: " << q.back() << endl;

    return 0;

}

Output:

Back of the queue: Bob

Explanation:

In this instance, the back method displays the element that was most recently added.

5) Checking Size (size)

The function provides the count of elements within the queue container, indicating the quantity of items held in the queue.

Syntax

It has the following syntax:

queue_name.size();

C++ Example to Check the Size

Let's examine the code snippet to illustrate how to verify the size of elements in a Queue.

Example

#include <iostream>

#include <queue>

using namespace std;

int main() {

    queue<int> q;

    q.push(5);

    q.push(15);

    q.push(25);

    cout << "Queue size: " << q.size() << endl;

    return 0;

}

Output:

Queue size: 3

Explanation

In this instance, the size method calculates the quantity of elements existing in the queue.

6) Empty a Queue

The function is implemented to check if a queue is empty. It will return true if the queue has no elements, and false for any other scenario.

Syntax

It has the following syntax:

queue_name.empty();

C++ Example to Empty function in a Queue

Let's examine the code snippet illustrating the process of dequeuing elements in a Queue.

Example

#include <iostream>

#include <queue>

using namespace std;  //using standard namespace

int main() {  //Main Function

    queue<int> q;

    if (q.empty())

        cout << "Queue is empty" << endl;

    q.push(100);

    if (!q.empty())

        cout << "Queue is not empty" << endl;

    return 0;

}

Output:

Queue is empty

Queue is not empty

Explanation

In this instance, the empty method will yield true if the queue contains no elements.

7) Traversing a Queue

To showcase all elements in a queue from initial to final, a traversal procedure is necessary. The printing of queue elements is accomplished by iterating through them using a loop, in conjunction with front and pop functions. This approach is essential as std::queue lacks support for iterators.

The queue becomes devoid of elements once the traversal is complete as all items are deleted. To retain the original queue, a duplicate can be created in a separate temporary queue, which can then be utilized for the traversal process.

C++ Example to Traverse a Queue

Let's examine the code to showcase how to iterate through elements in a Queue data structure.

Example

#include <iostream>

#include <queue>

using namespace std;

int main() {

    queue<int> q;

    q.push(1);

    q.push(2);

    q.push(3);

    cout << "Queue elements: ";

    while (!q.empty()) {

        cout << q.front() << " ";

        q.pop();  // removes after displaying

    }

    return 0;

}

Output:

Queue elements: 1 2 3

Explanation

In this instance, we display the front element and execute pop repeatedly. This process results in the queue being emptied by the conclusion of the traversal.

Time Complexity

The following table displays the time complexity of various operations of the Queue data structure in C++.

Conclusion:

In summary, queues in C++ function as crucial data structures that enforce FIFO behavior for handling commands based on their order of arrival. By utilizing the queue container within the C++ Standard Template Library (STL), programmers gain streamlined functionality for adding, removing, and observing elements in the queue.

C++ Queue MCQs

1) What is the best description of a queue in C++ STL?

• ✅ A LIFO (Last In First Out) data structure
• ✅ A container that stores elements in a key-value pair
• ✅ A FIFO (first in First out) data structure
• ✅ A dynamic array container

2) Which of the following statements about STD::queue is true?

• ✅ Elements can be randomly accessed using indices
• ✅ Queue allows insertion and deletion at both ends
• ✅ Elements are inserted from the front and removed from end
• ✅ Elements are inserted from behind and deleted from the front

Elements are added from the rear and removed from the front.

3) What does the empty function of std::queue return?

• ✅ Number of empty slots in the queue
• ✅ Last element in the queue
• ✅ True if there are elements in the queue
• ✅ True if there is no element in the queue

4) Which of the following is NOT true about std::queue?

• ✅ It is a container adapter
• ✅ It supports random access to elements
• ✅ It only allows insertion on the back
• ✅ It is defined in the header

5) Which of the following best describes the internal structure of std::queue?

• ✅ A container adapter that uses another container, such as deque or list
• ✅ A stack with reversed behavior
• ✅ A dynamic array with front and rear pointers
• ✅ A priority-based container

a) A container adapter that utilizes a different container like Deque or List