題目描述
請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列的支持的所有操作（push、pop、peek、empty）：
實(shí)現(xiàn) MyQueue 類：
void push(int x) 將元素 x 推到隊(duì)列的末尾
int pop() 從隊(duì)列的開頭移除并返回元素
int peek() 返回隊(duì)列開頭的元素
boolean empty() 如果隊(duì)列為空撩嚼，返回 true ；否則挖帘，返回 false
說(shuō)明：
你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的完丽。
你所使用的語(yǔ)言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可。
進(jìn)階：
你能否實(shí)現(xiàn)每個(gè)操作均攤時(shí)間復(fù)雜度為 O(1) 的隊(duì)列掠抬？換句話說(shuō)，執(zhí)行 n 個(gè)操作的總時(shí)間復(fù)雜度為 O(n) 聘鳞，即使其中一個(gè)操作可能花費(fèi)較長(zhǎng)時(shí)間。
示例：
輸入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 1, 1, false]
解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多調(diào)用 100 次 push要拂、pop抠璃、peek 和 empty
假設(shè)所有操作都是有效的 （例如，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）
數(shù)據(jù)結(jié)構(gòu)
- 棧
算法思維
- 棧操作
解題要點(diǎn)
- 棧的 LIFO 特性
- 隊(duì)列的 FIFO 特性
解題思路
一. Comprehend 理解題意
- 需要自實(shí)現(xiàn)一個(gè)隊(duì)列
- 只能使用兩個(gè)棧作為數(shù)據(jù)結(jié)構(gòu)
- 只能使用棧操作（push(x), pop(), peek(), isEmpty()）來(lái)實(shí)現(xiàn)隊(duì)列功能
二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法
解法一：兩棧相互 壓入/彈出 元素
- 數(shù)據(jù)結(jié)構(gòu)：棧
- 算法思維：棧操作
三. Code 編碼實(shí)現(xiàn)基本解法
class MyQueue {
Stack < Integer > s1; //入隊(duì)所用的 push 棧
Stack < Integer > s2; //出隊(duì)所用的 pop 棧
/**
* Initialize your data structure here.
*/
public MyQueue() {
s1 = new Stack < > ();
s2 = new Stack < > ();
}
/**
* Push element x to the back of queue.
*/
public void push(int x) {
//1.入隊(duì)前脱惰，先將s2中的所有元素移入s1中
while(!s2.isEmpty()) {
s1.push(s2.pop());
}
//2.入隊(duì) == 入s1棧
s1.push(x);
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {
//3.出隊(duì)前搏嗡，先將s1中的所有元素移入s2中
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
//4.出隊(duì) == 出s2棧
return s2.pop();
}
/**
* Get the front element.
*/
public int peek() {
//5.查詢隊(duì)首，與出隊(duì)類似,先將s1中的所有元素移入s2中
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
//6.查詢隊(duì)首 == 查詢s2棧頂
return s2.peek();
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {
//7.空隊(duì)為空 == s1和s2同時(shí)為空
return s1.isEmpty() && s2.isEmpty();
}
}
執(zhí)行耗時(shí)：0 ms拉一，擊敗了 100.00% 的Java用戶
內(nèi)存消耗：36.1 MB采盒，擊敗了 92.05% 的Java用戶
時(shí)間復(fù)雜度：O(n2) -- 每次出入隊(duì)都執(zhí)行1次棧的遍歷 O(n2)，出入棧操作 O(1)
空間復(fù)雜度：O(n) -- 棧的內(nèi)存空間 O(n)
四. Consider 思考更優(yōu)解
優(yōu)化代碼結(jié)構(gòu)
改變算法思維
借鑒其他算法
思路：
方法：
解法二：XXX
- 數(shù)據(jù)結(jié)構(gòu)：
- 算法思維：
五. Code 編碼實(shí)現(xiàn)最優(yōu)解
執(zhí)行耗時(shí)：
內(nèi)存消耗：
時(shí)間復(fù)雜度：O() --
空間復(fù)雜度：O() --
六. Change 變形與延伸
=== 待續(xù) ===
