目錄

1.題目描述

2.思路

3.代碼展示

4.用隊列實現棧

4.1題目描述

4.2思路

4.3代碼實現

---

---

1.題目描述

2.思路

思路是很清晰的，棧是先進后出，而隊列是先進先出，所以要用棧實現隊列，就必須用到兩個棧，一個輸入棧，一個輸出棧

在push數據的時候，只要數據放進輸入棧就好，「但在pop的時候，操作就復雜一些，輸出棧如果為空，就把進棧數據全部導入進來（注意是全部導入）」，再從出棧彈出數據，如果輸出棧不為空，則直接從出棧彈出數據就可以了。

如果進棧和出棧都為空的話，說明模擬的隊列為空了。

3.代碼展示

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里導入數據（導入strIn全部數據）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();} };/*** 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();*/

其實思路還是好理解的，實現起來也不復雜，建議以后大家寫文章粘貼代碼的時候附上運行的截圖，這樣大家看起來方便，也有助于自己回顧。

4.用隊列實現棧

4.1題目描述

4.2思路

前面已經介紹了棧和隊列兩者的特性了，用棧實現隊列就很簡單了，相反的，用隊列也能實現棧，也是需要兩個隊列，還是一個輸入隊列一個輸出隊列嗎？

當然不是這樣的，隊列是先進先出的規則，把一個隊列中的數據導入另一個隊列中，數據的順序并沒有變，并有變成先進后出的順序。

所以用棧實現隊列， 和用隊列實現棧的思路還是不一樣的，這取決于這兩個數據結構的性質。

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

4.3代碼實現

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賦值給que1;while (!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();} };/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

總結

以上是生活随笔為你收集整理的用栈实现队列（Leetcode第232题）+用队列实现栈（Leetcode第225题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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