Write an algorithm which reverses the order of elements of stack using one additional stack and some additional variables?


Q.) Write an algorithm which reverses the order of elements of stack using one additional stack and some additional variables?

Subject: Data Structures

Sure, let's write an algorithm to reverse the order of elements in a stack using an additional stack and some additional variables.

The stack is a Last-In-First-Out (LIFO) data structure, meaning that the last element added to the stack will be the first one to be removed. To reverse a stack, we need to make the bottom element to be on top, but we can only remove the top element of the stack. So, we need to use an additional stack to temporarily hold the popped elements.

Here is the algorithm:

  1. Initialize an empty stack, let's call it tempStack.
  2. While the original stack is not empty, repeat steps 3 and 4.
  3. Pop an element from the original stack, let's call it temp.
  4. Push temp into the tempStack.
  5. tempStack now contains the elements of the original stack but in reversed order.

Let's illustrate this algorithm with an example:

Suppose we have a stack originalStack with elements [1, 2, 3, 4, 5] where 5 is at the top.

Step originalStack tempStack temp
1 1, 2, 3, 4, 5
2 1, 2, 3, 4 5 5
2 1, 2, 3 5, 4 4
2 1, 2 5, 4, 3 3
2 1 5, 4, 3, 2 2
2 5, 4, 3, 2, 1 1

At the end of the algorithm, tempStack contains the elements of originalStack but in reversed order.

This algorithm has a time complexity of O(n) because each element in the original stack is popped and pushed to the tempStack once. The space complexity is also O(n) because an additional stack is used to store n elements.