代码随想录算法训练营第十天 |232.用栈实现队列， 225.用队列实现栈

分手后的思念是犯贱 2024-04-23 03:58 16阅读 0赞

#### 栈与队列基础： ####

队列是先进先出，栈是先进后出。

如图所示：

![88b5cda467719be1128eed8ea1a04b11.png][]

#### 232.用栈实现队列（已看视频） ####

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、视频讲解： [栈的基本操作！ | LeetCode：232.用栈实现队列\_哔哩哔哩\_bilibili][_ LeetCode_232._bilibili]

4、题目：

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。  
pop() -- 从队列首部移除元素。  
peek() -- 返回队列首部的元素。  
empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
    queue.push(1);
    queue.push(2);
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

说明:

*  你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
 *  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 *  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

5、注意点：

这个比较好实现，主要是弄清楚两个栈（in、out）来实现队列，模拟队列时候，先将in里面放out，接着操作out就可以了，相当于队列。

class MyQueue {
        Stack<Integer> stackIn;
        Stack<Integer> stackOut;
    
        public MyQueue() {
            stackIn = new Stack<>(); // 负责进栈
            stackOut = new Stack<>(); // 负责出栈
        }
    
        public void push(int x) {
            stackIn.push(x);
        }
    
        public int pop() {
            dumpstackIn();
            return stackOut.pop();
        }
    
        public int peek() {
            dumpstackIn();
            return stackOut.peek();
        }
    
        public boolean empty() {
            return stackIn.isEmpty() && stackOut.isEmpty();
        }
    
        // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
        private void dumpstackIn() {
            if (!stackOut.isEmpty()) return;
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }

#### 225.用队列实现栈（已看视频） ####

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、视频讲解：

[队列的基本操作！ | LeetCode：225. 用队列实现栈\_哔哩哔哩\_bilibili][_ LeetCode_225. _bilibili]

4、题目：

使用队列实现栈的下列操作：

*  push(x) -- 元素 x 入栈
 *  pop() -- 移除栈顶元素
 *  top() -- 获取栈顶元素
 *  empty() -- 返回栈是否为空

注意:

*  你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
 *  你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 *  你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）

5、思路：

队列每添加一个元素，都把剩下的元素弹出再加入，这样就保证每次添加的这个元素都在队列的队首

class MyStack {
        Queue<Integer> queue;
    
        public MyStack() {
            queue = new LinkedList<>();
        }
    
        // 每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
        public void push(int x) {
            queue.offer(x);
            int size = queue.size();
            // 移动除了 A 的其它数
            while (size-- > 1)
                queue.offer(queue.poll());
        }
    
        public int pop() {
            return queue.poll();
        }
    
        public int top() {
            return queue.peek();
        }
    
        public boolean empty() {
            return queue.isEmpty();
        }
    }

####  ####

[88b5cda467719be1128eed8ea1a04b11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/ff71783b97c546d3b1f30bca39c77400.png
[LeetCode_ -]: https://leetcode.cn/problems/implement-queue-using-stacks/
[Link 1]: https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
[_ LeetCode_232._bilibili]: https://www.bilibili.com/video/BV1nY4y1w7VC
[LeetCode_ - 1]: https://leetcode.cn/problems/implement-stack-using-queues/
[Link 2]: https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_225. _bilibili]: https://www.bilibili.com/video/BV1Fd4y1K7sm