Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explored how to reverse a Queue using Stack data structure.
Table of contents:
- Introduction to problem statement
- Algorithm/ Steps
- Demonstration
- Implementation
- Time and Space Complexity
Pre-requisite:
Introduction
Give an algorithm for reversing a queue Q. Only following standard operations are allowed on queue.
enqueue(x) : Add an item x to rear of queue.
dequeue() : Remove an item from front of queue.
empty() : Checks if a queue is empty or not.
Algorithm/ Steps
Steps to reverse a Queue using Stack:
- Enter the all elements in queue
- Then pop all elements into stack from queue
- At last, pop all elements from stack and push it into queue
Demonstration
As you can see in first step there is a queue in which elements are inserted that is 5,4,3,2 and the element 5 is at front,and element 2 is at rare.than in order to reverse the elements fist dequeue each element from queue and push it into the stack till whole queue will be empty than pop each element from the stack and enqueue it into the queue till all stack will be empty.
Implementation
Implementation of our algorithm to reverse a Queue using Stack:
#include<bits/stdc++.h>
using namespace std;
stack<int> s;
void print(queue<int> &q_ueue)
{
while(!q_ueue.empty( ))
{
cout<<q_ueue.front()<<" ";
q_ueue.pop( );
}
}
void reverse(queue<int> &q_ueue)
{
while(!q_ueue.empty())
{
s.push(q_ueue.front());
q_ueue.pop();
}
while(!s.empty())
{
q_ueue.push(s.top());
s.pop();
}
}
int main( )
{
printf("enter the element in your queue to stop insertion press -1\n");
int a;
queue<int> q;
while(a!=-1)
{
cin>>a;
if(a!=-1)
{
q.push(a);
}
}
reverse(q);
print(q);
}
Time and Space Complexity
- Worst case time complexity:
Θ(O(N)) - Average case time complexity:
Θ(O(N)) - Best case time complexity:
Θ(O(N)) - Space complexity:
Θ(O(N))
