為什么80%的碼農(nóng)都做不了架構(gòu)師？>>> ??

問(wèn)題：

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

解決：

【注】關(guān)于測(cè)試參數(shù)的解釋：

["MyQueue","push","push","peek","pop","pop","empty"] --- 表示要進(jìn)行的操作

[[],[1],[2],[],[],[],[]] --- 表示對(duì)應(yīng)傳入的參數(shù)

① 使用兩個(gè)棧s1，s2，進(jìn)棧的時(shí)候不做任何處理，出棧的時(shí)候把棧逆序放在另外一個(gè)棧，出另外一個(gè)棧。
之前寫(xiě)經(jīng)常出現(xiàn)空棧異常或者超時(shí)，就是沒(méi)有寫(xiě)好s1，s2之間的轉(zhuǎn)換。

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();
?*/

② 使用兩個(gè)棧，在進(jìn)棧的時(shí)候，把棧逆序放在另外一個(gè)棧，出的時(shí)候直接出另外一個(gè)棧就可以了。

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();
? ? }
}

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

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();
? ? }
}

轉(zhuǎn)載于:https://my.oschina.net/liyurong/blog/1512615

總結(jié)

以上是生活随笔為你收集整理的使用栈实现队列 Implement Queue using Stacks的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。