Implement Two Stacks Using One Array

Implement two stacks that share a single int[] of fixed capacity. Support:

push1(x) and push2(x): push onto stack 1 or stack 2. Return false if there's no room.
pop1() and pop2(): pop from stack 1 or stack 2. Return an OptionalInt (a container that holds either one int or nothing): OptionalInt.empty() if that stack is empty.

A push should fail only when the whole array is full, not when one stack's share of it is.

Example

Text

capacity = 4
push1(1), push1(2), push1(3)   -> true, true, true
push2(9)                       -> true    (array now full: [1, 2, 3, 9])
push2(8)                       -> false
pop1(), pop2(), pop2()         -> 3, 9, empty

Brute force: split the array in half

Give stack 1 the slots [0, cap/2) and stack 2 the slots [cap/2, cap). Each stack tracks its own length. The notation data[a..b) means the indexes from a up to, but not including, b.

This works, but if stack 1 is busy and stack 2 is empty, stack 1 reports "full" while half the array is unused.

Java

import java.util.OptionalInt;

public class Main {
    static class TwoStacks {
        private final int[] data;
        private int len1 = 0;
        private int len2 = 0;

        TwoStacks(int cap) {
            data = new int[cap];
        }

        private int half() {
            return data.length / 2;
        }

        boolean push1(int x) {
            if (len1 == half()) return false;
            data[len1] = x;
            len1++;
            return true;
        }

        boolean push2(int x) {
            if (len2 == data.length - half()) return false;
            data[half() + len2] = x;
            len2++;
            return true;
        }

        OptionalInt pop1() {
            if (len1 == 0) return OptionalInt.empty();
            len1--;
            return OptionalInt.of(data[len1]);
        }

        OptionalInt pop2() {
            if (len2 == 0) return OptionalInt.empty();
            len2--;
            return OptionalInt.of(data[half() + len2]);
        }
    }

    public static void main(String[] args) {
        TwoStacks s = new TwoStacks(4);
        System.out.println(s.push1(1) + " " + s.push1(2) + " " + s.push1(3)); // third push fails: half is full
        System.out.println(s.push2(9) + " " + s.pop1() + " " + s.pop2() + " " + s.pop2());
    }
}

Output

true true false
true OptionalInt[2] OptionalInt[9] OptionalInt.empty

Time: O(1) per operation. Space: O(n), but up to half of it can be unusable.

Optimal: grow the stacks toward each other

Stack 1 starts at the left end and grows right. Stack 2 starts at the right end and grows left. The free space is always the gap in the middle, shared by both, so the array is full only when the two tops meet.

Text

capacity 7, after push1(1), push1(2), push2(9), push2(8):

index:  0   1   2   3   4   5   6
       [1,  2,  _,  _,  _,  8,  9]
            ^len1 = 2       ^top2 = 5
stack 1 = data[0..2)         stack 2 = data[5..7) (top at index 5)

Stack 1 uses data[0..len1), and its top is at len1 - 1.
Stack 2 uses data[top2..cap), and its top is at top2. It's empty when top2 == cap.
The array is full when len1 == top2.

Java

import java.util.OptionalInt;

public class Main {
    static class TwoStacks {
        private final int[] data;
        private int len1; // stack 1 occupies data[0..len1)
        private int top2; // stack 2 occupies data[top2..cap)

        TwoStacks(int cap) {
            data = new int[cap];
            len1 = 0;
            top2 = cap;
        }

        boolean isFull() {
            return len1 == top2;
        }

        boolean push1(int x) {
            if (isFull()) return false;
            data[len1] = x;
            len1++;
            return true;
        }

        boolean push2(int x) {
            if (isFull()) return false;
            top2--;
            data[top2] = x;
            return true;
        }

        OptionalInt pop1() {
            if (len1 == 0) return OptionalInt.empty();
            len1--;
            return OptionalInt.of(data[len1]);
        }

        OptionalInt pop2() {
            if (top2 == data.length) return OptionalInt.empty();
            top2++;
            return OptionalInt.of(data[top2 - 1]);
        }
    }

    public static void main(String[] args) {
        TwoStacks s = new TwoStacks(4);
        System.out.println(s.push1(1) + " " + s.push1(2) + " " + s.push1(3)); // all fit now
        System.out.println(s.push2(9) + " " + s.push2(8));                    // only one slot was left
        System.out.println(s.pop1() + " " + s.pop2() + " " + s.pop2());
    }
}

Output

true true true
true false
OptionalInt[3] OptionalInt[9] OptionalInt.empty

Time: O(1) per operation. Space: O(n), and every slot is usable by either stack.

Storing a length (len1) and an exclusive boundary (top2) instead of top indices that start at -1 keeps the empty checks simple: len1 == 0 and top2 == data.length. Each pop checks for empty before changing its counter, so a failed pop leaves the stack unchanged.

Edge cases

Capacity 0: every push fails and every pop returns OptionalInt.empty().
Pop from an empty stack: OptionalInt.empty(), whatever the other stack holds.
One stack using the whole array: allowed in the optimal version.