Day10补代码随想录 理论基础|232.用栈实现队列|225.用队列实现栈|20.有效的括号|1047.删除字符串中的所有相邻重复项
栈和队列理论基础
抽象认识
- 栈是先进后出(FIFO)，队列是先进先出(LIFO)
- 队首(先进))队尾(后进)
- 栈顶(后进)栈底(先进)
- 栈(Stack)
- 只在一端进行进出操作(只在一端进一端出)
- 像个篮球框，取用篮球从一端进出。
-
/进栈 int a[1000];//足够大的栈空间 int top=-1;//栈的初始化，栈顶位置标记 for(i=0;i<10;i++){ a[++top]=i;//先对top+1，再录入位置，使用++top为了防止最后一次循环赋值后top依旧进行+1,使得top指向了栈外的空数组。 } /出栈 for(i=0;i<10;i++){ print("%d",a[top--]);}
- 队列(Queue)
- 在两端分别进行进和出的操作(一端进一端出)
- 食堂排队，从后面排队，前面买饭离开。
-
//QQ号，有10个数字的排列，排序为奇数的数字取出排列；排序为偶数的数字放入队尾重新报号，组成QQ号。 int a[100]={1,2,3,4,5,6,7,8,9,0},head,tail; //队头队尾 head=0; tail=10;//标记的是最后一个元素后面的空元素 while(head<tail){ printf("%d",a[head]);//奇数离开队伍 head++; a[tail]=a[head];//偶数放在队尾 tail++;//补长队尾 head++;//减少队头 }
JAVA中的栈和队列
- 栈(Stack) Stack类位于java.util包中
- 基本操作
- push(E item):将元素压入栈顶。
- pop():移除并返回栈顶的元素。
- peek():查看栈顶的元素，但不移除。
- isEmpty():判断栈是否为空。
- 低层实现：基于一个动态数组(Vector)来实现的，和C++类似，可以通过扩展Vector来管理栈中的元素。
- 基本操作
- 队列(Queue) Queue接口
- 常见的实现类
- LinkedList:提供队列的标准实现
- PriorityQueue:优先队列，根据元素的优先级顺序出队。
- ArrayDeque:基于数组的双端队列。
- 基础操作
- add(E e):将元素添加到队尾
- remove():移除并返回队首的元素
- peek():查看队首的元素，但不移除。
- isEmpty():判断队列是否为空
- 底层实现：默认的队列实现是LinkedList，基于双向链表来实现队列的入队和出队操作。ArrayDeque是基于数组的实现，通常性能更好。
- 常见的实现类
几个问题
- Java中的Stack是容器吗？
- 是，Stack是一个继承自vector类的容器。vector是一个可动态扩展的数组，实现了List接口。Stack类本身是一个容器类，提供了栈(LIFO)操作，由于
Stack继承自Vector，所以它本质上也继承了Vector的所有特性，包括动态调整大小和随机访问等。然而，Stack主要用来模拟栈的行为，提供了栈特有的操作，但并不暴露所有Vector提供的操作。
- 是，Stack是一个继承自vector类的容器。vector是一个可动态扩展的数组，实现了List接口。Stack类本身是一个容器类，提供了栈(LIFO)操作，由于
- 我们使用的stack是属于什么？
- JAVA标准库(JDK)，位于java.util，
- stack类是继承自Vector的一个类，设计用于支持栈(LIFO)行为。
- JAVA的stack是如何实现的？
- Stack是通过继承Vector类来实现的。Vector是一个动态数组，可以自动扩展它的容量。
- Stack通过push()和pop()方法来操作Vector中的元素，以实现栈的LIFO行为。
- stack提供迭代器来遍历stack空间吗？
- 是的，但不推荐使用。
- Stack提供了iterator()方法来获取一个迭代器，从而遍历栈中的元素、但是不符合栈的设计哲学，因为栈是符合先进后出原则，允许迭代器遍历栈中 元素会破坏这一原则。
- 由于栈的特性，只允许访问栈顶元素，允许迭代的做法违背了栈的设计原则，因此并不推荐使用Stack类，推荐使用Deque(双端队列)或ArrayDeque来代替Stack，这些类支持栈和队列的操作，并且不会提供队元素的遍历行为。
- 在java中，没有缺省容器的概念，栈类和队列类都是固定的，不能更换低层容易，Java中的Stack类的底层实现是固定的。
232.用栈实现队列
题目
https://leetcode.cn/problems/implement-queue-using-stacks/description/
使用栈实现队列的下列操作：
push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
- 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
- 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
思路
-
思路
- 用****2个栈(入栈)****来改变出栈顺序
- 入栈要全部放在出栈里，模拟队列的行为（如果出栈是空的）
- 队列是先进先出，栈是先进后出，那么就让数先入栈，再将入栈的数移动到出栈里，开口不变。
- 如果要弹出，看看出栈是否为空，如果为空，把所有元素加倒出栈里。
- 用****2个栈(入栈)****来改变出栈顺序
-
代码思路
- 写清各个接口的返回类型
- 初始化入栈和出栈类，创建入栈和出战的对象。
-
class MyQueue{ //声明入栈和出栈 Stack<Integer> stackIn; Stack<Integer> stackOut; //Initialize public MyQueue(){ stackIn=new Stack<>(); stackOut=new Stack<>(); } //将一个元素放入队列的尾部 public void push(int x){ stackIn.push(x);//队列从入栈进入 } //从队列首部移除元素 public int pop(){//队列中的先进先出，就是取出一个元素并返回它。 dumpstackIn();//在出栈放入栈pop出来的数 return stackOut.pop();//弹出(移除)再返回值 } //返回队列首部的元素 public int peek(){ dumpstackIn(); return stackOut.peek();//返回栈顶，但不移除它。 } //返回队列是否为空 public boolean empty(){ return stackIn.isEmpty()&&stackOut.isEmpty(); } private void dumpstackIn(){ if(!stackOut.isEmpty()) return;//如果出栈不是空的，那就返回不用执行 while(!stackIn.isEmpty()){ stackOut.push(stackIn.pop());//放入栈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<Integer>stackIn;
Stack<Integer>stackOut; - 创建入栈和出栈的对象，stackIn=new Stack<>();stackOut=new Stack<>();
- return stackOut.peek();//默认返回栈顶，但不移除它
225.用队列实现栈
题目
https://leetcode.cn/problems/implement-stack-using-queues/description/
https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
【惯性思维用两个队列来模拟栈，其实只用一个队列就可以模拟栈了】
使用队列实现栈的下列操作：
- push(x) – 元素 x 入栈
- pop() – 移除栈顶元素
- top() – 获取栈顶元素
- empty() – 返回栈是否为空
注意:
- 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）
- 【单向队列】
思路
- 我的思路
- 队列是先进先出，我们让它先进后出，改变出口方向，每当队列满了之后，从列尾出去
- Karl思路
- 队列是先进先出的顺序，如果用两个队列，将一个队列移动到另一个队列中时，先进先出的顺序还是没有改变。
- 栈pop的是栈顶元素(后进)，队列pop的是队首，我们让栈顶元素(后进)元素pop到栈尾，假设栈有n个元素，每次让栈的栈底元素pop出来，需要将前n-1个元素放入到栈底后面。
- 代码
class MyStack { Queue<Integer> queue;//Queue是个接口 public MyStack() { queue=new LinkedList<>();//LinkedList是Queue的一个实现类 } public void push(int x) { queue.add(x);//将元素添加到队尾，相当于栈整体移动到队列了 } public int pop() { rePosition(); return queue.poll();//移除并返回栈首元素 } public int top() { rePosition(); int result=queue.poll();//先移除队首(实际是之前的队尾，即后进) queue.add(result);//后进在栈顶，返回 return result; } public boolean empty() { return queue.isEmpty(); } //将队列前面的元素加入到队列末尾 public void rePosition(){ int size=queue.size(); size--;//需要将size-1个元素移动到队尾 while(size-->0)//在每次循环后，将size-1,只要size>0就继续 queue.add(queue.poll());//移除并返回队首元素，知道前size-1个元素全部返回 } } /** * 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(); */
总结
- size()和length的使用范围
- size()是方法，length是属性
- size():用于动态大小的集合类；Map的键值对数量
- length:固定长度的数组，字符串
- 注意事项
-
接口和实现类
- Queue
<Integer>queue;//Queue是个接口 - queue=new LinkedList<>();//LinkedList是Queue的一个实现类
- Queue
-
queue的一些用法
- queue.add(x) 将元素加入队尾
- queue.poll() 移除并返回队首元素
-
top()方法需要多练习，很绕。
-
20.有效的括号
题目
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
- 输入: “()”
- 输出: true
示例 2:
- 输入: “()[]{}”
- 输出: true
示例 3:
- 输入: “(]”
- 输出: false
示例 4:
- 输入: “([)]”
- 输出: false
示例 5:
- 输入: “{[]}”
- 输出: true
思路
- 我的思路
- 思路很混乱，怎么能在栈和队列中实现这些
- Carl
- 三种不匹配的情况
- 字符串里的左方向的括号多余了，不匹配。
- 括号没有多余，但是括号的类型没有匹配上。
- 右方向的括号多余了，不匹配
- 字符串里的左方向的括号多余了，不匹配。
- 三种不匹配的情况
- 代码思路
- 如果是奇数，一定可以发现不匹配字符。
- for循环
- if 遇到(，在栈中加)
- 提前准备比较匹配
- else if { ，在栈中加}
- elseif [,在栈中加]
- 【情况2，3】elseif 栈空(情况3)||不匹配(情况2) return false;相等情况弹出。
- 【情况1】 遍历到最后一个了，如果不是空栈，return false;
- 代码
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){ //情况2，3 return false; }else{//如果是右括号判断是否和栈顶元素匹配 deque.pop(); } } return deque.isEmpty(); } }
总结
- string要转换为char，才能比较
- 注意，情况2，3先判断栈空【情况3】
1047.删除字符串中的所有相邻重复项
题目
https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
- 输入：“abbaca”
- 输出：“ca”
- 解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
【栈的经典应用，栈喜欢做这种消除的操作，栈帮助记录了遍历数组当前元素的时候，前一个元素是什么】
思路
- 我的思路
- 难点，删除完bb后aa又靠近了。迭代。
- 每遍历一个元素，
-
如果有前一个元素，把他的前一个元素储push在栈中。
- 比较它和前一个元素，如果匹配，就删除字符串里的这个元素和前一个元素，不匹配就pop。
-
else if
- continue.
-
- Carl思路
- 消消乐，
- if 栈是空的||不匹配，那么放入当前元素
- else if 消除 pop弹出
- 最后要把栈中的字符串翻转过来
- 消消乐，
- 代码
class Solution { public String removeDuplicates(String s) { 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()){//全pop出去 str=deque.pop()+str;//先pop出去的放在前面，恢复正序 } return str; } }
总结
-
ArrayDeque 是JAVA中的双端队列数据结构，既可以用作栈，也可以用做队列
- 栈
- push()
- pop()
- 队列
- add()
- poll()
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点 //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist - 栈
-
低级错误，ch=s.charAt(i); 里面是string s 的第i个，而不是直接ch=s.charAt(s);