算法题目总结-栈和队列

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 == ']') {// 如果栈为空，就返回falseif (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.思路

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