Given a stack st[], Reverse the stack so that the top element becomes the bottom and the bottom element becomes the top, while preserving the order of the remaining elements accordingly.
Example:
Input: st[] = [1, 2, 3, 4]
Output: [1, 2, 3, 4]
Explanation:
Input: st[] = [3, 2, 1]
Output: [3, 2, 1]
Explanation:
[Approach 1] Recursive Approach
The idea is to use the recursion to reverse the given stack.
- First, we keep removing elements from the stack until stack becomes empty.
- Once the stack is empty, we start going back in the recursion. At each step, instead of placing the element back on top, we insert it at the bottom of the stack.
- To insert an element at the bottom, we recursively pop all elements, push the current element, and then put the popped elements back.
This way we will ensuring that the element that was originally at the top moves to the bottom, and gradually the entire stack gets reversed.
C++ #include <iostream> #include <stack> using namespace std; // function to insert element at the bottom of the stack void insertAtBottom(stack<int> &st, int x) { if (st.empty()) { st.push(x); return; } // hold the top element and remove it int top = st.top(); st.pop(); // recursively call to reach the bottom insertAtBottom(st, x); st.push(top); } // function to reverse the stack void reverseStack(stack<int> &st) { if (st.empty()) return; // hold the top element and remove it int top = st.top(); st.pop(); // reverse the remaining stack reverseStack(st); // insert the held element at the bottom insertAtBottom(st, top); } int main() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); reverseStack(st); while (!st.empty()) { cout << st.top() << " "; st.pop(); } return 0; } #include <stdio.h> #include <stdlib.h> #define MAX 100 struct myStack { int arr[MAX]; int top; }; // function to insert element at the bottom of the stack void insertAtBottom(struct myStack* st, int x) { if (st->top == -1) { st->arr[++st->top] = x; return; } // hold the top element and remove it int temp = st->arr[st->top--]; // recursively call to reach the bottom insertAtBottom(st, x); st->arr[++st->top] = temp; } // function to reverse the stack void reverseStack(struct myStack* st) { if (st->top == -1) return; // hold the top element and remove it int temp = st->arr[st->top--]; // reverse the remaining stack reverseStack(st); // insert the held element at the bottom insertAtBottom(st, temp); } int main() { struct myStack st; st.top = -1; st.arr[++st.top] = 1; st.arr[++st.top] = 2; st.arr[++st.top] = 3; st.arr[++st.top] = 4; reverseStack(&st); while (st.top != -1) { printf("%d ", st.arr[st.top--]); } return 0; } import java.util.Stack; class GfG{ // function to insert element at the bottom of the stack static void insertAtBottom(Stack<Integer> st, int x) { if (st.isEmpty()) { st.push(x); return; } // hold the top element and remove it int top = st.pop(); // recursively call to reach the bottom insertAtBottom(st, x); st.push(top); } // function to reverse the stack static void reverseStack(Stack<Integer> st) { if (st.isEmpty()) return; // hold the top element and remove it int top = st.pop(); // reverse the remaining stack reverseStack(st); // insert the held element at the bottom insertAtBottom(st, top); } public static void main(String[] args) { Stack<Integer> st = new Stack<>(); st.push(1); st.push(2); st.push(3); st.push(4); reverseStack(st); while (!st.isEmpty()) { System.out.print(st.pop() + " "); } } } # function to insert element at the bottom of the stack def insertAtBottom(st, x): if not st: st.append(x) return # hold the top element and remove it top = st.pop() # recursively call to reach the bottom insertAtBottom(st, x) st.append(top) # function to reverse the stack def reverseStack(st): if not st: return # hold the top element and remove it top = st.pop() # reverse the remaining stack reverseStack(st) # insert the held element at the bottom insertAtBottom(st, top) if __name__ == "__main__": st = [1, 2, 3, 4] reverseStack(st) while st: print(st.pop(), end=" ")
using System; using System.Collections.Generic; class GfG { // function to insert element at the bottom of the stack static void insertAtBottom(Stack<int> st, int x) { if (st.Count == 0) { st.Push(x); return; } // hold the top element and remove it int top = st.Pop(); // recursively call to reach the bottom insertAtBottom(st, x); st.Push(top); } // function to reverse the stack static void reverseStack(Stack<int> st) { if (st.Count == 0) return; // hold the top element and remove it int top = st.Pop(); // reverse the remaining stack reverseStack(st); // insert the held element at the bottom insertAtBottom(st, top); } static void Main() { Stack<int> st = new Stack<int>(); st.Push(1); st.Push(2); st.Push(3); st.Push(4); reverseStack(st); while (st.Count > 0) { Console.Write(st.Pop() + " "); } } } // function to insert element at the bottom of the stack function insertAtBottom(st, x) { if (st.length === 0) { st.push(x); return; } // hold the top element and remove it let top = st.pop(); // recursively call to reach the bottom insertAtBottom(st, x); st.push(top); } // function to reverse the stack function reverseStack(st) { if (st.length === 0) return; // hold the top element and remove it let top = st.pop(); // reverse the remaining stack reverseStack(st); // insert the held element at the bottom insertAtBottom(st, top); } // driver code let st = []; st.push(1); st.push(2); st.push(3); st.push(4); reverseStack(st); let res = []; while (st.length > 0) { res.push(st.pop()); } console.log(res.join(" ")); Time Complexity: O(n2)
Auxiliary Space: O(n), due to recursion stack
[Approach 2] Iterative Approach - O(n) Time and O(n) Space
We use an auxiliary stack to hold elements while popping them from the original stack. Since stacks are LIFO, pushing all elements into the auxiliary stack will naturally reverse their order. Finally, we replace the original stack with the auxiliary stack.
C++ #include <iostream> #include <stack> using namespace std; void reverseStack(stack<int> &st) { stack<int> aux; // move all elements to auxiliary stack while (!st.empty()) { aux.push(st.top()); st.pop(); } // swapping aux stack with st swap(st, aux); } int main() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); reverseStack(st); while (!st.empty()) { cout << st.top() << " "; st.pop(); } return 0; } #include <stdio.h> #include <stdlib.h> #define MAX 100 // stack structure struct myStack { int arr[MAX]; int top; }; // initialize stack void init(struct myStack* st) { st->top = -1; } // check empty int isEmpty(struct myStack* st) { return st->top == -1; } // push element void push(struct myStack* st, int x) { if (st->top == MAX - 1) return; st->arr[++st->top] = x; } // pop element int pop(struct myStack* st) { if (isEmpty(st)) return -1; return st->arr[st->top--]; } // get top int peek(struct myStack* st) { return st->arr[st->top]; } // function to reverse the stack void reverseStack(struct myStack* st) { struct myStack aux; init(&aux); // move all elements to auxiliary stack while (!isEmpty(st)) { push(&aux, pop(st)); } // replace original stack with auxiliary *st = aux; } int main() { struct myStack st; init(&st); push(&st, 1); push(&st, 2); push(&st, 3); push(&st, 4); reverseStack(&st); while (!isEmpty(&st)) { printf("%d ", pop(&st)); } return 0; } import java.util.Stack; class GfG { public static void reverseStack(Stack<Integer> st) { Stack<Integer> aux = new Stack<>(); // move all elements to auxiliary stack while (!st.isEmpty()) { aux.push(st.pop()); } // replace original stack with auxiliary st.addAll(aux); } public static void main(String[] args) { Stack<Integer> st = new Stack<>(); st.push(1); st.push(2); st.push(3); st.push(4); reverseStack(st); while (!st.isEmpty()) { System.out.print(st.pop() + " "); } } } def reverseStack(st): aux = [] # move all elements to auxiliary stack while st: aux.append(st.pop()) # replace original stack with auxiliary st[:] = aux if __name__ == "__main__": st = [] st.append(1) st.append(2) st.append(3) st.append(4) reverseStack(st) while st: print(st.pop(), end=" ")
using System; using System.Collections.Generic; class GfG { static void reverseStack(ref Stack<int> st) { Stack<int> aux = new Stack<int>(); // move all elements to auxiliary stack while (st.Count > 0) { aux.Push(st.Peek()); st.Pop(); } st = aux; } static void Main() { Stack<int> st = new Stack<int>(); st.Push(1); st.Push(2); st.Push(3); st.Push(4); reverseStack(ref st); while (st.Count > 0) { Console.Write(st.Peek() + " "); st.Pop(); } } } function reverseStack(st) { let aux = []; // move all elements to auxiliary stack while (st.length > 0) { aux.push(st.pop()); } // replace original stack with auxiliary st.push(...aux); } // Driver Code let st = []; st.push(1); st.push(2); st.push(3); st.push(4); reverseStack(st); let res = []; while (st.length > 0) { res.push(st.pop()); } console.log(res.join(" "));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile