Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) — Push element x to the back of queue.
  • pop() — Removes the element from in front of queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

Notes:

  • You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution:

  1. class MyQueue {
  2.   Stack<Integer> s1 = new Stack<>();
  3.   Stack<Integer> s2 = new Stack<>();
  5.   // Push element x to the back of queue.
  6.   public void push(int x) {
  7.     s1.push(x);
  8.   }
  10.   // Removes the element from in front of queue.
  11.   public void pop() {
  12.     peek();
  13.     s2.pop();
  14.   }
  16.   // Get the front element.
  17.   public int peek() {
  18.     if (s2.isEmpty()) {
  19.       while (!s1.isEmpty()) {
  20.         s2.push(s1.pop());
  21.       }
  22.     }
  24.     return s2.peek();
  25.   }
  27.   // Return whether the queue is empty.
  28.   public boolean empty() {
  29.     return s1.isEmpty() && s2.isEmpty();
  30.   }
  31. }