題目描述:
請你僅使用兩個(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
說明:
- 你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有
push to top , peek/pop from top , size , 和 is empty 操作是合法的。 - 你所使用的語言也許不支持棧,。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧,，只要是標(biāo)準(zhǔn)的棧操作即可。
進(jìn)階:
你能否實(shí)現(xiàn)每個(gè)操作均攤時(shí)間復(fù)雜度為 O(1) 的隊(duì)列,？換句話說,，執(zhí)行 n 個(gè)操作的總時(shí)間復(fù)雜度為 O(n) ，即使其中一個(gè)操作可能花費(fèi)較長時(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
提示:
- 最多調(diào)用
100 次 push ,、 pop 、 peek 和 empty - 假設(shè)所有操作都是有效的 （例如,，一個(gè)空的隊(duì)列不會(huì)調(diào)用
pop 或者 peek 操作）
題目分析:
這道題可以使用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列,。其中一個(gè)棧用作輸入棧，當(dāng)有數(shù)據(jù)要進(jìn)入隊(duì)列時(shí),，直接把該數(shù)據(jù)壓入輸入棧中,。另一個(gè)棧用作輸出棧，當(dāng)要獲取隊(duì)列頭元素或者隊(duì)列頭元素要出隊(duì)列時(shí),，就獲取輸出棧的最頂端元素或者把最頂端元素彈出,。當(dāng)然，每次執(zhí)行獲取隊(duì)列頭元素或者隊(duì)列頭元素要出隊(duì)列操作前,，都需要檢查輸出棧是否為空,，如果為空，就需要把輸入棧的所有元素先翻轉(zhuǎn)壓入輸出棧,，這樣輸出棧從棧頂往棧底的順序就是隊(duì)列從隊(duì)首往隊(duì)尾的順序,。最后，判斷隊(duì)列是否為空的方法就是直接判斷兩個(gè)棧是否都為空,，如果都為空就表明該隊(duì)列為空,。
題解:
執(zhí)行用時(shí): 0 ms
內(nèi)存消耗: 36.3 MB
class MyQueue {
// 創(chuàng)建兩個(gè)棧 一個(gè)入棧一個(gè)出棧
Stack<Integer> in, out;
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
// 添加進(jìn)隊(duì)列方法
public void push(int x) {
// 直接把元素壓入入棧
in.push(x);
}
// 出隊(duì)列方法
public int pop() {
// 把入棧的元素翻轉(zhuǎn)進(jìn)出棧
inToOut();
// 獲取出棧最頂端元素值
int x = out.peek();
// 把該元素彈出
out.pop();
// 返回彈出的元素值即隊(duì)頭值
return x;
}
// 獲取隊(duì)列頭元素方法
public int peek() {
// 把入棧的元素翻轉(zhuǎn)進(jìn)出棧
inToOut();
// 返回出棧最頂端元素值
return out.peek();
}
// 判斷隊(duì)列是否為空方法
public boolean empty() {
// 如果入棧和出棧都為空，隊(duì)列就是空的
return in.empty() && out.empty();
}
// 把入棧的元素翻轉(zhuǎn)進(jìn)出棧的方法
public void inToOut() {
// 如果出棧為空才進(jìn)行翻轉(zhuǎn)操作
// 出棧不為空,，后進(jìn)隊(duì)列的元素直接壓進(jìn)入棧
// 對出棧沒有任何影響
if (out.empty()) {
// 把入棧所有元素壓入出棧
while (!in.empty()) {
// 獲取入棧最頂端元素值
int x = in.peek();
// 把該元素彈出
in.pop();
// 把該元素壓入出棧
out.push(x);
}
}
}
}
/**
* 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();
*/
