当前位置：首页 > article >正文

《代码随想录》刷题笔记——栈与队列篇【java实现】

article 2024/11/30 5:40:23

文章目录

用栈实现队列
用队列实现栈
有效的括号
- 我的解法
- 代码随想录
删除字符串中的所有相邻重复项
- 我的解法
- 代码随想录
- - 栈解法
  - 字符串充当栈
  - ※双指针
逆波兰表达式求值
- 我的解法
- 代码随想录
滑动窗口最大值
- 我的解法
- - 暴力解法
  - 暴力解法+一点优化
  - 单调队列
- 代码随想录
- - 单调队列
前 K 个高频元素
- 代码随想录
- - 优先队列
总结

用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/

在队列中，存入顺序是1、2、3，取出的顺序也是1、2、3。如果使用一个栈，那么取出顺序是3、2、1，如果想要和队列的取出顺序一致，那就要多使用一个新栈，3、2、1存入到新栈，从新栈中取出来就是1、2、3。

如果先push1、2、3 进栈，然后pop一次，接着存入4，再peek一次，需要怎么操作？

按照队列的操作逻辑，pop出来的应该是1，那就需要先将1、2、3按照顺序存入栈A中，然后从A中依次取出3、2、1，存储到栈B中（将这个行为称为转移），这时pop出来的就是1，栈B中剩余的元素是2、3；接着存入4，再peek的出来的应该是2，此时就不能从栈A中取出4放入到栈B中了，不然peek出来的是4，不是2，因此当栈B中有元素的时候，直接peek即可，无需进行转移操作

private Stack<Integer> stackA;
private Stack<Integer> stackB;

public MyQueue() {
    this.stackA = new Stack<>();
    this.stackB = new Stack<>();
}

public void push(int x) {
    this.stackA.push(x);
}

public int pop() {
    transfer();
    return this.stackB.pop();
}

public int peek() {
    transfer();
    return this.stackB.peek();
}

/**
 * 转移栈A的元素到B中
 */
private void transfer() {
    if (!stackB.empty()) {
        return;
    }
    while (!stackA.empty()) {
        stackB.push(stackA.pop());
    }
}

public boolean empty() {
    // 当两个栈中的元素都为空时，队列才可以看成为空
    return this.stackA.empty() && this.stackB.empty();
}

用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/

在这里插入图片描述

/**
 * @Author dam
 * @create 2023/11/1 22:06
 */
public class MyStack {
    private LinkedList<Integer> queueA;
    private LinkedList<Integer> queueB;

    public MyStack() {
        this.queueA = new LinkedList<>();
        this.queueB = new LinkedList<>();
    }

    public void push(int x) {
        this.queueA.add(x);
    }

    public int pop() {
        int num;
        while (true) {
            Integer pop = queueA.pop();
            if (queueA.isEmpty()) {
                // --if-- queueA.isEmpty()==true，说明pop已经是queueA最后一个元素
                // 记录最后一个元素，这个元素要被弹出，无需存储到queueB中进行备份
                num = pop;
                break;
            } else {
                // --if-- 如果pop不是最后一个元素，那就将其存储到queueB中进行备份
                queueB.add(pop);
            }
        }
        // 将queueB中备份的元素重新添加回到queueA中
        while (!queueB.isEmpty()) {
            queueA.add(queueB.pop());
        }
        return num;
    }

    public int top() {
        int num;
        while (true) {
            Integer pop = queueA.pop();
            if (queueA.isEmpty()) {
                num = pop;
                queueB.add(pop);
                break;
            } else {
                queueB.add(pop);
            }
        }
        while (!queueB.isEmpty()) {
            queueA.add(queueB.pop());
        }
        return num;
    }

    public boolean empty() {
        return this.queueA.isEmpty();
    }

}

有效的括号

https://leetcode.cn/problems/valid-parentheses/description/

在这里插入图片描述

【补充案例】

示例 4:

输入: “([)]”
输出: false

示例 5:

输入: “{[]}”
输出: true

我的解法

【思路】

使用一个栈来存储符号，遍历字符串的每个字符：

如果遍历到的是左括号，直接添加到栈中；
如果遍历到的是右括号，否则判断栈中的顶元素是否可以和当前所遍历右括号凑成一对，是则将栈顶元素消除，否则返回false，若栈为空也返回false

public static boolean isValid(String s) {
    if (s.length() % 2 == 1) {
        return false;
    }
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == ')') {
            if (stack.size() == 0 || stack.peek() != '(') {
                return false;
            } else {
                stack.pop();
            }
        } else if (c == '}') {
            if (stack.size() == 0 ||stack.peek() != '{') {
                return false;
            } else {
                stack.pop();
            }
        } else if (c == ']') {
            if (stack.size() == 0 ||stack.peek() != '[') {
                return false;
            } else {
                stack.pop();
            }
        } else {
            stack.add(c);
        }
    }
    return stack.size() == 0;
}

在这里插入图片描述