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

今日任务

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

链接：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q (opens in a new tab)

理论基础

问题：

java中，

stack，queue 是容器么？

stack，queue是如何实现的？

stack，queue 提供迭代器来遍历空间么？

在Java中，Stack和Queue被视为容器或集合，因为它们都能存储和管理对象。

Stack：Stack是个后进先出（LIFO）的数据结构，Java中的Stack类继承自Vector类。主要的操作有push（将元素压入栈顶），pop（移除栈顶元素并返回），peek（查看栈顶元素但不移除）， empty（检查栈是否为空）等。
Queue：Queue是一个先进先出（FIFO）的数据结构，它是Java Collection Framework的一部分。 Java中的Queue接口有多种实现，例如LinkedList、PriorityQueue等。主要的操作有add/offer （向队列尾部添加元素），remove/poll（移除并返回队列头部的元素），element/peek （查看但不移除队列头部的元素）等。

至于是否提供迭代器来遍历，答案是肯定的。Stack和Queue都是Java集合框架的一部分，它们都实现了Iterable接口，因此都可以使用迭代器来遍历。例如，你可以使用for-each循环或者直接创建迭代器来遍历Stack或Queue中的元素。但是要注意，遍历并不会改变Stack和Queue中元素的顺序或状态，它只是访问每一个元素。

问题：

C++中，

stack，queue 是容器么？

stack，queue是如何实现的？

stack，queue 提供迭代器来遍历空间么？

在C++中，stack和queue被称为容器适配器，而不是标准的容器。它们提供了特定的接口（如LIFO（后进先出）行为对于stack，FIFO（先进先出）行为对于queue），但实际上是构建在其他容器之上的。默认情况下，stack和queue使用std::deque作为其底层容器，但也可以使用其他容器，如std::list或std::vector。

stack和queue的实现依赖于其底层容器。例如，stack的push操作可能只是在底层容器的一端添加一个元素，而pop操作则是从底层容器的同一端移除一个元素。queue的实现类似，但是添加元素（push）和移除元素（pop）发生在底层容器的不同端点。

需要注意的是，尽管stack和queue基于其他容器，但它们不提供迭代器来遍历其元素。这是因为 stack和queue的设计目标是提供特定的（LIFO或FIFO）行为，而不是提供一般的序列操作。如果你需要遍历stack或queue的元素，可能需要重新考虑你的设计，或者使用更适合你需求的容器（如std::vector或std::list）。

232.用栈实现队列

自己想法

以下策略只在压入的时候作文章：

压入的时候先把que都移到tmp里，再压入tmp，再把tmp移到que里；

弹出的时候从que弹出即可。

class MyQueue {
 
    Stack<Integer> stackTmp;
    Stack<Integer> stackQue;
 
    public MyQueue() {
        stackTmp = new Stack<>();
        stackQue = new Stack<>();
    }
    
    public void push(int x) {
        moveStack(stackQue, stackTmp);
        stackTmp.push(x);
        moveStack(stackTmp, stackQue);
    }
    
    public int pop() {
        return stackQue.pop();
    }
    
    public int peek() {
        return stackQue.peek();
    }
    
    public boolean empty() {
        return stackQue.isEmpty();
    }
 
    public void moveStack(Stack<Integer> fromS, Stack<Integer> toS) {
        while(!toS.isEmpty()) toS.pop();
        while(!fromS.isEmpty()) {
            toS.push(fromS.pop());
        }
    }
}
 
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

题解想法

两个Stack分别叫stackIn和stackOut，分别处理进出。与我的做法相比，可以减少stack挪移次数。

回顾

java Stack声明：Stack<Integer> stack = new Stack<>();
java Stack类的常用方法：push(), pop(), peek(), isEmpty()

225. 用队列实现栈

自己想法

以下策略保证两个队列中始终有一个为空，只在压入的时候作文章：

压入的时候先压到空的那个里（记为a），再把另一个（记为b）全部弹到a。此时b为空；

弹出的时候找到不为空的那个（记为a），弹出即可。

class MyStack {
 
    Queue<Integer> queue1;
    Queue<Integer> queue2;
 
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(queue1.isEmpty()) {
            queue1.offer(x);
            moveQueue(queue2, queue1);
        }
        else if(queue2.isEmpty()) {
            queue2.offer(x);
            moveQueue(queue1, queue2);
        }
    }
    
    public int pop() {
        if(!queue2.isEmpty()) return queue2.poll();
        else if(!queue1.isEmpty()) return queue1.poll();
        else return -1;
    }
    
    public int top() {
        if(!queue2.isEmpty()) return queue2.peek();
        else if(!queue1.isEmpty()) return queue1.peek();
        else return -1;
    }
    
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
 
    public void moveQueue(Queue<Integer> fromQ, Queue<Integer> toQ) {
        while(!fromQ.isEmpty()) {
            toQ.offer(fromQ.poll());
        }
    }
}
 
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

题解想法

其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候, 只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

回顾

java Queue声明：Queue<Integer> queue = new LinkedList<>();
java Queue类的常用方法：offer(), poll(), peek(), isEmpty()