Sort Values in a Stack

Sort a stack so that the smallest value is on top. You may only use stack operations (push, pop, peek, isEmpty) and at most one extra stack. You can't index into the stack or copy it into an array. In Java the stack is an ArrayDeque<Integer>: push and pop work at the head (the top), and peek reads the top without removing it. The programs print the stack from bottom to top, using descendingIterator(), which walks from the tail to the head.

Example

Text

Input  (bottom → top): [23, 60, 12, 42, 4, 97, 2]
Output (bottom → top): [97, 60, 42, 23, 12, 4, 2]     top = 2

If the stack may be copied into an ArrayList<Integer>, Collections.sort(list, Collections.reverseOrder()) sorts it in O(n log n). The question tests whether you can sort with stack operations only.

Brute force: recursive insertion

This is insertion sort, with the call stack holding elements temporarily:

sortStack: pop the top element, sort the rest recursively, then insert the popped element into its correct place.
insert: to insert x into a sorted stack (smallest on top), pop every element smaller than x, push x, then push the popped elements back. That part is recursive too.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static void insert(Deque<Integer> stack, int x) {
        if (!stack.isEmpty() && stack.peek() < x) {
            int top = stack.pop();
            insert(stack, x);
            stack.push(top);
        } else {
            stack.push(x);
        }
    }

    static void sortStack(Deque<Integer> stack) {
        if (!stack.isEmpty()) {
            int x = stack.pop();
            sortStack(stack);
            insert(stack, x);
        }
    }

    static List<Integer> bottomToTop(Deque<Integer> stack) {
        List<Integer> list = new ArrayList<>();
        stack.descendingIterator().forEachRemaining(list::add);
        return list;
    }

    static Deque<Integer> stackOf(int... values) { // the last value ends on top
        Deque<Integer> stack = new ArrayDeque<>();
        for (int v : values) stack.push(v);
        return stack;
    }

    public static void main(String[] args) {
        Deque<Integer> stack = stackOf(23, 60, 12, 42, 4, 97, 2);
        sortStack(stack);
        System.out.println(bottomToTop(stack));
    }
}

Output

[97, 60, 42, 23, 12, 4, 2]

Time: O(n²): each of the n inserts can pop up to n elements. Space: O(n) for the recursion. The call stack is effectively the extra stack.

Optimal: one temporary stack, no recursion

Keep a second stack, sorted, with the largest value on top. Pop values from the input one at a time. Before pushing value x onto sorted, move every element of sorted that's larger than x back onto the input stack, where they'll be pushed again later. When the input is empty, sorted is in order. Finally, move everything back to the original stack, which reverses it so the smallest value ends up on top.

Walkthrough with input [23, 60, 12, 42] (top is 42):

pop x	move back from `sorted` (larger than x)	`sorted` after push (bottom → top)	input (bottom → top)
42		[42]	[23, 60, 12]
12	42	[12]	[23, 60, 42]
42		[12, 42]	[23, 60]
60		[12, 42, 60]	[23]
23	60, 42	[12, 23]	[60, 42]
42		[12, 23, 42]	[60]
60		[12, 23, 42, 60]	[]

Moving back gives [60, 42, 23, 12] with 12 on top.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static void sortStack(Deque<Integer> stack) {
        Deque<Integer> sorted = new ArrayDeque<>(); // largest on top
        while (!stack.isEmpty()) {
            int x = stack.pop();
            while (!sorted.isEmpty() && sorted.peek() > x) {
                stack.push(sorted.pop());
            }
            sorted.push(x);
        }
        while (!sorted.isEmpty()) {
            stack.push(sorted.pop()); // reverses the order: smallest ends on top
        }
    }

    static List<Integer> bottomToTop(Deque<Integer> stack) {
        List<Integer> list = new ArrayList<>();
        stack.descendingIterator().forEachRemaining(list::add);
        return list;
    }

    static Deque<Integer> stackOf(int... values) { // the last value ends on top
        Deque<Integer> stack = new ArrayDeque<>();
        for (int v : values) stack.push(v);
        return stack;
    }

    public static void main(String[] args) {
        Deque<Integer> stack = stackOf(23, 60, 12, 42, 4, 97, 2);
        sortStack(stack);
        System.out.println(bottomToTop(stack));

        Deque<Integer> dups = stackOf(3, 1, 3, 2, 1);
        sortStack(dups);
        System.out.println(bottomToTop(dups));
    }
}

Output

[97, 60, 42, 23, 12, 4, 2]
[3, 3, 2, 1, 1]

Time: O(n²) in the worst case, when the input is in the order that makes every value move back. Space: O(n) for the second stack, with no recursion.

Both versions are O(n²), because a stack only gives access to its top. The iterative version cannot overflow the call stack: the recursive one uses one stack frame per element, and the depth is limited by the thread stack size. Once the stack-only constraint is lifted, copying into a list and sorting it takes O(n log n).

Edge cases

Empty stack or one element: unchanged.
Duplicates: kept, since the comparisons use strict >.
Already sorted: in the iterative version, nothing moves back, so it's O(n).