☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Sort a Stack

Medium TUF ID 936 SDE

Java source ↗ Edit this article ↗

Problem

You are given a stack of integers. Rearrange it in place so that it is sorted with the largest element on top: popping it repeatedly yields the values in non-increasing order. You may use the stack operations push, pop, peek and isEmpty. The classic version forbids loops over auxiliary arrays and expects either recursion or a second stack.

In Java the stack is a Deque<Integer> (an ArrayDeque used through push, pop and peek).

Constraints: 0 ≤ n ≤ 10^4; recursive solutions are additionally limited by the depth of the call stack. Values fit in an int, duplicates and negatives allowed.

Example 1

stack (bottom → top) = [11, 2, 32, 3, 41]
after sorting, popping gives 41, 32, 11, 3, 2

Example 2

stack (bottom → top) = [3, 2, 1]        // 1 is on top
after sorting, popping gives 3, 2, 1    // 3 must now be on top

Approach 1: Brute force, copy out and sort

Intuition. If the restrictions are lifted, sorting a stack is just sorting a list. Pop everything into a list, sort it ascending, and push it back smallest first so the largest ends on top. This is the reference answer the other two approaches must match, and it is the fastest. It is “brute force” only in the sense that it ignores the exercise’s rules.

Algorithm.

  1. Pop every element into a list.
  2. Sort the list ascending.
  3. Push the elements in that order; the last pushed (the largest) ends on top.
static void bruteForce(Deque<Integer> st) {
    List<Integer> items = new ArrayList<>();
    while (!st.isEmpty()) items.add(st.pop());
    Collections.sort(items);
    for (int v : items) st.push(v);                    // smallest pushed first ends at the bottom
}

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

Approach 2: Recursion (insertion sort on the call stack)

Intuition. Recursion gives us a free second stack: the call stack. Each pending call can hold one popped value in a local variable while the rest of the stack is processed. That is enough to run insertion sort:

Both functions are correct by induction on the stack size. insertSorted only ever removes elements larger than x and puts them back in the same order, so sortedness is preserved.

Algorithm.

  1. sortRecursive(st): if empty, return. Pop top, call sortRecursive(st), call insertSorted(st, top).
  2. insertSorted(st, x): if st is empty or st.peek() ≤ x, push x and return. Otherwise pop bigger, call insertSorted(st, x), push bigger.
static void sortRecursive(Deque<Integer> st) {
    if (st.isEmpty()) return;
    int top = st.pop();
    sortRecursive(st);                                 // the remaining stack is now sorted
    insertSorted(st, top);
}

static void insertSorted(Deque<Integer> st, int x) {
    if (st.isEmpty() || st.peek() <= x) {
        st.push(x);
        return;
    }
    int bigger = st.pop();                             // x belongs below this element
    insertSorted(st, x);
    st.push(bigger);
}

Complexity. Time O(n^2): inserting into a sorted stack of size i can unwind all i elements, and 1 + 2 + ... + n is quadratic. Space O(n) for the call stack: sortRecursive nests n deep, and an insertSorted chain can nest up to n more on top of it.

That recursion depth is the practical weakness. Each frame is small, but a stack of tens of thousands of elements can throw StackOverflowError with default JVM settings.

Approach 3: Iterative, with a temporary stack

Intuition. Replace the call stack with an explicit second stack tmp, kept sorted with its smallest element on top. Take elements from the input one at a time. Before placing x on tmp, move every element of tmp that is smaller than x back onto the input stack; now tmp’s top is ≥ x, so pushing x keeps it sorted. The elements we moved back are not lost: they will be popped and placed again later.

When the input is empty, tmp holds everything with the smallest on top. Pouring it back into the input reverses the order, which leaves the largest on top as required.

Algorithm.

  1. While the input stack is not empty: pop x.
  2. While tmp is not empty and tmp.peek() < x, move tmp’s top back to the input.
  3. Push x onto tmp.
  4. Finally pop everything from tmp and push it onto the input.
static void sortWithTempStack(Deque<Integer> st) {
    Deque<Integer> tmp = new ArrayDeque<>();           // invariant: sorted, smallest element on top
    while (!st.isEmpty()) {
        int x = st.pop();
        while (!tmp.isEmpty() && tmp.peek() < x) st.push(tmp.pop());  // park smaller ones back on st
        tmp.push(x);
    }
    while (!tmp.isEmpty()) st.push(tmp.pop());         // smallest goes in first, so largest ends on top
}

Dry run on Example 1 (stacks written top first):

step popped x moved back to st tmp after st after
1 41 none 41 3, 32, 2, 11
2 3 none 3, 41 32, 2, 11
3 32 3 32, 41 3, 2, 11
4 3 none 3, 32, 41 2, 11
5 2 none 2, 3, 32, 41 11
6 11 2, 3 11, 32, 41 3, 2
7 3 none 3, 11, 32, 41 2
8 2 none 2, 3, 11, 32, 41 empty

Pouring tmp back pushes 2, 3, 11, 32, 41 in that order, so the input becomes (top first) 41, 32, 11, 3, 2.

Complexity. Time O(n^2) in the worst case: an element can be moved back and forth many times (an input that arrives in the “wrong” order forces this). Space O(n) for tmp. No recursion, so no risk of overflowing the call stack.

Edge cases and pitfalls