Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Reverse a Stack in Java: Understand Every Call and Return

Reverse a stack using recursion only, with insert-at-bottom reasoning, LIFO dry runs, commented Java and edge-case tests.

MediumRecursion and backtrackingPattern: recursion, reversal

Problem statement

Reverse a stack in place, using only push, pop, peek, and an empty check. The original takeUforward prompt forbids loops, extra collections, and built-in reversal. It allows O(n) call-stack space; n is between 1 and 100.

Our diagrams write stacks bottom → top, so the rightmost value is popped first. For [4, 1, 3, 2], the result is [2, 3, 1, 4]. Reversal changes order, not values. It works with duplicates and negative values too.

Constraints & requirements

CONTRACT
Return the same stack with its bottom-to-top order reversed; preserve every value, including duplicates.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    1, 2, 3
    Output
    [3, 2, 1]

    Old top becomes bottom.

  2. Example 2 Case 2

    Input
    7
    Output
    [7]

    A single value is unchanged.

  3. Example 3 Case 3

    Input
    2, 2, -1
    Output
    [-1, 2, 2]

    Preserve duplicates and signs.

Solve on GeeksforGeeks ↗

The Atlas exercise additionally requires recursion without loops; keep that requirement when practising.

Hints Optional

Hints become more specific one step at a time.
01Find the smaller problem

Where should the old top go after reversing the smaller stack?

02Define the state

At the bottom, not the top. Define a helper that inserts one saved value at the bottom.

03Connect the recurrence

Temporarily pop until empty, push the saved value, then restore each displaced top on return.

Understand the smaller problem

The intuition is to let recursion reverse the smaller stack, then place the value we removed underneath that reversed stack.

Imagine lifting the top value 2 out of [4, 1, 3, 2]. If someone reverses the smaller stack [4, 1, 3] into [3, 1, 4], where should 2 go?

At the bottom. Pushing it onto the top would simply undo our work.

This gives two responsibilities:

  1. reverseStack reverses everything except the saved top.
  2. insertBottom moves that saved value beneath the reversed smaller stack.

A call frame remembers its local top while it waits. The input stack and the Java call stack are two different stacks.

How to think before coding

Trust that recursion can reverse the smaller stack after you pop its top. The saved value must then go at the bottom, not back at the top. That creates a second smaller problem, insertAtBottom, which temporarily pops values and restores them after inserting. Define both empty-stack base cases before writing either recursive method. This respects the recursion-only restriction.

A simpler baseline—and why it is forbidden here

With an extra list, we could pop everything, then rebuild the stack in reverse order in O(n) time and O(n) storage:

Java
static void reverseWithExtraStorage(Deque<Integer> stack) {
    List<Integer> popped = new ArrayList<>(); // Store the old top-first order.
    while (!stack.isEmpty()) popped.add(stack.pop()); // Remove each original value.
    for (int value : popped) stack.push(value); // Last pushed becomes the new top.
}

This is a useful baseline, not a valid submission for the recursion-only contract. We must replace the temporary list and loops with suspended recursive calls.

Recursive solution

Use java.util.Deque and ArrayDeque in a standalone program. The judge may instead supply Stack; its push/pop/isEmpty operations serve the same roles. Neither algorithm uses iteration.

Java
public static void reverseStack(Deque<Integer> stack) {
    if (stack.isEmpty()) return; // An empty stack is already reversed; stop descending.
    int top = stack.pop(); // Save this value in this call frame, not in another collection.
    reverseStack(stack); // Trust the smaller stack to reverse before this call resumes.
    insertBottom(stack, top); // The old top belongs below every reversed remaining value.
}

private static void insertBottom(Deque<Integer> stack, int value) {
    if (stack.isEmpty()) { // We reached the bottom: there is nothing below value.
        stack.push(value); // Place the saved old top at the bottom.
        return; // Do not pop the value we just inserted.
    }
    int top = stack.pop(); // Temporarily expose the next deeper position.
    insertBottom(stack, value); // Keep descending until the bottom is exposed.
    stack.push(top); // Restore this displaced value above the inserted value.
}

Why does insertBottom pop values and then push them back? There is no “insert at index zero” stack operation. We temporarily remove values until the stack is empty, place the new bottom, and restore removed values in reverse call order. Their relative order stays unchanged.

Recursion tree: the helpers are real calls

For bottom → top [1, 2], this is the actual call structure:

Worked example · read from top to bottom
reverse([1,2]) saves 2
└─ reverse([1]) saves 1
   ├─ reverse([]) returns
   └─ insertBottom([],1) pushes 1
└─ insertBottom([1],2) saves 1
   └─ insertBottom([],2) pushes 2
   resumes: pushes saved 1
Final data stack: [2,1] (top = 1)

The call tree is not a complete binary decision tree. Helper calls begin only after a reverse call’s child returns. Read the helper trace in return order: reverse waits first, then its resumed frame calls insertAtBottom.

Dry run: what returns first?

Numbered illustrated dry run for Reverse a Stack; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript
Event Data stack, bottom → top Saved values in waiting frames
reverse saves 2 [1] 2
reverse saves 1 [] 2, 1
Empty reverse returns [] 2, 1
Insert 1 at bottom [1] 2
Insert 2 removes 1 [] 2, 1
Insert 2 reaches bottom [2] 2, 1
Restore removed 1 [2, 1] 2
Outer reverse returns [2, 1] none

A popped input value is not lost: it lives in one local variable until its call resumes. The newest call returns first—last in, first out.

Why this is correct

The empty stack is already reversed. Assume reversing n−1 values works. We remove the original top, reverse those n−1 values, then insert the removed top underneath them. That is exactly the required reversal of n values.

For insertBottom, assume it inserts correctly into a smaller stack. Removing the top exposes that smaller stack; the recursive insertion places value at its bottom; restoring the saved top preserves all original relative positions above value.

Complexity and practical limits

The nth insertion may remove and restore n−1 values. Work is 1 + 2 + … + n, so O(n²) time, not O(n). Peak live frames are O(n), not O(n²); completed calls no longer occupy the call stack. Extra space is O(n).

This is the natural recursion-only solution, not a globally fastest stack reversal. Large inputs can overflow Java’s call stack; the stated bound is small.

Common mistakes and edge cases

  • Pushing top immediately after reverse restores the original order instead of reversing it.
  • Forgetting the empty base case eventually pops an empty stack.
  • Forgetting to restore a popped helper value loses data.
  • Reading a displayed leftmost value as the top reverses the diagram convention.
  • Test [] → [] as a defensive extension, [7] → [7], and [2, 2, -1] → [-1, 2, 2].

“Reverse, recursion only, no other data structure” suggests do work while returning, with a helper that places a saved item at the far end. Compare printing an immutable list backward: there we only print during returns; we do not mutate a structure.

Company evidence

Amazon · historical candidate report. A public Amazon SDE2 experience describes stack reversal with recursion in a Hyderabad interview dated 2 February 2019. This is one candidate’s account, not an official question bank or evidence of current frequency. Source checked 3 October 2026.

Final takeaway

Remove the top, reverse the rest, insert the saved top at the bottom. Ask “what does my child promise?” and “what remains for this frame after it returns?”

Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.

Practice next

Next lessonCount Subsequences with Sum K in Java: Choices, Returns, and DP

Compare a different recursive promise and how its parent resumes.

Back to Recursion and backtracking →