算法题目总结-栈和队列

1.有效的括号

1.答案

package com.sunxiansheng.arithmetic.day10;

import java.util.Stack;

/**
 * Description: 20. 有效的括号
 *
 * @Author sun
 * @Create 2025/1/15 09:37
 * @Version 1.0
 */
public class t20 {

    public static boolean isValid(String s) {
        // 栈
        Stack<Character> stack = new Stack<>();
        // 遍历
        for (int i = 0; i < s.length(); i++) {
            // 如果是左括号就入栈
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            }
            // 如果是右括号，就进行匹配
            if (c == ')' || c == '}' || c == ']') {
                // 如果栈为空，就返回false
                if (stack.isEmpty()) {
                    return false;
                }
                // 从栈中获取一个左括号进行匹配
                Character pop = stack.pop();
                boolean match = match(pop, c);
                if (!match) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 匹配
     *
     * @param left
     * @param right
     * @return
     */
    private static boolean match(Character left, Character right) {
        if (left == '(' && right == ')') {
            return true;
        }
        if (left == '{' && right == '}') {
            return true;
        }
        if (left == '[' && right == ']') {
            return true;
        }
        return false;
    }
}

2.思路

就是左括号入栈，右括号匹配，但是需要注意的是右括号在匹配左括号之前栈不能为空，并且最后所有的右括号都匹配完了栈也不能为空

2.最小栈

1.答案

package com.sunxiansheng.arithmetic.day10;

import java.util.Stack;

/**
 * Description: 155. 最小栈
 *
 * @Author sun
 * @Create 2025/1/15 09:51
 * @Version 1.0
 */
public class MinStack {

    /**
     * 辅助栈
     */
    private Stack<Integer> stack;
    /**
     * 最小栈
     */
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
        // 初始化为一个最大的元素
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        // 压栈压最小
        stack.push(val);
        minStack.push(Math.min(val, minStack.peek()));
    }

    public void pop() {
        // pop都出去
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

2.思路

最小栈初始化一个最大值，压栈压最小，pop都出去，这样就能保证最小栈的栈顶是目前的最小元素

3.前 K 个高频元素

1.答案

package com.sunxiansheng.arithmetic.day10;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Description: 347. 前 K 个高频元素
 *
 * @Author sun
 * @Create 2025/1/15 10:06
 * @Version 1.0
 */
public class t347 {

    public static int[] topKFrequent(int[] nums, int k) {
        // 首先统计频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 构建大顶堆
        PriorityQueue<Map.Entry<Integer, Integer>> pq =
                new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        // 将map的元素放到大顶堆中
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(entry);
        }
        // 从大顶堆中取出前k个元素
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll().getKey();
        }
        return res;
    }
}

2.思路

统计频率之后将其放到大顶堆中，然后取出前k个元素即可

4.用栈实现队列

1.答案

package com.sunxiansheng.arithmetic.day10;

import java.util.Stack;

/**
 * Description: 232. 用栈实现队列
 *
 * @Author sun
 * @Create 2025/1/15 10:19
 * @Version 1.0
 */
public class MyQueue {

    /**
     * 输入栈和输出栈
     */
    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    /**
     * push到输入栈
     *
     * @param x
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * 如果输出栈是空的，就将输入栈的元素全都放到输出栈
     *
     * @return
     */
    public int pop() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }

    /**
     * 如果输出栈是空的，就将输入栈的元素全都放到输出栈
     *
     * @return
     */
    public int peek() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek();
    }

    /**
     * 只有当输入栈和输出栈都不为空的时候才可以
     *
     * @return
     */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

2.思路

两个栈可以实现队列的原理就是，一个输入栈输入，然后需要输出的时候就将输入栈中的元素放到输出栈中，这样负负得正，就是顺序的了

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

1.答案

package com.sunxiansheng.arithmetic.day10;

import java.util.Stack;

/**
 * Description: 1047. 删除字符串中的所有相邻重复项
 *
 * @Author sun
 * @Create 2025/1/15 10:29
 * @Version 1.0
 */
public class t1047 {

    public static String removeDuplicates(String s) {
        // 栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // 当前元素
            char c = s.charAt(i);
            // 如果栈不为空，并且匹配成功的才会出栈，否则就是栈为空或者是栈不为空但是匹配失败的情况，就入栈
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        // 将栈中的元素倒序
        char[] chars = new char[stack.size()];
        for (int i = chars.length - 1; i >= 0; i--) {
            chars[i] = stack.pop();
        }
        return new String(chars);
    }
}

2.思路

如果栈不为空，并且匹配成功的才会出栈，否则就是栈为空或者是栈不为空但是匹配失败的情况，就入栈