Reversing a Stack

Reversing a Stack

Introduction 

Reversing a stack is one of the most basic coding questions in stacks. In this blog, we are going to discuss the various methods to reverse the stack. Let’s get started.

Problem Statement for Reversing a Stack:

Write a program to insert elements to the stack and display the reversed stack.

Problem Statement

Stack

Stack is a linear data structure similar to arrays and linked lists that allow us to store and retrieve data sequentially. In general, insertion operation is called “push,” and deletion operation is called “pop.” They are useful when dynamic addition and deletion of elements are required.

 Push Operation
 Pop Operation

At any given time, one can only access the top element of a stack. Due to this reason, it is a LIFO (Last In First Out) data structure. In this, the element added last is accessed first. The time complexity for all operations in a stack is O(1), making it efficient and improving performance.

Check out Stack Notes to learn stack in detail.

Driver code(Main function):

Let’s check out the main function before moving to each approach. In the main function, we initialize the stack, enter elements, reverse the stack by calling reverseStack() function and print the reversed stack.

Main function for Driver code:

public static void main(String args[]) {
  // initialize stack
  Stack<Integer> s = new Stack<Integer>();
  // push elements
  s.push(1);  s.push(2);
  s.push(3);
  s.push(4);
 
  // print elements before reversing
  System.out.println("Stack before reversing:");
  System.out.println(s);
 
  // reverse stack using reverseStack()
  s = reverseStack(s); // using stacks
  reverseStack() // recursion
 
  // print elements after reversing
  System.out.println("Stack after reversing:");
  System.out.println(s);
}

Now let’s go through each approach.

Reversing a Stack using Another Stack

In this approach, we would be using an extra stack to reverse the stack. Let’s see the pseudo-code for this approach.

Pseudo – Code for reverseStack()

initialize an empty extra stack
set n to the size of the original stack
for i to n
  set the variable element to the topmost element of the original stack
  pop the topmost element of the original stack
  push this element into the extra stack
return the extra stack, which is reversed
Working

reverseStack()

 // function to reverse stack using another stack
 static Stack<Integer> reverseStack(Stack<Integer> s) {
   // initialize extra stack
   Stack<Integer> extraStack = new Stack<Integer>();
   int n = s.size();
 
   for (int i = 0; i < n; i++) {
     // access the top element
     int element = s.peek();
     // remove the top element
     s.pop();
     // push the element into the extra stack
     extraStack.push(element);
   }
 
   // return the extraStack which is reversed
   return extraStack;
}

Time Complexity: O(N) 

Reason: The loop runs for n times and the time complexity for all the stack operations is O(1). Therefore the overall time complexity is O(N)

Space Complexity: O(N)

Reason: An extra stack of size N is used.

Reversing a Stack using Two Stacks

In this approach, we would be using two stacks to reverse the stack. This is similar to the above approach; the difference is that in this approach, instead of returning the extra stack, we directly use the original stack after transferring elements. Let’s see the pseudo-code for this approach.

Pseudo – Code for reverseStack()

initialize two empty stacks, a and b
transfer elements from s to a
transfer elements from a to b
transfer elements from b to s
display elements of s

Pseudo – Code for transfer

While stack is not empty
 Set element to the topmost element of the s1 stack
 Push element into the s2 stack
 Pop element from the s1 stack
Working

transfer() 

// function to transfer elements
static void transfer(Stack<Integer> s1, Stack<Integer> s2) {
 while (!s1.empty()) {
    int element = s1.peek();
    s2.push(element);
    s1.pop();
  } 
}

reverseStack()

// function to reverse stack
static Stack<Integer> reverseStack(Stack<Integer> s) {
  // initialize stack a and b
  Stack<Integer> a = new Stack<Integer>();
  Stack<Integer> b = new Stack<Integer>();
 
  // transfer elements from s to a
  transfer(s,a);
  // transfer elements from a to b
  transfer(a,b);
  // transfer elements from b to s
  transfer(b,s);
  // return the original stack
  return s;
}

Time Complexity: O(N) 

Reason: The loop runs for 3n times and the time complexity for all the stack operations is O(1). Therefore the overall time complexity is O(N)

Space Complexity: O(N)

Reason: Two extra stacks of size N is used and the overall space complexity becomes O(N)

Reversing a Stack using Recursion

If the question specifies that no other data structure can be used to solve the problem, recursion has to be used. In this approach, we pop the top element from the given stack and recursively call another instance of the same function. When this child function returns to the parent function, append the popped element to the bottom of the stack. For this, we would be using two recursive functions: reverseStack() and insertAtBottom().  

reverseStack():

It checks if the stack is empty or not. The top element is popped out and stored in the element variable if the stack is not empty. We then call reverseStack() function again on the updated stack. When this child function returns, we call the helper function insertAtBottom().

insertAtBottom()

It recursively inserts an element at the bottom of a stack. If the stack is empty, it simply pushes the element else; the top element is popped out and stored in the topElement variable. Then insertAtBottom() is called again on the updated stack. When this child function returns, it pushes the topElement back in the stack.

In this solution, we would be using recursion so check out this blog Recursion in Data Structure: How Does it Work, Types & When Used to know more about recursion.

Recommended: Please try to solve Reverse Stack Using Recursion on “CODESTUDIO” first before moving on to the solution. 

reverseStack()

specify the base case
  when the stack is empty, return
set element to topmost element of the stack
pop the topmost element of the stack
recursively call reverseStack on the updated stack
insert the element at the bottom of the stack

insertAtBottom()

specify the base case
   when the stack is empty, push element to stack and return
set toElement to topmost element of the stack
pop the topmost element of the stack
recursively call insertAtBottom on the updated stack
push element to stack
Working

reverseStack()

// function to reverse stack using recursion
 static void reverseStack(Stack<Integer> s) {
   // base case
   if(s.empty()) {
     return;
   }
 
   // access the top element
   int element = s.peek();
   // remove the top element
   s.pop();
   // reverse the remaining elements of a stack
   reverseStack(s);
   // insert the popped out element at the bottom
   insertAtBottom(s,element);
 }

insertAtBottom()

// function to insert top element at the bottom of stack
 static void insertAtBottom(Stack<Integer> s, int element) {
   // base case
   if(s.empty()) {
     // push the element at bottom
     s.push(element);
     return;
   }
   // access the top element
   int topElement = s.peek();
   // remove the top element
   s.pop();
   // insert the element at the bottom of the stack
   insertAtBottom(s,element);
   // add the top element to the stack
   s.push(topElement);
 }

Time Complexity: O(N²) 

Two recursive functions are there in which the first function is calling itself recursively and the second function in each call. Also, the second function is recursively called.

Space Complexity: O(N)

The recursive program uses a memory of O(N) to store the function call stack.

Reversing a Stack without using Recursion

In this solution, we would be implementing Implement Stack using Linked List and reverse the linked list to get the reversed stack. 

Please try to implement a Stack using a Linked List on CodeStudio. Also, check out this blog, How To Master Linked List And Its Importance, and notes on Linked List Reversal to know more about Linked List.

Working

Time Complexity: O(N) 

Reason: O(N) is the time complexity to reverse a linked list.

Space Complexity: O(1)

Reason: No extra space is required.

Frequently Asked Questions

Why is the space complexity in recursive solution O(N) even though no extra data structure is used?

The recursive program uses a memory of O(N) to store the function call stack. In the recursive program, we are storing both the functions in the call stack one after another.

Why is the time complexity in a recursive solution O(N²)?

For each topmost element of the stack, the whole stack is popped out and the topmost element is placed at the bottom of the stack. This takes O(N) complexity and doing this for every stack element makes the overall time complexity O(N²).

How is the topmost stack element inserted at the top element at the bottom of the stack in the recursive approach?

The top element of the stack is popped out and stored in the call stack frame until the stack becomes empty. When the stack becomes empty, the top element is added to the empty stack, and all the elements stored in the call stack are pushed while returning down the recursion tree.

Can the stack be reversed without using any extra space?

es, if the linked list is used to implement the stack, it can be reversed without extra space and linear time complexity.

Which node is considered as the top of the stack in the linked list implementation of the stack?

The head node (or the first node) is considered the top element when a stack is implemented using a linked list.

Key Takeaways

This blog covered the various methods of reversing a stack. The methods involved: reversing a stack using another stack, reversing a stack using two stacks,  reversing a stack using recursion, and reversing a stack using Linked List.
Don’t stop here. Check out our Data Structures and Algorithms -guided path to learning DSA from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.

Exit mobile version