Day9——用栈实现队列、用队实现拟栈

今天是算法训练的第9天

目录

前言

题目来源：

解题思路：

二、用队列模拟栈

题目来源：

解题思路1（双队列）：

解题思路2（循环队列）：

总结

---

前言

今日文案：

已是悲秋之境，又何以有悲秋之心，不忍在这深秋里独自忧思，因而更愿意让一切伤秋之感随深秋沉淀，埋藏在这季节的最深处，不再萌发伤感之意。

---

一、用栈实现队列

题目来源：

力扣

解题思路：

栈的特点：先入后出，后入先出，就是一层一层铺上去，只能从上面开始吃。

队列特点：顾名思义，排队，先到先出。

那用栈来实现我们要怎么做，如果一碗饭，我们想从最下面吃起来，我们只需要找多一个碗，然后把饭盖过去，不就是底层变表层，表层变底层了吗。栈也是如此，创建两个栈就可以实现。

代码如下：

class MyQueue {
public:
    stack<int> st1;        //创建两个栈
    stack<int> st2;
 
    MyQueue() {
 
    }
    
    void push(int x) {
        st1.push(x);        //1栈插入元素
    }
    
    int pop() {
        if(st2.empty())        //如果2栈是空的，直接全盘接受1栈的饭
        {
            while(!st1.empty())        //知道1栈变空
            {
                st2.push(st1.top());        //插入1栈的头
                st1.pop();                //1栈去头，这样就是一层一层扒下来了
            }
        }
        int w=st2.top();            //接受2栈头元素
        st2.pop();                //去头，为下次做准备
        return w;
    }
    
    int peek() {
        int res = pop();        //这里只有一个点，为什么不直接返会st2.top()，因为2可能没东西
        st2.push(res); 
        return res;
    }
    
    bool empty() {
        return st2.empty()&&st1.empty();    
    }
};

---

二、用队列模拟栈

题目来源：

力扣

解题思路1（双队列）：

开两条队列，让需要出去的元素出去，这就像是一条堵车的车道，旁边有一块空地，每次后面的车要出去了，就去另外一块空地呆着，让后面的车出去。这种办法比较冗余。

解题思路2（循环队列）：

上面的方法是走去外面的空地等，所有有两条队，那我们如果可以让前面的人走到队尾重新排队，不就需要一条队伍了吗。

代码如下：

class MyStack {
public:
    queue<int> que;
    MyStack() {
    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size=que.size();    
        size--;                //减1，留下最后那个
        while(size--)
        {
            que.push(que.front());    //重新排队
            que.pop();
        }
        int ans=que.front();    //重新排好后，第一位就是原来的最后一位
        que.pop();
        return ans;
    } 
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

---

总结

今天的内容就这么多，只是简单了解了一下队列，加油！！1