Implement a Queue using Stacks

Implement a first-in-first-out (FIFO) queue using only two stacks. Your queue should support the standard queue operations:

• push(x): push element x to the back of the queue.
• pop(): remove and return the element at the front of the queue.
• peek(): return the element at the front of the queue without removing it.
• empty(): return true if the queue is empty, false otherwise.

You may only use standard stack operations: push to top, pop from top, peek at top, and check if a stack is empty.

Example

Input:
  push(1)
  push(2)
  peek()   # returns 1
  pop()    # returns 1
  empty()  # returns false

Constraints

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All calls to pop and peek are valid (the queue is non-empty when they are called).