【代码随想录算法训练营Day10】栈与队列理论基础；232.用栈实现队列；225.用队列实现栈

❇️Day 10 第五章 栈与队列 part01

✴️今日任务：

• 理论基础
• 232.用栈实现队列
• 225.用队列实现栈

⏺️理论基础

• 了解一下 栈与队列的内部实现机制，文中是以C++为例讲解的。
• 文章讲解：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

队列是先进先出，栈是先进后出。
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

❇️232.用栈实现队列

• 大家可以先看视频，了解一下模拟的过程，然后写代码会轻松很多。
• 题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/
• 视频讲解：https://www.bilibili.com/video/BV1nY4y1w7VC/
• 文章讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

随想录思路

用两个栈来实现队列（双栈模拟队列）

• 入队列操作：把元素直接添加到栈s1就可以
• 出队列操作：需要把栈s1中所有元素都放到栈s2中再进行出队列操作

自己的代码（✅通过100%）

class MyQueue {
    LinkedList<Integer> s1 = new LinkedList<>();
    LinkedList<Integer> s2 = new LinkedList<>();
    public MyQueue() {
        s1.clear();
        s2.clear();
    }

    public void push(int x) {
        //push前把s2中剩下的数加回s1
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
        s1.push(x);
    }

    public int pop() {
        //pop前把s1中所有的数加到s2
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        return s2.pop();
    }

    public int peek() {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        return s2.peek();
    }

    public boolean empty() {
        if(s1.isEmpty() && s2.isEmpty()){
            return true;
        }else {
            return false;
        }
    }
}

❇️225. 用队列实现栈

• 可以大家惯性思维，以为还要两个队列来模拟栈，其实只用一个队列就可以模拟栈了。
• 建议大家掌握一个队列的方法，更简单一些，可以先看视频讲解
• 题目链接：https://leetcode.cn/problems/implement-stack-using-queues/
• 视频讲解：https://www.bilibili.com/video/BV1Fd4y1K7sm/
• 文章讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

随想录思路

当要pop时，先把队列除要pop的数字之外都弹出然后重新加到队列中

自己的代码（✅通过100%）

class MyStack {
    Queue<Integer> queue = new LinkedList<>();
    public MyStack() {

    }

    public void push(int x) {
        queue.offer(x);
    }

    public int pop() {
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
        return queue.poll();
    }

    public int top() {
        int res = 0;
        for (int i = 0; i < queue.size(); i++) {
            if(i == queue.size() - 1){
                res = queue.peek();
            }
            queue.offer(queue.poll());
        }
        return res;
    }

    public boolean empty() {
        if(queue.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}