Deque — Interview Preparation¶

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

/**
 * Deque implemented with two stacks.
 *
 * Amortised O(1) per operation. The rebalance moves half of the elements
 * from the non-empty stack to the empty stack in reversed order, preserving
 * deque ordering.
 */
public class TwoStackDeque {

    // Top of front = front of deque.
    // Top of back  = back of deque.
    private final Deque<Integer> front = new ArrayDeque<>();
    private final Deque<Integer> back  = new ArrayDeque<>();

    public void pushFront(int x) { front.push(x); }
    public void pushBack(int x)  { back.push(x); }

    public int popFront() {
        if (front.isEmpty()) rebalanceInto(front, back);
        if (front.isEmpty()) throw new NoSuchElementException("empty");
        return front.pop();
    }

    public int popBack() {
        if (back.isEmpty()) rebalanceInto(back, front);
        if (back.isEmpty()) throw new NoSuchElementException("empty");
        return back.pop();
    }

    public int size() { return front.size() + back.size(); }
    public boolean isEmpty() { return front.isEmpty() && back.isEmpty(); }

    /**
     * Move half (rounded up) of source into target, reversing.
     * Reversal is what makes the order correct: the bottom of source
     * becomes the top of target.
     */
    private void rebalanceInto(Deque<Integer> target, Deque<Integer> source) {
        if (source.isEmpty()) return;

        int half = (source.size() + 1) / 2;

        // Drain source into a temporary list to access its bottom.
        Integer[] arr = source.toArray(new Integer[0]);
        // arr[0] is the top, arr[arr.length - 1] is the bottom.

        // Move the bottom `half` elements (from arr[arr.length - half] to arr[arr.length - 1])
        // to target, in order. That puts the deepest into target first, so it ends up at
        // the bottom of target — which is correct because the deepest of source is closest
        // to "the other end" of the deque.
        source.clear();
        for (int i = 0; i < arr.length - half; i++) {
            source.push(arr[arr.length - 1 - i]);  // re-push top elements back, reversed twice = original order
        }
        // Wait — pushing reverses. Let us redo cleanly:
        source.clear();
        // Push the top (arr.length - half) elements back onto source, in reverse iteration
        // so they come out in original top-to-bottom order.
        for (int i = arr.length - half - 1; i >= 0; i--) {
            source.push(arr[i]);
        }
        // Now push the bottom `half` elements onto target. We want target's top to be
        // the element that was deepest in source (next to the "other end" of the deque).
        for (int i = arr.length - 1; i >= arr.length - half; i--) {
            target.push(arr[i]);
        }
    }

    public static void main(String[] args) {
        TwoStackDeque d = new TwoStackDeque();
        d.pushBack(1);
        d.pushBack(2);
        d.pushBack(3);
        d.pushFront(0);
        // Deque is [0, 1, 2, 3] front to back.
        System.out.println(d.popFront()); // 0
        System.out.println(d.popBack());  // 3
        System.out.println(d.popFront()); // 1
        System.out.println(d.popBack());  // 2
    }
}