Queue in C++ Standard Template Library (STL)
Last Updated :
22 Apr, 2023
Queues are a type of container adaptors that operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. Queues use an encapsulated object of deque or list (sequential container class) as its underlying container, providing a specific set of member functions to access its elements.
Following is an example to demonstrate the queue and its various methods.
CPP
#include <iostream>
#include <queue>
using namespace std;
void showq(queue<int> gq)
{
queue<int> g = gq;
while (!g.empty()) {
cout << '\t' << g.front();
g.pop();
}
cout << '\n';
}
int main()
{
queue<int> gquiz;
gquiz.push(10);
gquiz.push(20);
gquiz.push(30);
cout << "The queue gquiz is : ";
showq(gquiz);
cout << "\ngquiz.size() : " << gquiz.size();
cout << "\ngquiz.front() : " << gquiz.front();
cout << "\ngquiz.back() : " << gquiz.back();
cout << "\ngquiz.pop() : ";
gquiz.pop();
showq(gquiz);
return 0;
}
|
Output
The queue gquiz is : 10 20 30
gquiz.size() : 3
gquiz.front() : 10
gquiz.back() : 30
gquiz.pop() : 20 30
Methods of Queue are:
The time complexity and definition of the following functions are as follows:
| queue::empty() |
O(1) |
| queue::size() |
O(1) |
| queue::emplace() |
O(1) |
| queue::front() |
O(1) |
| queue::back() |
O(1) |
| queue::push(g) |
O(1) |
| queue::pop() |
O(1) |
| Method |
Definition |
| queue::empty() |
Returns whether the queue is empty. It return true if the queue is empty otherwise returns false. |
| queue::size() |
Returns the size of the queue. |
| queue::swap() |
Exchange the contents of two queues but the queues must be of the same data type, although sizes may differ. |
| queue::emplace() |
Insert a new element into the queue container, the new element is added to the end of the queue. |
| queue::front() |
Returns a reference to the first element of the queue. |
| queue::back() |
Returns a reference to the last element of the queue. |
| queue::push(g) |
Adds the element ‘g’ at the end of the queue. |
| queue::pop() |
Deletes the first element of the queue. |
C++ program for some more methods
C++
#include <iostream>
#include <queue>
using namespace std;
void print_queue(queue<int> q)
{
queue<int> temp = q;
while (!temp.empty()) {
cout << temp.front()<<" ";
temp.pop();
}
cout << '\n';
}
int main()
{
queue<int> q1;
q1.push(1);
q1.push(2);
q1.push(3);
cout << "The first queue is : ";
print_queue(q1);
queue<int> q2;
q2.push(4);
q2.push(5);
q2.push(6);
cout << "The second queue is : ";
print_queue(q2);
q1.swap(q2);
cout << "After swapping, the first queue is : ";
print_queue(q1);
cout << "After swapping the second queue is : ";
print_queue(q2);
cout<<q1.empty();
return 0;
}
|
Output
The first queue is : 1 2 3
The second queue is : 4 5 6
After swapping, the first queue is : 4 5 6
After swapping the second queue is : 1 2 3
0
The time and space complexities of the operations in this code are as follows:
print_queue function:
Time complexity: O(n), where n is the number of elements in the queue.
Space complexity: O(n), where n is the number of elements in the queue.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Time complexity: O(1) for each push operation.
Space complexity: O(n), where n is the total number of elements in both queues.
q1.swap(q2):
Time complexity: O(1) for each swap operation.
Space complexity: O(1), as this operation only swaps the internal pointers of the two queues.
q1.empty():
Time complexity: O(1), as this operation simply checks if the queue is empty.
Space complexity: O(1), as no extra space is used for this operation.
Overall, the time and space complexities of this code are reasonable and efficient for typical use cases.
Recent Articles on C++ Queue
Please Login to comment...