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，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);