☕ DSA Java Articles

Topics › Recursion and Backtracking › Get a Strong Hold

Reverse a Stack

Medium TUF ID 901 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a stack of integers. Reverse it in place: the element that was on top must end up at the bottom and vice versa. The intended solution uses recursion only, with no auxiliary array, list or second stack; the function call stack is the only extra memory.

Constraints: up to a few thousand elements (bounded by recursion depth); values fit in an int.

The stack is a Deque<Integer> backed by ArrayDeque; push, pop and peek work on the top. The examples list elements from bottom to top.

Example 1

stack (bottom to top) = [1, 2, 3]       // 3 is on top
answer                = [3, 2, 1]       // 1 is on top

Example 2

stack (bottom to top) = [3, 2, 1, 4, 5]
answer                = [5, 4, 3, 2, 1]

Reversing is not the same as popping everything and printing it: a pop loop reads the elements in reverse order, but destroys the stack. We need the same stack object to hold the reversed contents afterwards.

Approach 1: Brute force, through a list

Intuition. A stack hands its elements back in reverse order of insertion. If we pop everything into a list, the list reads top to bottom. Pushing that list back in order puts the old top in first, so it lands at the bottom, which is exactly a reversal.

Algorithm.

  1. Pop every element into a list popped (old top first).
  2. For each value in popped, in order, push it.
static void reverseViaList(Deque<Integer> stack) {
    List<Integer> popped = new ArrayList<>();
    while (!stack.isEmpty()) popped.add(stack.pop());   // popped = old top, ..., old bottom
    for (int v : popped) stack.push(v);                  // the old top is pushed first and ends at the bottom
}

Complexity. Time O(n). Space O(n) for the list.

Approach 2: Three pours with two helper stacks

Intuition. Suppose only stack operations are allowed, but extra stacks are fine. Pouring a stack into another stack (pop from one, push onto the other until empty) reverses it, but the result lives in the wrong object. Pouring it back restores the original order. So one pour is too few and two pours cancel out; three pours leave the original object holding the reversed sequence.

Algorithm.

  1. Pour stack into first: first is reversed.
  2. Pour first into second: second has the original order.
  3. Pour second back into stack: stack is reversed.
static void reverseWithTwoStacks(Deque<Integer> stack) {
    Deque<Integer> first = new ArrayDeque<>();
    Deque<Integer> second = new ArrayDeque<>();
    while (!stack.isEmpty()) first.push(stack.pop());    // first holds the reversed order
    while (!first.isEmpty()) second.push(first.pop());   // second holds the original order again
    while (!second.isEmpty()) stack.push(second.pop());  // back into the original stack, reversed
}

Complexity. Time O(n), three passes. Space O(n) for the two helper stacks.

This is how you would do it with a stack API that gives no access to the underlying storage. It still needs auxiliary data structures, which the recursive version eliminates.

Approach 3: Optimal, recursion only

Intuition. A recursive call can hold one element in a local variable while the rest of the stack is processed, so the frames of the call stack act as the hidden helper storage. The reversal of a stack is: take the top off, reverse the remaining n - 1 elements, then put the element you took at the bottom. Putting something at the bottom is itself recursive: pop the top, insert the value at the bottom of what remains, push the popped top back.

Algorithm.

reverseRecursive(stack):

  1. If the stack is empty, return.
  2. top = pop().
  3. reverseRecursive(stack).
  4. insertAtBottom(stack, top).

insertAtBottom(stack, v):

  1. If the stack is empty, push v and return.
  2. top = pop().
  3. insertAtBottom(stack, v).
  4. push(top).
static void reverseRecursive(Deque<Integer> stack) {
    if (stack.isEmpty()) return;                         // base case: the empty stack is its own reverse
    int top = stack.pop();
    reverseRecursive(stack);                             // the other n - 1 elements, reversed
    insertAtBottom(stack, top);                          // the old top becomes the new bottom
}

static void insertAtBottom(Deque<Integer> stack, int v) {
    if (stack.isEmpty()) {                               // base case: the bottom is right here
        stack.push(v);
        return;
    }
    int top = stack.pop();                               // lift the elements above the bottom, one frame each
    insertAtBottom(stack, v);
    stack.push(top);                                     // and put them back in the same order
}

Dry run on [1, 2, 3] (bottom to top). The reverseRecursive frames pop 3, then 2, then 1, reaching an empty stack. They finish in the opposite order:

frame finishing inserts at bottom stack before stack after
the one holding 1 1 [] [1]
the one holding 2 2 [1] pop 1, push 2, push 1 → [2, 1]
the one holding 3 3 [2, 1] pop 1, pop 2, push 3, push 2, push 1 → [3, 2, 1]

The deepest frame holds the original bottom and is the first to insert, so the bottom becomes the new top; the outermost frame holds the original top and inserts it last, at the very bottom.

Complexity. Time O(n^2): inserting at the bottom of a stack with k elements pops and re-pushes all k of them, and we do this for k = 0, 1, ..., n - 1. Space O(n): at the deepest point there are n frames of reverseRecursive plus up to n frames of insertAtBottom.

Note the trade: compared with Approach 1 this is slower, but it uses no data structure beyond the call stack, which is the whole point of the exercise. The same two-function pattern (pop, recurse, re-insert with a second recursion) solves the sorting version of this problem too.

Edge cases and pitfalls