Implement 2 stack in an array

The problem, simply

You get one array of size n. Build two stacks inside it. You need push1, pop1, push2 and pop2.

The catch: the array should only be "full" when all n boxes are used. If stack 1 is empty, stack 2 should be allowed to use every box.

A story to remember it

Picture it

Examples

Way 1: the simple way

Cut the array in half. Stack 1 lives in boxes 0 to n/2 - 1. Stack 2 lives in boxes n/2 to n - 1. Each half works like a normal array stack.

1. top1 starts at -1. top2 starts at n/2 - 1.
2. push1 fails when top1 reaches n/2 - 1. push2 fails when top2 reaches n - 1.

class TwoStacksHalves {
    private final int[] arr;
    private final int mid;
    private int top1, top2;

    TwoStacksHalves(int n) {
        arr = new int[n];
        mid = n / 2;
        top1 = -1;          // stack 1 uses 0 .. mid-1
        top2 = mid - 1;     // stack 2 uses mid .. n-1
    }

    void push1(int x) {
        if (top1 == mid - 1) throw new RuntimeException("stack 1 overflow");
        arr[++top1] = x;
    }

    void push2(int x) {
        if (top2 == arr.length - 1) throw new RuntimeException("stack 2 overflow");
        arr[++top2] = x;
    }

    int pop1() {
        if (top1 < 0) throw new RuntimeException("stack 1 underflow");
        return arr[top1--];
    }

    int pop2() {
        if (top2 < mid) throw new RuntimeException("stack 2 underflow");
        return arr[top2--];
    }
}

How long it takes: every action is O(1). Extra room: the array of n, but each stack can only ever hold n/2 items, so half the room may be wasted.

Way 2: the clever way

Grow the two stacks toward each other.

1. top1 starts at -1, just left of the array. top2 starts at n, just right of it.
2. push1(x): if top1 + 1 == top2, the piles touch, so overflow. Else arr[++top1] = x.
3. push2(x): same check. Else arr[--top2] = x.
4. pop1(): if top1 == -1 it is empty. Else return arr[top1--].
5. pop2(): if top2 == n it is empty. Else return arr[top2++].

The free space is always the gap between top1 and top2, and either stack may take it.

class TwoStacks {
    private final int[] arr;
    private int top1, top2;

    TwoStacks(int n) {
        arr = new int[n];
        top1 = -1;          // just left of the array
        top2 = n;           // just right of the array
    }

    void push1(int x) {
        if (top1 + 1 == top2) throw new RuntimeException("overflow");
        arr[++top1] = x;    // grow to the right
    }

    void push2(int x) {
        if (top1 + 1 == top2) throw new RuntimeException("overflow");
        arr[--top2] = x;    // grow to the left
    }

    int pop1() {
        if (top1 == -1) throw new RuntimeException("stack 1 underflow");
        return arr[top1--];
    }

    int pop2() {
        if (top2 == arr.length) throw new RuntimeException("stack 2 underflow");
        return arr[top2++];
    }

    int size1() { return top1 + 1; }

    int size2() { return arr.length - top2; }
}

How long it takes: every action is O(1). Extra room: the one array of n, and every box can be used by either stack.

Watch out for

• Stack 2 moves the other way. Push is arr[--top2] (step left first), pop is arr[top2++] (read, then step right). Swapping the order of -- and the read is the most common slip.
• Stack 2 is empty when top2 == n, not when top2 == -1.
• Size of stack 2 is n - top2.

What interviewers ask next

• Can you put three stacks in one array the same way? Not with this trick. There are only two ends. For k stacks, link free boxes together in a chain, which is the "n stacks in an array" problem.
• What if a stack grows past the array? Make a bigger array, copy stack 1 to its left side and stack 2 to its right side, and fix top2.
• Can a queue and a stack share an array like this? A stack from one end works, but a queue moves at both of its ends, so it drifts. It is messy and rarely worth it.
• Where is this used? Old compilers and some memory managers put two growing areas, like the call stack and the heap, at opposite ends of memory for the same reason.

Remember this

Grown-up words: the shelf is the array, each toy pile is a stack, the two walls are the two ends of the array, top1 and top2 are the top indices, and running out of room is overflow.