面试题 03.04. 化栈为队

  1. class MyQueue {
  2.     Deque<Integer> instack;
  3.     Deque<Integer> outStack;
  4.     /** Initialize your data structure here. */
  5.     public MyQueue() {
  6.         instack = new LinkedList<>();
  7.         outStack = new LinkedList<>();
  8.     }
  10.     /** Push element x to the back of queue. */
  11.     public void push(int x) {
  12.         instack.push(x);
  13.     }
  15.     /** Removes the element from in front of queue and returns that element. */
  16.     public int pop() {
  17.         if (outStack.isEmpty()) {
  18.             inToOut();
  19.         }
  21.         return outStack.pop();
  22.     }
  24.     /** Get the front element. */
  25.     public int peek() {
  26.         if (outStack.isEmpty()) {
  27.             inToOut();
  28.         }
  30.         return outStack.peek();
  31.     }
  33.     private void inToOut() {
  34.         while (!instack.isEmpty()) {
  35.             outStack.push(instack.pop());
  36.         }
  37.     }
  39.     /** Returns whether the queue is empty. */
  40.     public boolean empty() {
  41.         return instack.isEmpty() && outStack.isEmpty();
  42.     }
  43. }
  45. /**
  46.  * Your MyQueue object will be instantiated and called as such:
  47.  * MyQueue obj = new MyQueue();
  48.  * obj.push(x);
  49.  * int param_2 = obj.pop();
  50.  * int param_3 = obj.peek();
  51.  * boolean param_4 = obj.empty();
  52.  */