代码随想录算法训练营Day10 | LeetCode232.用栈实现队列、LeetCode225.用队列实现栈

LeetCode232.用栈实现队列

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/

思路：用两个栈：一个输入栈，一个输出栈，来模拟队列的各个操作。在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

C++代码如下：

class MyQueue 
{
public:
    stack<int> stack_in;
    stack<int> stack_out;

    MyQueue()   //构造函数
    {

    }
    //将一个元素放到队尾
    void push(int x) 
    {
        stack_in.push(x);
    }
    //从队首移除元素
    int pop() 
    {
        if(!stack_out.empty())
        {
            int result = stack_out.top();
            stack_out.pop();
            return result;
        }
        else
        {
            while(!stack_in.empty())
            {
                int tmp = stack_in.top();
                stack_out.push(tmp);
                stack_in.pop();
            }
            int result = stack_out.top();
            stack_out.pop();
            return result;
        }
    }
    //返回队首元素(不移除)
    int peek() 
    {
        if(!stack_out.empty())
        {
            int result = stack_out.top();
            return result;
        }
        else
        {
            while(!stack_in.empty())
            {
                int tmp = stack_in.top();
                stack_out.push(tmp);
                stack_in.pop();
            }
            int result = stack_out.top();
            return result;
        }
    }
    //判断是否为空
    bool empty() 
    {
        if(stack_in.empty() && stack_out.empty())
        {
            return true;
        }
        else
        {
            return false;
        }

    }
};

LeetCode225.用队列实现栈

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/

思路：用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

C++代码如下：

class MyStack {
public:
    queue<int> que1;
    queue<int> que2; //辅助

    MyStack() 
    {

    }
    //传入
    void push(int x) 
    {
        que1.push(x);
    }

    //移除
    int pop() 
    {
        while(que1.size() != 1)
        {
            int tmp = que1.front();
            que1.pop();
            que2.push(tmp);
        }
        int result = que1.front();
        que1.pop();
        while(!que2.empty())
        {
            int tmp = que2.front();
            que2.pop();
            que1.push(tmp);
        }
        return result;
    }

    //返回栈顶元素（不移除）
    int top() 
    {
        while(que1.size()!=1)
        {
            int tmp = que1.front();
            que1.pop();
            que2.push(tmp);
        }
        int result = que1.front();
        que1.pop();
        que2.push(result);
        while(!que2.empty())
        {
            int tmp = que2.front();
            que2.pop();
            que1.push(tmp);
        }
        return result;
    }
    //判断是否为空
    bool empty() 
    {
        return (que1.empty() && que2.empty());
    }
};