资源引用：
栈与队列理论基础（栈与队列理论基础）
leetcode题目：
225.用队列实现栈（225.用队列实现栈）
232.用栈实现队列（232.用栈实现队列）
20.有效的括号（20.有效的括号）
1047.删除字符串中的所有相邻重复项（1047.删除字符串中的所有相邻重复项）
久违碎碎念：
“放弃不可怕，可怕的是没有继续前行的勇气。”
有朋友在csdn上催问我怎么没有更新了？对此我感到一些局促和羞愤——我忙吗？我真挺忙的，每天都有ddl要赶，本周绝大部分课程的最终实验和最终作业全面结束，花了我不少精力。我忙吗？我好像也没那么忙，每天晚上习惯熬夜到1点却无所事事，天气日渐转冷我不但不去运动，每天早上还越睡越晚，午觉也屡屡一睡1个多小时不起，只有从17点到22点的时间每天能够保证完全学习任务。
代码随想录如今以及到了第24天，我才完成了第10天。
接下来又有2个考试和一个实验结项。
报名了腾讯的产品经理训练营为期21天也将在下周一开课。
尽管如此，还是要学，还是要练，想法不能停留在脑海和口头，而要实践在指尖！
不管怎么说，今天是改变的一天，起得早，午睡半小时，运动一小时！
本期带来的内容比较精彩，适合轻易上手理解什么是栈和队列。
栈与队列理论基础（栈与队列理论基础）
栈是先进后出，队列是先进先出
栈与队列的四问：
1. Java中的栈/队列是容器吗？
-
- 在Java中这两种数据结构可以被视为容器，但通常被视为特殊的集合，因为他们具有特定的适用场景和操作限制。
2. 我们使用的栈/队列来自哪个标准库？
-
- 栈（Stack）：在Java中，可以通过
java.util.Stack类来实现栈，这个类继承自Vector类，因此它是一个同步的线程安全的栈实现。但是，由于Stack类是遗留类，它不推荐在新的代码中使用，因为它的性能和灵活性不如使用Deque接口及其实现类。 - 队列（Queue）：Java提供了
java.util.Queue接口，以及多种实现这个接口的类，如LinkedList、ArrayDeque、PriorityQueue等。这些类可以作为队列使用，但它们也是Java Collections Framework的一部分，因此可以被视为容器。
- 栈（Stack）：在Java中，可以通过
3. 我们使用的标准库（Java Collections Framework）中的栈/队列是怎样实现的？
-
- 在Java Collections Framework中，
Queue是一个正式的接口，而Stack则不是一个接口，而是一个具体的类。在现代Java编程中，推荐使用Deque接口及其实现类（如ArrayDeque）来实现栈的功能，因为它们提供了更好的性能和更灵活的API。
- 在Java Collections Framework中，
4. 队列Queue的实现：
Java Collections Framework中的Queue接口是一个集合接口，它扩展了Collection接口，专门用于表示队列这种数据结构。Queue接口提供了队列操作的基本方法，如入队（offer）、出队（poll）、查看队首元素（peek）等。以下是Queue接口的一些关键方法：
boolean offer(E e)：如果可能的话，将元素添加到队列中，如果队列容量限制不允许添加，则返回false。E poll()：移除并返回队列头部的元素，如果队列为空，则返回null。E peek()：返回队列头部的元素但不移除它，如果队列为空，则返回null。boolean add(E e)：将元素添加到队列中，如果添加失败（例如队列容量限制），则抛出一个IllegalStateException。boolean offer(E e, long timeout, TimeUnit unit)：尝试在指定时间内将元素添加到队列中，如果添加失败，则返回false。E poll(long timeout, TimeUnit unit)：尝试在指定时间内移除并返回队列头部的元素，如果超时，则返回null。
Queue接口有多种实现，每种实现都提供了不同的功能和特性，以适应不同的使用场景：
ArrayDeque：这是一个基于动态数组的双端队列实现，没有容量限制，支持快速的插入和删除操作。它实现了Deque接口，因此也可以作为栈使用。LinkedList：这是一个基于链表的双端队列实现，可以作为队列或双端队列使用。它允许在队列的头部和尾部进行快速的插入和删除操作。PriorityQueue：这是一个基于优先级堆的队列实现，它确保队列头部始终是元素中具有最高优先级的元素。元素通常使用Comparable或Comparator进行排序。ConcurrentLinkedQueue：这是一个基于链表的无界线程安全队列，适用于高并发环境。ConcurrentLinkedDeque：这是一个基于链表的双端队列，也是线程安全的，适用于高并发环境。LinkedBlockingQueue：这是一个基于链表的有界线程安全队列，支持阻塞操作，当队列为空时，取元素的操作会阻塞，直到有元素可用。ArrayBlockingQueue：这是一个基于数组的有界线程安全队列，支持阻塞操作，当队列为空时，取元素的操作会阻塞，直到有元素可用。
每种Queue实现都有其特定的用途和性能特点，开发者可以根据实际需求选择合适的实现。
使用ArrayDeque实现队列的代码示例如下：
Deque<String> queue = new ArrayDeque<>();
queue.offer("element1"); // 在队尾插入元素
queue.offer("element2"); // 再次在队尾插入元素
String element = queue.poll(); // 从队首移除元素5. 栈Stack的实现：
在Java Collections Framework中，Stack类是一个遗留类，它继承自Vector类，但它并不是Java Collections Framework的一部分，因为它不实现任何接口，且由于继承自Vector，它是同步的，这可能导致不必要的性能开销。此外，Stack类的方法签名不是泛型的，这意味着它只能处理Object类型的元素，这在使用时需要进行类型转换，增加了代码的复杂性和出错的可能性。
由于这些限制，Java官方推荐使用Deque接口及其实现类来实现栈的功能。Deque接口提供了双端队列的功能，可以通过限制元素的插入和删除操作来模拟栈的行为。以下是使用Deque实现栈的示例：
Deque<String> stack = new ArrayDeque<>();
stack.push("element1"); // 将元素压入栈顶
stack.push("element2"); // 再次压入元素
String element = stack.pop(); // 移除并返回栈顶元素6. stack /queue提供迭代器来遍历stack/queue空间么？
Deque实现的栈（Stack）和队列（Queue）也提供迭代器来遍历其元素。由于Deque接口继承自Queue接口，而Queue接口又扩展了Collection接口，所以任何实现了Deque接口的类（如ArrayDeque、LinkedList等）都会提供迭代器来遍历其元素。
以下是使用迭代器遍历Deque实现的栈和队列的示例代码：
// 使用ArrayDeque实现栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
// 遍历栈
Iterator<Integer> stackIterator = stack.iterator();
while (stackIterator.hasNext()) {
System.out.println(stackIterator.next());
}
// 使用ArrayDeque实现队列
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 遍历队列
Iterator<Integer> queueIterator = queue.iterator();
while (queueIterator.hasNext()) {
System.out.println(queueIterator.next());
}总结
栈和队列都可以使用Deque接口及其实现类来实现栈/队列的功能，虽然提供了迭代器，但必须注意：一定不能在遍历过程中对元素进行改动！
225.用队列实现栈（225.用队列实现栈）
题目分析：
要求使用且仅使用两个队列实现栈，并支持push、top、pop和empty两种操作
解题重点：
两个队列作为主从队列，从队列作为主队列的备份。
解题思路：
- 使用Deque接口和ArrayDeque类实现主队列que1和从队列que2
- MyStack方法对两个队列初始化
- push方法将参数x压入que1
- pop方法通过size.()方法获取que1中的元素个数，将que1中的元素pop入que2直到que1只剩最后一个元素，pop该元素并保存为res，再将que2赋值给que1恢复备份并清空备份que2，最后返回res。
- top方法的与pop方法的唯一不同之处是，que1中的最后一个元素保存为res后需要压入que2，保证备份完整性。
- empty方法只需检查主队列que1即可。
总结反思：
这道题目限制要求使用两个队列，回顾队列的特性可知：队列的输出顺序和输入顺序不变，因此只需结合size进行pop计数，除目标元素外的每一个pop的元素重新push到队尾即可。
232.用栈实现队列（232.用栈实现队列）
题目分析：
栈是先进后出，队列是先进先出，为了用栈实现队列的push、pop、peek和empty功能，考虑使用两个栈实现“倒放”。
题目重点：
使用两个栈，一个栈作为输入栈，另一个栈作为输出栈。
解题思路：
- 使用Deque接口和ArrayDeque类来实现输入栈stackIn和输出栈stackOut
- MyQueue方法对两个栈初始化
- push方法将参数x压入stackIn
- pop方法，先将stackIn中全部元素压入输出栈stackOut，然后再从stackOut中pop出栈顶元素，最后将stackOut中全部元素压回输出栈stackIn
- peek方法，唯一与pop方法不同的是不将stackOut栈顶元素pop出，而是使用stack的peek
- empty方法，通过检查输入栈stackIn的isEmpty方法实现
总结反思：
由于队列具有“先进后出”的特性，所以不必每次pop都将输入栈和输出栈来回腾挪，只需在每次pop或peek前检查输出栈内是否为空，若为空，则先将输入栈的元素全部压入输出栈，再从输出栈pop/peek；若不为空，则直接从输出栈pop/peek。
class MyQueue {
Deque<Integer> stackIn;
Deque<Integer> stackOut;
public MyQueue() {
stackIn = new ArrayDeque<>(); // 负责进栈
stackOut = new ArrayDeque<>(); // 负责出栈
}
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());
}
}
}20.有效的括号（20.有效的括号）
题目分析：
给定一个包含()/{}/[]三种括号的字符串s，需要判断是否有效：1.相同类型括号左右完整闭合 2.左括号按照正确顺序闭合 3.每个右括号都有对应的左括号
解题重点：
需满足第二点，则后出现的左括号先由相应的右括号闭合，符合后进先出，用栈解决
解题思路：
初始化一个栈，当遇到左括号时入栈，当遇到右括号时检查是否和栈顶左括号相匹配，若匹配则将栈顶括号弹出，若不匹配或栈空则直接返回false。当字符串读取完毕，检查栈是否为空，以"stack.isEmpty()"作为返回值即可。
总结反思：
此题简单，分析清楚三种不匹配的情况，找准返回值的时机，最终通过检查栈是否为空来返回相应值即可。
class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
//碰到左括号，就把相应的右括号入栈
if (ch == '(') {
deque.push(')');
}else if (ch == '{') {
deque.push('}');
}else if (ch == '[') {
deque.push(']');
} else if (deque.isEmpty() || deque.peek() != ch) {
return false;
}else {//如果是右括号判断是否和栈顶元素匹配
deque.pop();
}
}
//最后判断栈中元素是否匹配
return deque.isEmpty();
}
}1047.删除字符串中的所有相邻重复项（1047.删除字符串中的所有相邻重复项）
题目分析：
字符串由小写字母组成，需要删除相邻且相同的字母，对s反复执行该“重复项删除”操作，直至最终无重复项删除并返回最终字符串。
解题重点：
使用栈解决，好处是栈可以告诉你前一个输入是什么，并直接利用出栈将重复项删除。
解题思路：
初始化一个栈为空，遍历字符串中的每一个字符：检查该字符是否与栈顶字符相同，若相同则弹出栈顶字符且该字符不入栈，否则字符入栈。直至遍历字符串完全，将栈内字符依次弹出并倒置（因为先进后出）组成新的字符串，与原字符串的长度相比较（因为若删除重复项，则前后字符串长度一定不同），若长度相同则直接返回该字符串，若不相同则重复置栈为空、遍历字符做出入栈及重复项删除操作，直至最终前后字符串长度相同为止。
class Solution {
public String removeDuplicates(String S) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}总结反思：
拿字符串直接作为栈，省去了栈还要转为字符串并翻转的操作
class Solution {
public String removeDuplicates(String s) {
// 将 res 当做栈
// 也可以用 StringBuilder 来修改字符串，速度更快
// StringBuilder res = new StringBuilder();
StringBuffer res = new StringBuffer();
// top为 res 的长度
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
// 否则，将该字符 入栈，同时top++
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}