Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Reverse a Stack Recursively

EASYProblemSolveExternal Links

Description

Given a stack of integers, reverse the order of its elements so that the element currently at the top becomes the bottom-most element, and the element at the bottom becomes the new top. You must modify the stack in-place.

A stack is a Last-In-First-Out (LIFO) data structure — the most recently pushed element is the first one to be popped. Reversing a stack means flipping this order entirely: the element that was pushed first (and sits at the bottom) should now be on top, and the element pushed last (currently on top) should move to the bottom.

The challenge is to accomplish this reversal using only recursion, without employing any loop or explicit auxiliary data structure.

Examples

Example 1

Input: st = [1, 2, 3, 4]

Output: [4, 3, 2, 1]

Explanation: The array represents the stack from bottom to top. Initially, 1 is at the bottom and 4 is at the top. After reversing, 4 moves to the bottom and 1 becomes the new top element. Every element's position is mirrored around the center of the stack.

Example 2

Input: st = [3, 2, 1]

Output: [1, 2, 3]

Explanation: Before reversal the top element is 1 and the bottom is 3. After reversal the top becomes 3 and the bottom becomes 1. The middle element 2 stays in place since it is the center of an odd-length stack.

Example 3

Input: st = [5]

Output: [5]

Explanation: A single-element stack is already its own reverse — there is nothing to swap.

Constraints

  • 1 ≤ st.size() ≤ 100
  • 0 ≤ st[i] ≤ 100

Editorial

Brute Force - Auxiliary Array

Intuition

The most straightforward way to reverse a stack is to use an auxiliary container. Imagine you have a tower of plates (the stack) and you want to flip the entire tower upside down. The simplest strategy is to move every plate to a table (an auxiliary array), one at a time from the top, and then stack them back up in the same order you placed them on the table.

When you pop elements from a stack, they come out in reverse order — the top element comes first, then the next-to-top, and so on. If you store them in an array in this order and then push them back into the stack, each element lands in the exact opposite position it started in. The top becomes the bottom and the bottom becomes the top.

This works because the LIFO property of the stack naturally reverses the order during the pop phase, and the array preserves that reversed order so we can reconstruct the stack.

Step-by-Step Explanation

Let's trace through with st = [1, 2, 3] (bottom to top, where 3 is on top):

Step 1: Create an empty temporary array. Original stack: [1, 2, 3]. Temp: [].

Step 2: Pop the top element 3 from the stack and append it to the temp array.

  • Stack: [1, 2], Temp: [3]

Step 3: Pop the top element 2 and append it.

  • Stack: [1], Temp: [3, 2]

Step 4: Pop the last element 1 and append it.

  • Stack: [], Temp: [3, 2, 1]

Step 5: Push all elements from the temp array back into the stack in order: push 3 first (it goes to the bottom), then 2, then 1 (it ends up on top).

  • Stack: [3, 2, 1]

Step 6: The stack is now [3, 2, 1] — reversed. Bottom is 3, top is 1. Originally bottom was 1 and top was 3.

Auxiliary Array Transfer — Reversing the Stack — Watch how popping all elements from the original stack into an auxiliary array and pushing them back naturally reverses the order.

Algorithm

  1. Create an empty temporary array (or list)
  2. While the stack is not empty:
    • Pop the top element from the stack
    • Append it to the temporary array
  3. For each element in the temporary array (in order):
    • Push it back onto the stack
  4. The stack is now reversed

Code

#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    void reverse(stack<int>& st) {
        vector<int> temp;
        
        // Pop all elements into a temporary array
        while (!st.empty()) {
            temp.push_back(st.top());
            st.pop();
        }
        
        // Push elements back in the same order
        // Since we popped in reverse, pushing back gives reversed stack
        for (int val : temp) {
            st.push(val);
        }
    }
};
class Solution:
    def reverse(self, st):
        temp = []
        
        # Pop all elements into temporary list
        while st:
            temp.append(st.pop())
        
        # Extend stack with elements in popped order
        # This reverses the original order
        st.extend(temp)
import java.util.*;

class Solution {
    public void reverse(Stack<Integer> st) {
        List<Integer> temp = new ArrayList<>();
        
        // Pop all elements into temporary list
        while (!st.isEmpty()) {
            temp.add(st.pop());
        }
        
        // Push elements back in the same order they were popped
        for (int val : temp) {
            st.push(val);
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

We pop all n elements from the stack once (n operations) and push all n elements back once (n operations). Each pop and push is O(1). Total work: 2n operations, which simplifies to O(n).

Space Complexity: O(n)

The temporary array stores all n elements simultaneously. This is explicit auxiliary memory that scales linearly with the input size.

Why This Approach Is Not Efficient

The auxiliary array approach reverses the stack in O(n) time, which is efficient in terms of speed. However, it relies on an explicit extra data structure (a temporary array or a second stack) that consumes O(n) additional memory.

In many technical interviews, the follow-up challenge is: can you reverse the stack without using any extra data structure? The only tool allowed is recursion itself.

The key insight is that recursion provides an implicit storage mechanism — the function call stack. Each recursive call can hold one element in a local variable. By leveraging this, we can pop all elements during the downward phase of recursion and reinsert them in reversed order during the upward (unwinding) phase, without ever creating an auxiliary container.

This leads us to a purely recursive approach using two cooperating functions: one to reverse the stack and another to insert an element at the bottom.

Optimal Approach - Recursion with Insert at Bottom

Intuition

Imagine you have a stack of numbered boxes: 3 on top, 2 in the middle, 1 at the bottom. To reverse it, you need 1 on top and 3 at the bottom.

Here is the clever recursive strategy: pick up the top box (3), ask a helper to reverse the remaining stack ([1, 2] → [2, 1]), and then slide the box you are holding (3) underneath the entire reversed sub-stack. That last step — sliding an element to the very bottom — is itself a recursive operation.

This gives us two functions:

  1. reverseStack(stack): Pop the top element, recursively reverse the rest of the stack, then insert the popped element at the bottom.
  2. insertAtBottom(stack, element): If the stack is empty, just push the element. Otherwise, pop the top, recursively insert the element at the bottom of the smaller stack, then push the popped value back.

The recursion naturally holds elements in the call stack's local variables during the downward phase and places them back in reversed positions during the upward (unwinding) phase.

Two-phase recursive reversal: pop all elements via reverseStack, then insert each at the bottom via insertAtBottom
Two-phase recursive reversal: pop all elements via reverseStack, then insert each at the bottom via insertAtBottom

Step-by-Step Explanation

Let's trace through with st = [1, 2, 3] (bottom to top, where 3 is on top):

Phase 1: Unwinding — Pop all elements via recursion

Step 1: Call reverseStack([1, 2, 3]). Pop 3 and hold it in a local variable. Stack becomes [1, 2]. Recurse on the smaller stack.

Step 2: Call reverseStack([1, 2]). Pop 2 and hold it. Stack becomes [1]. Recurse again.

Step 3: Call reverseStack([1]). Pop 1 and hold it. Stack becomes []. Recurse on the empty stack — base case reached. The stack is empty, so start unwinding.

Phase 2: Rewinding — Insert each held element at the bottom

Step 4: Returning from the deepest call, insert 1 at the bottom of the empty stack. Stack is empty, so simply push 1. Stack: [1].

Step 5: Insert 2 at the bottom of [1]. To reach the bottom, pop 1 and hold it. Push 2 into the now-empty stack. Push 1 back on top. Stack: [2, 1].

Step 6: Insert 3 at the bottom of [2, 1]. Pop 1, hold it. Pop 2, hold it. Stack is empty. Push 3. Push 2 back. Push 1 back. Stack: [3, 2, 1].

Result: Stack is now [3, 2, 1] — fully reversed! The original top element 3 is now at the bottom and the original bottom element 1 is at the top.

Recursive Stack Reversal — Pop All, Then Insert at Bottom — Watch the two-phase recursive process: first all elements are popped via reverseStack, then each is inserted at the bottom via insertAtBottom during the unwinding.

Algorithm

reverseStack(stack):

  1. If the stack is empty, return (base case)
  2. Pop the top element and store it in a local variable
  3. Recursively call reverseStack on the remaining stack
  4. Call insertAtBottom to place the stored element at the bottom of the now-reversed stack

insertAtBottom(stack, element):

  1. If the stack is empty, push the element and return (base case)
  2. Pop the top element and store it in a local variable
  3. Recursively call insertAtBottom with the smaller stack and the same element
  4. Push the stored top element back onto the stack

Code

#include <stack>
using namespace std;

class Solution {
public:
    // Helper: insert an element at the bottom of the stack
    void insertAtBottom(stack<int>& st, int element) {
        if (st.empty()) {
            st.push(element);
            return;
        }
        
        int topVal = st.top();
        st.pop();
        
        // Recurse until stack is empty
        insertAtBottom(st, element);
        
        // Push the held element back on top
        st.push(topVal);
    }
    
    void reverse(stack<int>& st) {
        if (st.empty()) {
            return;
        }
        
        // Hold the top element
        int topVal = st.top();
        st.pop();
        
        // Reverse the remaining stack
        reverse(st);
        
        // Insert the held element at the bottom
        insertAtBottom(st, topVal);
    }
};
class Solution:
    def insertAtBottom(self, st, element):
        if not st:
            st.append(element)
            return
        
        top_val = st.pop()
        
        # Recurse until stack is empty
        self.insertAtBottom(st, element)
        
        # Push the held element back on top
        st.append(top_val)
    
    def reverse(self, st):
        if not st:
            return
        
        # Hold the top element
        top_val = st.pop()
        
        # Reverse the remaining stack
        self.reverse(st)
        
        # Insert the held element at the bottom
        self.insertAtBottom(st, top_val)
import java.util.*;

class Solution {
    // Helper: insert an element at the bottom of the stack
    static void insertAtBottom(Stack<Integer> st, int element) {
        if (st.isEmpty()) {
            st.push(element);
            return;
        }
        
        int topVal = st.pop();
        
        // Recurse until stack is empty
        insertAtBottom(st, element);
        
        // Push the held element back on top
        st.push(topVal);
    }
    
    static void reverse(Stack<Integer> st) {
        if (st.isEmpty()) {
            return;
        }
        
        // Hold the top element
        int topVal = st.pop();
        
        // Reverse the remaining stack
        reverse(st);
        
        // Insert the held element at the bottom
        insertAtBottom(st, topVal);
    }
}

Complexity Analysis

Time Complexity: O(n²)

The reverseStack function makes n recursive calls (one for each element). At each level of the recursion, it calls insertAtBottom, which itself makes up to k recursive calls where k is the current size of the stack. Summing over all levels: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2, which simplifies to O(n²).

Space Complexity: O(n)

The maximum depth of the recursion call stack is O(n). reverseStack recurses n levels deep, and at each level insertAtBottom can recurse up to n levels. However, these two recursions are not nested simultaneously — insertAtBottom completes before the next reverseStack call begins. Therefore, the maximum call stack depth at any point is O(n). No explicit auxiliary data structures are used.