Implement Queue using Stacks

1. The obvious way

   On every pop, pour everything into a helper stack and back: O(n) per pop.

2. The key insight

   Use an in-stack for pushes and an out-stack for pops. Only when the out-stack is empty, move every item from the in-stack to it (this reverses them so the oldest is on top). Each item is moved at most once, so pops cost O(1) on average.

3. The algorithm
   1. push: put the item on the in-stack.
   2. pop/peek: if the out-stack is empty, move all items from the in-stack to it one by one.
   3. Then take (or look at) the top of the out-stack.
   4. empty: true when both stacks are empty.

Watch it run

in: 1, 2    out: (empty)

class MyQueue:
    def __init__(self):
        self.in_pile = []          # new items land here
        self.out_pile = []         # items leave from here, oldest on top

    def push(self, x):
        self.in_pile.append(x)

    def _fill_out(self):
        if not self.out_pile:                    # only pour when it has run out
            while self.in_pile:
                self.out_pile.append(self.in_pile.pop())

    def pop(self):
        self._fill_out()
        return self.out_pile.pop()

    def peek(self):
        self._fill_out()
        return self.out_pile[-1]

    def empty(self):
        return not self.in_pile and not self.out_pile

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.