YouTipCpp Libs Queue
# C++ Standard Library: ``
The C++ Standard Library provides the `` header, which implements a queue data structure. A queue is a **First-In, First-Out (FIFO)** linear data structure. It allows you to add elements at one end (the back/rear) and remove them from the other end (the front).
In a FIFO structure, the first element added to the queue will be the first one to be removed.
---
## Key Characteristics of a Queue
* **FIFO Rule:** Elements are processed in the exact order they are inserted.
* **Restricted Access:** Elements can only be added to the back and removed from the front.
* **No Random Access:** You cannot access elements in the middle of the queue directly via index (e.g., `q` is not allowed).
---
## Syntax and Declaration
To use the queue container, you must include the `` header file.
```cpp
#include
// Declaration syntax
std::queue q;
```
* `Type`: The data type of the elements to be stored in the queue (e.g., `int`, `double`, `std::string`, or custom classes/structs).
### Underlying Container
By default, `std::queue` is a **container adapter**. It wraps an underlying container (by default, `std::deque`) and exposes a specific set of member functions. You can optionally specify a different underlying container, such as `std::list`:
```cpp
std::queue> custom_q;
```
---
## Core Member Functions
The `std::queue` class provides the following member functions for managing elements:
| Function | Description | Time Complexity |
| :--- | :--- | :--- |
| `push(const value_type& val)` | Inserts a new element at the end (back) of the queue. | $O(1)$ |
| `pop()` | Removes the element at the front of the queue. | $O(1)$ |
| `front()` | Returns a reference to the element at the front of the queue. | $O(1)$ |
| `back()` | Returns a reference to the element at the back of the queue. | $O(1)$ |
| `empty()` | Checks whether the queue is empty. Returns `true` if empty, `false` otherwise. | $O(1)$ |
| `size()` | Returns the number of elements currently in the queue. | $O(1)$ |
| `emplace(Args&&... args)` | Constructs an element in-place at the back of the queue (C++11). | $O(1)$ |
---
## Practical Code Example
The following example demonstrates how to initialize a queue, insert elements, inspect the front and back, and safely pop elements until the queue is empty.
```cpp
#include
#include
int main() {
// Create an integer queue
std::queue q;
// Add elements to the back of the queue
q.push(10);
q.push(20);
q.push(30);
// Print the size of the queue
std::cout << "Queue size: " << q.size() << std::endl;
// Print the front and back elements
std::cout << "Front element: " << q.front() << std::endl;
std::cout << "Back element: " << q.back() << std::endl;
// Remove the front element
q.pop();
std::cout << "After popping, new front element: " << q.front() << std::endl;
// Print the updated size of the queue
std::cout << "Queue size after pop: " << q.size() << std::endl;
std::cout << "\n--- Processing remaining elements ---" << std::endl;
// Loop to empty the queue safely
while (!q.empty()) {
std::cout << "Processing: " << q.front() << std::endl;
q.pop();
}
return 0;
}
```
### Output
```text
Queue size: 3
Front element: 10
Back element: 30
After popping, new front element: 20
Queue size after pop: 2
--- Processing remaining elements ---
Processing: 20
Processing: 30
```
---
## Important Considerations
1. **No Iterators:** Unlike sequential containers like `std::vector` or `std::list`, `std::queue` does not support iterators. You cannot use `std::begin()`, `std::end()`, or range-based `for` loops directly on a queue.
2. **Undefined Behavior on Empty Queues:** Calling `front()`, `back()`, or `pop()` on an empty queue results in undefined behavior. Always check if the queue is not empty using `empty()` before performing these operations:
```cpp
if (!q.empty()) {
int val = q.front();
q.pop();
}
```
3. **Memory Management:** The default underlying container `std::deque` manages memory dynamically. When elements are popped, the memory is managed internally by the container, but it may not immediately release the allocated memory back to the system.