数据结构-栈与队列笔记

普通的双端队列

用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

import java.util.ArrayDeque;
import java.util.Deque;class MyQueue {// 使用双端队列（Deque）来实现一个队列Deque<Integer> input; // 用于存放新加入的元素Deque<Integer> output; // 用于存放准备出队的元素public MyQueue() {input = new ArrayDeque<>(); // 初始化input队列output = new ArrayDeque<>(); // 初始化output队列}public void push(int x) {// 将元素x添加到input队列的前端input.addFirst(x);}public int pop() {// 首先调用exchange方法，确保output队列中有元素exchange();// 从output队列的前端移除并返回元素return output.removeFirst();}public int peek() {// 首先调用exchange方法，确保output队列中有元素exchange();// 返回output队列前端的元素，但不移除它return output.getFirst();}public boolean empty() {// 如果input和output队列都为空，则返回true，表示队列为空return input.isEmpty() && output.isEmpty();}public void exchange() {// 如果output队列不为空，则不需要交换，直接返回if (!output.isEmpty()) {return;}// 当output队列为空时，将input队列中的所有元素转移到output队列while (!input.isEmpty()) {int temp = input.removeFirst(); // 从input队列前端移除元素output.addFirst(temp); // 将移除的元素添加到output队列的前端}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue(); // 创建MyQueue对象* obj.push(x); // 将元素x添加到队列* int param_2 = obj.pop(); // 移除并返回队列前端的元素* int param_3 = obj.peek(); // 返回队列前端的元素，但不移除* boolean param_4 = obj.empty(); // 检查队列是否为空*/

有效的括号（难）

20. 有效的括号 - 力扣（LeetCode）

import java.util.ArrayDeque;
import java.util.Deque;class Solution {public boolean isValid(String s) {// 使用双端队列（Deque）来存储尚未匹配的右括号Deque<Character> deque = new ArrayDeque<>();// 遍历字符串s中的每个字符for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i); // 获取当前遍历到的字符// 如果当前字符是左括号，将其对应的右括号添加到队列的前端if (ch == '(') {deque.addFirst(')');} else if (ch == '{') {deque.addFirst('}');} else if (ch == '[') {deque.addFirst(']');} else {// 如果当前字符是右括号// 检查栈是否为空或者栈顶元素是否与当前右括号匹配if (deque.isEmpty() || ch != deque.getFirst()) {// 如果栈为空或者栈顶元素不匹配，说明括号序列无效，返回falsereturn false;} else {// 如果栈顶元素与当前右括号匹配，从队列中移除栈顶元素deque.removeFirst();}}}// 最后检查栈是否为空，如果为空，说明所有括号都正确匹配，返回true；否则返回falsereturn deque.isEmpty();}
}

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

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringBuilder;class Solution {public String removeDuplicates(String s) {// 使用双端队列（Deque）来存储不重复的字符Deque<Character> deque = new ArrayDeque<>();// 遍历字符串s中的每个字符for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i); // 获取当前遍历到的字符// 如果队列不为空且队列的第一个字符与当前字符相同if (!deque.isEmpty() && deque.getFirst() == ch) {// 移除队列中的第一个字符deque.removeFirst();} else {// 否则，将当前字符添加到队列的前端deque.addFirst(ch);}}// 使用StringBuilder来构建最终的字符串StringBuilder sb = new StringBuilder();// 遍历队列，将队列中的字符添加到StringBuilder中while (!deque.isEmpty()) {sb.append(deque.removeLast()); // 从队列的后端移除字符并添加到StringBuilder}// 将StringBuilder转换为字符串并返回return sb.toString();}
}

逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

import java.util.ArrayDeque;
import java.util.Deque;class Solution {public int evalRPN(String[] tokens) {// 使用双端队列（Deque）来存储操作数Deque<Integer> deque = new ArrayDeque<>();// 遍历tokens数组中的每个元素for (int i = 0; i < tokens.length; i++) {String ch = tokens[i]; // 获取当前遍历到的元素// 如果当前元素是运算符if (ch.equals("+")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的和，并将其压入队列前端int sum = first + second;deque.addFirst(sum);} else if (ch.equals("-")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的差，并将其压入队列前端int sum = second - first;deque.addFirst(sum);} else if (ch.equals("*")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的乘积，并将其压入队列前端int sum = first * second;deque.addFirst(sum);} else if (ch.equals("/")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的商，并将其压入队列前端// 注意：这里假设不会出现除以零的情况int sum = second / first;deque.addFirst(sum);} else {// 如果当前元素不是运算符，将其转换为整数并压入队列前端deque.addFirst(Integer.parseInt(ch));}}// 返回队列中的第一个元素，即表达式的结果return deque.getFirst();}
}

单调队列

滑动窗口最大值（难）

239. 滑动窗口最大值 - 力扣（LeetCode）

import java.util.ArrayDeque;
import java.util.Deque;class MyDeque {Deque<Integer> deque; // 双端队列，用于存储元素MyDeque() {deque = new ArrayDeque<>(); // 初始化双端队列}// 尝试移除队列头部的元素，如果头部元素等于valboolean remove(int val) {if (!deque.isEmpty() && deque.getFirst() == val) {deque.removeFirst(); // 移除队列头部元素}return true; // 无论是否移除，都返回true}// 将val添加到队列中，移除所有比val小的尾部元素boolean add(int val) {while (!deque.isEmpty() && deque.getLast() < val) {deque.removeLast(); // 移除队列尾部元素}deque.addLast(val); // 添加val到队列尾部return true; // 返回true表示添加成功}// 返回队列头部的元素，即当前窗口中的最大值int maxValue() {return deque.getFirst(); // 返回队列头部元素}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length; // 输入数组的长度int[] ret = new int[n - k + 1]; // 存储每个窗口的最大值MyDeque deque = new MyDeque(); // 创建MyDeque对象// 将数组的前k个元素添加到队列中for (int i = 0; i < k; i++) {deque.add(nums[i]);}// 将第一个窗口的最大值添加到结果数组中int index = 0;ret[index++] = deque.maxValue();// 遍历数组，从索引k到n-1for (int i = k; i < n; i++) {// 移除窗口外的元素deque.remove(nums[i - k]);// 将当前元素添加到队列中deque.add(nums[i]);// 将当前窗口的最大值添加到结果数组中ret[index++] = deque.maxValue();}return ret; // 返回结果数组}
}

优先队列

前 K 个高频元素（难）

. - 力扣（LeetCode）

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;class Solution {public int[] topKFrequent(int[] nums, int k) {// 创建一个HashMap来存储数组中每个数字的出现次数HashMap<Integer, Integer> hashmap = new HashMap<>();for (int num : nums) {// 对于数组中的每个数字，如果它已经在HashMap中，则增加其计数，否则添加到HashMap中并设置计数为1hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);}// 创建一个小顶堆（PriorityQueue），用于存储二元组（数字，出现次数）// 比较器使用Lambda表达式，根据二元组的第二个元素（出现次数）来比较PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {// 遍历HashMap中的每个条目if (pq.size() < k) {// 如果堆的大小小于k，则直接添加当前条目pq.add(new int[]{entry.getKey(), entry.getValue()});} else {// 如果堆的大小已经达到k，并且堆顶元素的出现次数小于当前条目的出现次数if (pq.peek()[1] < entry.getValue()) {// 移除堆顶元素（出现次数最小的元素）pq.poll();// 添加当前条目pq.add(new int[]{entry.getKey(), entry.getValue()});}}}// 创建一个数组来存储最终的k个最频繁出现的数字int[] ret = new int[k];for (int i = 0; i < k; i++) {// 依次从堆中取出元素，填充到数组中ret[i] = pq.poll()[0];}// 返回结果数组return ret;    }
}