Program to Reverse Stack Using Queue

In this post, we will discuss how to reverse a stack using queue.

Stack follows LIFO (Last In First Out) and Queue follows FIFO ( First In First Out ) principle. First, we pop all elements of the stack and push them to the queue. The top element of the stack appears at the front of the queue and so on. After that, we pop all elements of the queue and push them back to the stack. Queue pop elements from the front. Thus, the elements in the stack appear in reverse order.

---

---

Steps

1. Initialize an empty queue.
2. Pop each element of stack and push it to the queue.
3. Pop each element of queue and push it back to the stack.

Program

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

void ReverseStackUsingQueue(stack<int>& s) {
	queue<int> q;
	// push all elements of stack to queue
	while (!s.empty()) {
		q.push(s.top());
		s.pop();
	}
	// push all elements of the queue back to stack
	while (!q.empty()) {
		s.push(q.front());
		q.pop();
	}
}

int main()
{
	int n;
	stack<int> s;
	cout << "Enter number of elements you want to Push to stack: ";
	cin >> n;

	for (int i = 0; i < n; ++i) {
		int x;
		cout << "Enter a value: ";
		cin >> x;
		s.push(x);
	}
	cout << "Element on top of the stack: " << s.top() << endl;
	ReverseStackUsingQueue(s);
	cout << "Element on top of the stack after reverse: " << s.top() << endl;
}

Output

Enter number of elements you want to Push to stack: 4
Enter a value: 1
Enter a value: 2
Enter a value: 3
Enter a value: 4
Element on top of the stack: 4
Element on top of the stack after reverse: 1

Time Complexity

Time to pop elements from the stack and push them into the queue = O(N)

Time to pop elements from the queue and push them back into the stack = O(N)

Time Complexity of algorithm = O(N) + O(N) = O(N)

Read
Merge Two Sorted Arrays using Recursion
Print Diamond Pattern Using recursion
Reverse String without strrev() in C
Find all subset of an array ( recursive and iterative approach )