Reverse a Stack utilizing Queue

Given a stack, the duty is to reverse the stack utilizing the queue knowledge construction.

Examples:

Enter: Stack: (Prime to Backside) [10 -> 20 -> 30 -> 40]
Output: Stack: (Prime to Backside) [40 -> 30 -> 20 -> 10]

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

Strategy: The issue may be solved based mostly on the next concept:

The stack follows LIFO order and the queue follows FIFO order. So, if we push all stack parts into queue after which push it again into the stack it will likely be reversed.

Illustration:

Think about Stack: [40 -> 30 -> 20 -> 10]     

Step 1:

• Stack: (Backside to Prime) [40 -> 30 -> 20 -> 10]     
  Queue: (Entrance to Rear) Empty

Step 2:

• Stack: (Backside to Prime) [40 -> 30 -> 20]
  Queue: (Entrance to Rear) 10

Step 3:

• Stack: (Backside to Prime) [40 -> 30]             
  Queue: (Entrance to Rear) [10 -> 20]

Step 4:

• Stack: (Backside to Prime) [40]
  Queue: (Entrance to Rear) [10 -> 20 -> 30]

Step 5:

• Stack: (Backside to Prime) Empty
  Queue: (Entrance to Rear) [10 -> 20 -> 30 -> 40]

Step 6:

• Stack: (Backside to Prime) [10]
  Queue: (Entrance to Rear) [20 -> 30 -> 40]

Step 7:

• Stack: (Backside to Prime) [10 -> 20]
  Queue: (Entrance to Rear) [30 -> 40]

Step 8:

• Stack: (Backside to Prime) [10 -> 20 -> 30]
  Queue: (Entrance to Rear) [40]

Step 9:

• Stack: (Backside to Prime) [10 -> 20 -> 30 -> 40]
  Queue: (Entrance to Rear) Empty

Comply with the steps to unravel the issue:

• Pop Parts one after the other from the stack.
• Enqueue each popped factor into the queue.
• Do it until the stack is empty.
• Then, Dequeue parts one after the other from the queue.
• Push each dequeued factor into the stack.
• Do it until the queue is empty.
• The stack is now reversed.

Under is the implementation for the above method:

After Reverse : (Prime to Backside)
40 30 20 10 

Time Complexity: O(N), As we’re coming out N parts, then solely pushing N parts. N+N operations.
Auxiliary Area: O(N), As we’re utilizing an Further Queue of N Area.

Associated articles: