Stack/queue conversions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Pushing elements (1, 2, 3):
  inStack:  [ 1, 2, 3 ] (top is 3)
  outStack: [ ]

When pop() or peek() is called:
If outStack is empty, transfer ALL elements from inStack to outStack:
  Pop 3 from inStack -> Push to outStack
  Pop 2 from inStack -> Push to outStack
  Pop 1 from inStack -> Push to outStack

Now:
  inStack:  [ ]
  outStack: [ 3, 2, 1 ] (top is 1! Exactly the FIFO order!)

Subsequent pop() simply pops from outStack in O(1)!
Amortized Cost per operation: O(1) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class MyQueue {
    private Deque<Integer> inStack = new ArrayDeque<>();
    private Deque<Integer> outStack = new ArrayDeque<>();

    public void push(int x) {
        inStack.push(x); // O(1)
    }

    public int pop() {
        moveIfEmpty();
        return outStack.pop(); // Amortized O(1)
    }

    public int peek() {
        moveIfEmpty();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void moveIfEmpty() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}