目錄：

解題及思路學習

232.用棧實現隊列

https://leetcode.cn/problems/implement-queue-using-stacks/

模擬題，用兩個棧來實現隊列的功能。

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() {// 只有當stOut為空的時候，再從stIn里導入數據（導入stIn全部數據）if (stOut.empty()) {// 從stIn導入數據直到stIn為空while(!stIn.empty()) {stOut.push(stIn.top());stIn.pop();}}int result = stOut.top();stOut.pop();return result;}/** Get the front element. */int peek() {int res = this->pop(); // 直接使用已有的pop函數stOut.push(res); // 因為pop函數彈出了元素res，所以再添加回去return res;}/** Returns whether the queue is empty. */bool empty() {return stIn.empty() && stOut.empty();}
};

• 時間復雜度: push和empty為O(1), pop和peek為O(n)
• 空間復雜度: O(n)

項目開發中，代碼復用很重要。

一定要懂得復用，功能相近的函數要抽象出來，不要大量的復制粘貼，很容易出問題！（踩過坑的人自然懂）

工作中如果發現某一個功能自己要經常用，同事們可能也會用到，自己就花點時間把這個功能抽象成一個好用的函數或者工具類，不僅自己方便，也方便了同事們。

同事們就會逐漸認可你的工作態度和工作能力，自己的口碑都是這么一點一點積累起來的！在同事圈里口碑起來了之后，你就發現自己走上了一個正循環，以后的升職加薪才少不了你！

225.?用隊列實現棧

https://leetcode.cn/problems/implement-stack-using-queues/

用兩個隊列來模擬棧，只不過沒有輸入和輸出的關系，而是另一個隊列完全用來備份的！

如下面動畫所示，用兩個隊列que1和que2實現隊列的功能，que2其實完全就是一個備份的作用，把que1最后面的元素以外的元素都備份到que2，然后彈出最后面的元素，再把其他元素從que2導回que1。

class MyStack {
public:queue<int> que1;queue<int> que2; // 輔助隊列，用來備份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que1.size();size--;while (size--) { // 將que1 導入que2，但要留下最后一個元素que2.push(que1.front());que1.pop();}int result = que1.front(); // 留下的最后一個元素就是要返回的值que1.pop();que1 = que2;            // 再將que2賦值給que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};

• 時間復雜度: push為O(n)，其他為O(1)
• 空間復雜度: O(n)

優化：隊列模擬棧，其實一個隊列就夠了。

一個隊列在模擬棧彈出元素的時候只要將隊列頭部的元素（除了最后一個元素外） 重新添加到隊列尾部，此時再去彈出元素就是棧的順序了。

class MyStack {
public:queue<int> que;/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que.size();size--;while (size--) { // 將隊列頭部的元素（除了最后一個元素外） 重新添加到隊列尾部que.push(que.front());que.pop();}int result = que.front(); // 此時彈出的元素順序就是棧的順序了que.pop();return result;}/** Get the top element. */int top() {return que.back();}/** Returns whether the stack is empty. */bool empty() {return que.empty();}
};

• 時間復雜度: push為O(n)，其他為O(1)
• 空間復雜度: O(n)

復盤總結

個人反思

很多算法題目主要是對知識點的考察和教學意義遠大于其工程實踐的意義，所以面試題也是這樣！