Reverse a Stack using Queue

By Ann Roberts On Dec 14, 2022

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a stack, the task is to reverse the stack using the queue data structure.

Examples:

Input: Stack: (Top to Bottom) [10 -> 20 -> 30 -> 40]
Output: Stack: (Top to Bottom) [40 -> 30 -> 20 -> 10]

Input: Stack: [6 -> 5 -> 4]
Output: Stack: [4 -> 5 -> 6]

Approach: The problem can be solved based on the following idea:

The stack follows LIFO order and the queue follows FIFO order. So, if we push all stack elements into queue and then push it back into the stack it will be reversed.

Illustration:

Consider Stack: [40 -> 30 -> 20 -> 10]

Step 1:

Stack: (Bottom to Top) [40 -> 30 -> 20 -> 10]
Queue: (Front to Rear) Empty

Step 2:

Stack: (Bottom to Top) [40 -> 30 -> 20]
Queue: (Front to Rear) 10

Step 3:

Stack: (Bottom to Top) [40 -> 30]
Queue: (Front to Rear) [10 -> 20]

Step 4:

Stack: (Bottom to Top) [40]
Queue: (Front to Rear) [10 -> 20 -> 30]

Step 5:

Stack: (Bottom to Top) Empty
Queue: (Front to Rear) [10 -> 20 -> 30 -> 40]

Step 6:

Stack: (Bottom to Top) [10]
Queue: (Front to Rear) [20 -> 30 -> 40]

Step 7:

Stack: (Bottom to Top) [10 -> 20]
Queue: (Front to Rear) [30 -> 40]

Step 8:

Stack: (Bottom to Top) [10 -> 20 -> 30]
Queue: (Front to Rear) [40]

Step 9:

Stack: (Bottom to Top) [10 -> 20 -> 30 -> 40]
Queue: (Front to Rear) Empty

Follow the steps to solve the problem:

Pop Elements one by one from the stack.
Enqueue every popped element into the queue.
Do it till the stack is empty.
Then, Dequeue elements one by one from the queue.
Push every dequeued element into the stack.
Do it till the queue is empty.
The stack is now reversed.

Below is the implementation for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void reverse(stack<int>& stk)

{

queue<int> qu;

while (!stk.empty()) {

qu.push(stk.top());

stk.pop();

}

while (!qu.empty()) {

stk.push(qu.front());

qu.pop();

}

int main()

{

stack<int> stk;

stk.push(40);

stk.push(30);

stk.push(20);

stk.push(10);

reverse(stk);

cout << "After Reverse : (Top to Bottom)"

<< "\n";

while (!stk.empty()) {

cout << stk.top() << " ";

stk.pop();

}

cout << "\n";

return 0;

}

Output

After Reverse : (Top to Bottom)
40 30 20 10

Time Complexity: O(N), As we are popping out N elements, then only pushing N elements. N+N operations.
Auxiliary Space: O(N), As we are using an Extra Queue of N Space.

Related articles:

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a stack, the task is to reverse the stack using the queue data structure.

Examples:

Input: Stack: (Top to Bottom) [10 -> 20 -> 30 -> 40]
Output: Stack: (Top to Bottom) [40 -> 30 -> 20 -> 10]

Input: Stack: [6 -> 5 -> 4]
Output: Stack: [4 -> 5 -> 6]

Approach: The problem can be solved based on the following idea:

The stack follows LIFO order and the queue follows FIFO order. So, if we push all stack elements into queue and then push it back into the stack it will be reversed.

Illustration:

Consider Stack: [40 -> 30 -> 20 -> 10]

Step 1:

Stack: (Bottom to Top) [40 -> 30 -> 20 -> 10]
Queue: (Front to Rear) Empty

Step 2:

Stack: (Bottom to Top) [40 -> 30 -> 20]
Queue: (Front to Rear) 10

Step 3:

Stack: (Bottom to Top) [40 -> 30]
Queue: (Front to Rear) [10 -> 20]

Step 4:

Stack: (Bottom to Top) [40]
Queue: (Front to Rear) [10 -> 20 -> 30]

Step 5:

Stack: (Bottom to Top) Empty
Queue: (Front to Rear) [10 -> 20 -> 30 -> 40]

Step 6:

Stack: (Bottom to Top) [10]
Queue: (Front to Rear) [20 -> 30 -> 40]

Step 7:

Stack: (Bottom to Top) [10 -> 20]
Queue: (Front to Rear) [30 -> 40]

Step 8:

Stack: (Bottom to Top) [10 -> 20 -> 30]
Queue: (Front to Rear) [40]

Step 9:

Stack: (Bottom to Top) [10 -> 20 -> 30 -> 40]
Queue: (Front to Rear) Empty

Follow the steps to solve the problem:

Pop Elements one by one from the stack.
Enqueue every popped element into the queue.
Do it till the stack is empty.
Then, Dequeue elements one by one from the queue.
Push every dequeued element into the stack.
Do it till the queue is empty.
The stack is now reversed.

Below is the implementation for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void reverse(stack<int>& stk)

{

queue<int> qu;

while (!stk.empty()) {

qu.push(stk.top());

stk.pop();

}

while (!qu.empty()) {

stk.push(qu.front());

qu.pop();

}

int main()

{

stack<int> stk;

stk.push(40);

stk.push(30);

stk.push(20);

stk.push(10);

reverse(stk);

cout << "After Reverse : (Top to Bottom)"

<< "\n";

while (!stk.empty()) {

cout << stk.top() << " ";

stk.pop();

}

cout << "\n";

return 0;

}

Output

After Reverse : (Top to Bottom)
40 30 20 10

Time Complexity: O(N), As we are popping out N elements, then only pushing N elements. N+N operations.
Auxiliary Space: O(N), As we are using an Extra Queue of N Space.

Related articles:

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.