代码随想录算法训练营第10天

标签：10 队列 训练营 随想录 pop que1 int que2 empty

今日刷题2道：先简单复习了栈和队列的理论基础，然后做题：232.用栈实现队列，225. 用队列实现栈。

ps:昨天不想学习，所以今天补回来，出来混总是要还的啊。

●  232.用栈实现队列

题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

 碎碎念：栈是先进后出，队列是先进先出，用栈实现队列的话，就需要用两个栈，将数据输入到第一个栈内，然后将出栈结果放到第二个栈里即可，这样再出栈得到的结果就和队列一样了。

class MyQueue { public:     stack<int> stIn;     stack<int> stOut;     MyQueue() {           }         void push(int x) {         stIn.push(x);     }         int pop() {         if(stOut.empty()){             while(!stIn.empty()){                 stOut.push(stIn.top());                 stIn.pop();             }         }         int result = stOut.top();         stOut.pop();         return result;     }         int peek() {         int res = this -> pop();         stOut.push(res);         return res;     }         bool empty() {         return stIn.empty() && stOut.empty();     } };

●  225. 用队列实现栈

题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

 碎碎念：用队列实现栈有两种方法，常规的是用两个队列去实现，用两个队列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赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};

一个队列实现：

class MyStack { public:     queue<int> que;     MyStack() {
    }         void push(int x) {         que.push(x);     }         int pop() {         int size = que.size();         size--;         while(size--){             que.push(que.front());             que.pop();         }         int result = que.front();         que.pop();         return result;     }         int top() {         return que.back();     }         bool empty() {         return que.empty();     } };

标签：10,队列,训练营,随想录,pop,que1,int,que2,empty
From： https://www.cnblogs.com/zzw0612/p/17032241.html