題目

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列的支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false
說明：
你只能使用標準的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。
進階：
你能否實現每個操作均攤時間復雜度為 O(1) 的隊列？換句話說，執行 n 個操作的總時間復雜度為 O(n) ，即使其中一個操作可能花費較長時間。

參考別人思路，使用雙棧思想

push數據：把數據放進輸入棧

pop數據:

輸出棧如果為空，就把輸入棧數據全部導入，再從輸出棧彈出數據

如果輸出棧不為空，則直接從輸出棧彈出數據就可以了。

如何判斷隊列為空：如果輸入棧和輸出棧都為空，則說明模擬的隊列為空。

代碼

class MyQueue { public:stack<int> stIn;stack<int> stOut;/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {stIn.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {//如果輸出棧為空if(stOut.empty()){//就把數據全部導入while(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}//從輸出棧彈出數據int result =stOut.top();stOut.pop();return result;}/** Get the front element. */int peek() {//直接使用已有pop函數int res = this->pop();//因為pop()函數彈出了元素res，所以還得再添加回去stOut.push(res);return res;}/** Returns whether the queue is empty. */bool empty() {return stIn.empty() && stOut.empty();} };/*** 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();* bool param_4 = obj->empty();*/

總結

以上是生活随笔為你收集整理的leetcode 232. 用栈实现队列 思考分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。