Queue: Container, C++

In C++, the queue container is a part of the Standard Template Library (STL) and provides a way to manage data in a FIFO (First In, First Out) manner. This means the first element added to the queue will be the first one to be removed, making it ideal for scenarios such as scheduling tasks or processing data in a sequential order. In this guide, we will cover all the methods to construct a queue, its various operations like push, pop, front, back, empty, size, and more.

Table of Contents

1. Introduction to Queue in C++
2. Different Ways to Construct a Queue
3. Common Operations on Queue
   • push()
   • pop()
   • front()
   • back()
   • empty()
   • size()
4. Working with Custom Data Types
5. Summary and Best Practices

---

1. Introduction to Queue in C++

In C++, the queue is a container adaptor that is implemented over other underlying containers, such as deque or list. The queue operates based on the FIFO principle, meaning elements are added at the back (rear) and removed from the front.

Key Features:

• Push: Adds an element to the back of the queue.
• Pop: Removes the element from the front of the queue.
• Front: Retrieves the element at the front of the queue without removing it.
• Back: Retrieves the element at the back of the queue.
• Size: Returns the number of elements in the queue.
• Empty: Checks if the queue is empty.

---

2. Different Ways to Construct a Queue

The queue container in C++ can be constructed in various ways, depending on the required behavior and the underlying container.

2.1 Default Constructor

The simplest way to construct a queue is by using the default constructor, which creates an empty queue with deque as the underlying container by default.

queue<int> q;

In this example, q is an empty queue of integers.

2.2 Constructor with an Initial Container

You can initialize a queue by directly passing an existing container (like deque or list) to the queue constructor. It is important to note that the queue container cannot be initialized using iterators (such as .begin() and .end()).

deque<int> d = {1, 2, 3, 4};
queue<int> q(d); // Initialize queue with a deque

Here, the queue q is initialized directly with the elements from the deque d. The queue container can only be initialized using deque or list as the underlying container.

2.3 Queue with Custom Container

If you want to specify a different underlying container, you can explicitly provide it as a template parameter. The default underlying container for queue is deque, but you can change it to list or any other supported container type.

queue<int, list<int>> q;

In this case, a list<int> is used as the underlying container instead of deque. This can be useful if you want the specific properties of a list, such as better performance for certain types of insertions and deletions.

---

3. Common Operations on Queue

3.1 push()

The push() function is used to add an element to the back of the queue.

Syntax:

q.push(element);

Example:

queue<int> q;
q.push(10);
q.push(20);
q.push(30);

After this code, the queue q will contain: 10 at the front, 20 in the middle, and 30 at the back.

3.2 pop()

The pop() function removes the element from the front of the queue.

Syntax:

q.pop();

Example:

queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.pop(); // Removes 10

After calling pop(), the front of the queue will be 20.

3.3 front()

The front() function retrieves the front element of the queue without removing it.

Syntax:

element = q.front();

Example:

queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << "Front element: " << q.front() << endl; // Outputs 10

3.4 back()

The back() function retrieves the back element of the queue without removing it.

Syntax:

element = q.back();

Example:

queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << "Back element: " << q.back() << endl; // Outputs 30

3.5 empty()

The empty() function checks whether the queue is empty.

Syntax:

bool isEmpty = q.empty();

Example:

queue<int> q;
cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl; // Outputs Yes
q.push(10);
cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl; // Outputs No

3.6 size()

The size() function returns the number of elements in the queue.

Syntax:

size_t queueSize = q.size();

Example:

queue<int> q;
q.push(10);
q.push(20);
cout << "Queue size: " << q.size() << endl; // Outputs 2

---

4. Working with Custom Data Types

Just like stack, the queue container can also store custom data types. Let’s explore how to use queues with user-defined objects.

Example: Queue with Custom Object

#include <iostream>
#include <queue>
using namespace std;

class Person {
public:
    string name;
    int age;

    Person(string n, int a) : name(n), age(a) {}

    void display() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};

int main() {
    queue<Person> personQueue;
    personQueue.push(Person("Alice", 25));
    personQueue.push(Person("Bob", 30));

    // Display front person
    personQueue.front().display();  // Outputs: Name: Alice, Age: 25
    personQueue.pop();
    personQueue.front().display();  // Outputs: Name: Bob, Age: 30

    return 0;
}

In this example, we define a Person class and push Person objects into the queue. We use the front() method to retrieve the front object and pop() to remove it from the queue.

---

5. Summary and Best Practices

• Queue Construction: You can create a queue using the default constructor, by passing an existing container, or by specifying a custom underlying container.
• Operations: Use push() to add elements, pop() to remove the front element, front() to peek at the front element, back() to get the last element, empty() to check if the queue is empty, and size() to get the number of elements.
• Custom Types: You can store objects of custom classes in a queue just like basic data types.

Best Practices:

1. Check for empty before popping: Always check if the queue is empty using empty() before calling pop(). Popping from an empty queue is undefined behavior.
2. Choosing the Right Container: If you need frequent insertion and deletion at both ends, consider using deque as the underlying container. For simpler use cases, list can also work well.
3. No direct iteration: Just like stack, queue does not allow direct iteration. If you need to access all elements, you must remove them one by one (e.g., using pop()).

---

The queue container in C++ is a powerful and easy-to-use tool for managing data in a FIFO manner. It's particularly useful for scheduling, buffering, and handling tasks in a sequential manner. By understanding the various ways to construct and manipulate queues, you can leverage its full potential in your C++ programs.