問題：

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 emptyoperations 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).

解決：

【注】關于測試參數的解釋：

["MyQueue","push","push","peek","pop","pop","empty"] --- 表示要進行的操作

[[],[1],[2],[],[],[],[]] --- 表示對應傳入的參數

① 使用兩個棧s1，s2，進棧的時候不做任何處理，出棧的時候把棧逆序放在另外一個棧，出另外一個棧。
之前寫經常出現空棧異常或者超時，就是沒有寫好s1，s2之間的轉換。

class MyQueue { // 87ms
? ? Stack<Integer> s1 = new Stack<>();
? ? Stack<Integer> s2 = new Stack<>();
? ? /** Initialize your data structure here. */
? ? public MyQueue() {}
? ? /** Push element x to the back of queue. */
? ? public void push(int x) {
? ? ? ? while(! s2.isEmpty()) s1.push(s2.pop());
? ? ? ? s1.push(x);
? ? }
? ? /** Removes the element from in front of queue and returns that element. */
? ? public int pop() {
? ? ? ? while(! s1.isEmpty()) s2.push(s1.pop());
? ? ? ? return s2.pop();
? ? }
? ? /** Get the front element. */
? ? public int peek() {
? ? ? ? while(! s1.isEmpty()) s2.push(s1.pop());
? ? ? ? return s2.peek();
? ? }
? ? /** Returns whether the queue is empty. */
? ? public boolean empty() {
? ? ? ? while(! s2.isEmpty()) s1.push(s2.pop());
? ? ? ? return s1.isEmpty();
? ? }
}
/**
?* Your MyQueue object will be instantiated and called as such:
?* MyQueue obj = new MyQueue();
?* obj.push(x);
?* int param_2 = obj.pop();
?* int param_3 = obj.peek();
?* boolean param_4 = obj.empty();
?*/

② 使用兩個棧，在進棧的時候，把棧逆序放在另外一個棧，出的時候直接出另外一個棧就可以了。

class MyQueue { //93ms
? ? Stack<Integer> s1 = new Stack<>();
? ? Stack<Integer> s2 = new Stack<>();
? ? /** Initialize your data structure here. */
? ? public MyQueue() {}
? ? /** Push element x to the back of queue. */
? ? public void push(int x) {
? ? ? ? while(! s1.isEmpty()) s2.push(s1.pop());
? ? ? ? s2.push(x);
? ? ? ? while(! s2.isEmpty()) s1.push(s2.pop());
? ? }
? ? /** Removes the element from in front of queue and returns that element. */
? ? public int pop() {
? ? ? ? return s1.pop();
? ? }
? ? /** Get the front element. */
? ? public int peek() {
? ? ? ? return s1.peek();
? ? }
? ? /** Returns whether the queue is empty. */
? ? public boolean empty() {
? ? ? ? return s1.isEmpty();
? ? }
}

③ 除了使用兩個棧之外，額外使用一個指針指向頭部。

class MyQueue { //113ms
? ? Stack<Integer> s1 = new Stack<>();
? ? Stack<Integer> s2 = new Stack<>();
? ? int head;
? ? /** Initialize your data structure here. */
? ? public MyQueue() {}
? ? /** Push element x to the back of queue. */
? ? public void push(int x) {
? ? ? ? if(s1.isEmpty()) head = x;
? ? ? ? s1.push(x);
? ? }
? ? /** Removes the element from in front of queue and returns that element. */
? ? public int pop() {
? ? ? ? while(! s1.isEmpty()) s2.push(s1.pop());
? ? ? ? int top = -1;
? ? ? ? if(! s2.isEmpty()){
? ? ? ? ? ? top = s2.pop();
? ? ? ? ? ? if(! s2.isEmpty()) head = s2.peek();
? ? ? ? }
? ? ? ? while(! s2.isEmpty()) s1.push(s2.pop());
? ? ? ? return top;
? ? }
? ? /** Get the front element. */
? ? public int peek() {
? ? ? ? return head;
? ? }
? ? /** Returns whether the queue is empty. */
? ? public boolean empty() {
? ? ? ? return s1.isEmpty();
? ? }
}