Reverse a stack using recursion
Given a stack, recursively reverse it only using its abstract data type (ADT) standard operations, i.e., push(item), pop(), peek(), isEmpty(), size(), etc.
The idea is to hold all items in a call stack until the stack becomes empty. Then, insert each item in the call stack at the bottom of the stack. Following is the pictorial representation of the above logic:
To insert an item x at the bottom of the given stack, pop all items from the stack and hold them in the call stack. When the stack becomes empty, push the given item x into the stack. Then as the recursion unfolds, push each item in the call stack into the stack’s top.
Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <stack> using namespace std; // Recursive function to insert an item at the bottom of a given stack void insertAtBottom(stack<int> &s, int item) { // base case: if the stack is empty, insert the given item at the bottom if (s.empty()) { s.push(item); return; } // Pop all items from the stack and hold them in the call stack int top = s.top(); s.pop(); insertAtBottom(s, item); // After the recursion unfolds, push each item in the call stack // at the top of the stack s.push(top); } // Recursive function to reverse a given stack void reverseStack(stack<int> &s) { // base case: stack is empty if (s.empty()) { return; } // Pop all items from the stack and hold them in the call stack int item = s.top(); s.pop(); reverseStack(s); // After the recursion unfolds, insert each item in the call stack // at the bottom of the stack insertAtBottom(s, item); } int main() { stack<int> s; for (int i = 1; i <= 5; i++) { s.push(i); } reverseStack(s); cout << "Reversed stack is "; while (!s.empty()) { cout << s.top() << ' '; s.pop(); } return 0; } |
Output:
Reversed stack is 1 2 3 4 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import java.util.Stack; class Main { // Recursive function to insert an item at the bottom of a given stack public static void insertAtBottom(Stack<Integer> s, int item) { // base case: if the stack is empty, insert the given item at the bottom if (s.empty()) { s.push(item); return; } // Pop all items from the stack and hold them in the call stack int top = s.pop(); insertAtBottom(s, item); // After the recursion unfolds, push each item in the call stack // at the top of the stack s.push(top); } // Recursive function to reverse a given stack public static void reverseStack(Stack<Integer> s) { // base case: stack is empty if (s.empty()) { return; } // Pop all items from the stack and hold them in the call stack int item = s.pop(); reverseStack(s); // After the recursion unfolds, insert each item in the call stack // at the bottom of the stack insertAtBottom(s, item); } public static void main(String[] args) { Stack<Integer> s = new Stack<>(); for (int i = 1; i <= 5; i++) { s.push(i); } System.out.println("Original stack is " + s); reverseStack(s); System.out.println("Reversed stack is " + s); } } |
Output:
Original stack is [1, 2, 3, 4, 5]
Reversed stack is [5, 4, 3, 2, 1]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from collections import deque # Recursive function to insert an item at the bottom of a given stack def insertAtBottom(s, item): # base case: if the stack is empty, insert the given item at the bottom if not s: s.append(item) return # Pop all items from the stack and hold them in the call stack top = s.pop() insertAtBottom(s, item) # After the recursion unfolds, push each item in the call stack # at the top of the stack s.append(top) # Recursive function to reverse a given stack def reverseStack(s): # base case: stack is empty if not s: return # Pop all items from the stack and hold them in the call stack item = s.pop() reverseStack(s) # After the recursion unfolds, insert each item in the call stack # at the bottom of the stack insertAtBottom(s, item) if __name__ == '__main__': s = deque(range(1, 6)) print('Original stack is', s) reverseStack(s) print('Reversed stack is', s) |
Output:
Original stack is deque([1, 2, 3, 4, 5])
Reversed stack is deque([5, 4, 3, 2, 1])
The time complexity of the above solution is O(n2) and requires O(n) implicit space for the call stack, where n is the total number of elements in the stack. The recurrence relation is:
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
and so on, until
T(n) = T(n-(n-1)) + T(n-(n-2)) + … + (n-2) + (n-1) + n
= T(1) + T(2) + … + (n-2) + (n-1) + n = n×(n+1)/2
= 1 + 2 + … + (n-2) + (n-1) + n = n×(n+1)/2
= O(n2)
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)