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是属于什么？
  • 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个栈(入栈)****来改变出栈顺序
    • 入栈要全部放在出栈里，模拟队列的行为（如果出栈是空的）
    • 队列是先进先出，栈是先进后出，那么就让数先入栈，再将入栈的数移动到出栈里，开口不变。
  • 如果要弹出，看看出栈是否为空，如果为空，把所有元素加倒出栈里。

• 代码思路

  • 写清各个接口的返回类型
  • 初始化入栈和出栈类，创建入栈和出战的对象。

  • 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.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，3return 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);