代码随想录算法训练营第10天 | 理论基础、232.用栈实现队列、225. 用队列实现栈、20. 有效的括号、1047. 删除字符串中的所有相邻重复项

理论基础

了解一下栈与队列的内部实现机制，文中是以C++为例讲解的

文章讲解：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

队列（Queue）

队列是一种先进先出（FIFO，First In First Out）的数据结构，元素从队尾加入，从队头取出。Java 提供了多个接口和类来实现队列，例如 Queue 接口和 LinkedList、PriorityQueue 等实现类。

常用操作

添加元素： add(E e) 或 offer(E e)
移除元素： remove() 或 poll()
查看队头元素： element() 或 peek()

栈（Stack）

栈是一种后进先出（LIFO，Last In First Out）的数据结构，元素从栈顶加入，从栈顶取出。Java 提供了 Stack 类来实现栈。

常用操作

压入元素： push(E e)
弹出元素： pop()
查看栈顶元素： peek()

在 Java 中，Stack 是一种容器，它继承自 Vector 类。

Java 提供了自己的集合框架（Collections Framework），它与 C++ 的 STL 类似但独立发展。Java 的 Stack 类是从 Java 1.0 版本开始就有的。

Stack 类是基于 Vector 实现的，具有动态数组的特性。

虽然 Stack 类没有直接提供迭代器，但它继承自 Vector，因此可以使用 Vector 的迭代器来遍历。

这部分数据结构完全没有学过的印象……准备先打一下基础

232.用栈实现队列

题目链接/文章讲解/视频讲解

图示

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        //只有stackOut为空，才从stackIn导入全部数据
        if(stackOut.isEmpty()){
            while(!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }
    
    public int peek() {
        int res = this.pop();
        stackOut.push(res); //因为pop了所以要再添加回去
        return res;
        
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }


}

/**
 * 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();
 */

可以注意一下代码是如何复用的。

225. 用队列实现栈

题目链接/文章讲解/视频讲解

一个队列模拟栈的方法
取的是队列里的最后一个元素，就要把之前的size-1个元素添加到队列尾部。

图示

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();  //注意 initialization
    }
    
    public void push(int x) {
        queue.offer(x);
    }
    
    public int pop() {
        rePosition(); // Queue 接口没有 rePosition 方法。 rePosition 方法是自己在 MyStack 类
                      // 中定义的一个方法，而不是 Queue 接口的一部分。因此，应该直接调用 MyStack 类                    
                      // 中的 rePosition 方法，而不是通过 queue 对象来调用它。
        return queue.poll(); // 弹出最后一个元素，这就是栈顶元素
    }
    
    public int top() {
        rePosition();
        int res = queue.poll();
        queue.offer(res);
        return res;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    private void rePosition(){
        int size = queue.size();
        // 将队列头部的元素（除了最后一个元素外）重新添加到队列尾部
        size--;
        while(size-- > 0){
            queue.offer(queue.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();
 */

双端队列不太会，之后补一下学数据结构的笔记。

20. 有效的括号

栈的经典应用了。
题目链接/文章讲解/视频讲解

解题思路

分析不匹配的三种场景：左括号多余；右括号多余；括号数量正确但是不匹配。
如果当前字符是左括号 (、{ 或 [，则将相应的右括号 )、} 或 ] 压入栈中，这样可以直接弹出来检验，方便代码实现
如果当前字符是右括号 )、} 或 ]，则进行如下检查：
如果栈为空（即没有对应的左括号），返回 false。
如果栈顶的元素与当前字符不匹配，返回 false。
如果栈顶元素与当前字符匹配，弹出栈顶元素。
检查栈是否为空：遍历结束后，如果栈为空，说明所有括号都匹配，返回 true；否则，返回 false。

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0){
            return false; // 如果s的长度为奇数，一定不符合要求
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(')');
            }else if(c == '{'){
                stack.push('}');
            }else if(c == '['){
                stack.push(']');
            }
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if(stack.isEmpty() || stack.peek() != c){
                return false;
            }else{
                stack.pop();
            }

        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

栈的经典应用。
要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了遍历数组当前元素时候，前一个元素是什么。
题目链接/文章讲解/视频讲解