数据结构-栈与队列笔记

普通的双端队列

验证图书取出顺序

class Solution {/*** 验证书籍的借阅顺序是否合法。* * @param putIn 表示放入书架的书籍序列。* @param takeOut 表示从书架取出的书籍序列。* @return 如果书籍的借阅顺序合法，返回 true；否则返回 false。*/public boolean validateBookSequences(int[] putIn, int[] takeOut) {// 创建一个双端队列，用于模拟书架上的书籍顺序。ArrayDeque<Integer> deque = new ArrayDeque<>();// 用于记录当前取出书籍的索引。int takeOutCount = 0;// 遍历所有放入书架的书籍。for (int i = 0; i < putIn.length; i++) {// 将书籍放入队列的前端。deque.addFirst(putIn[i]);// 当队列不为空，并且队列前端的书籍与要取出的书籍序列中的当前书籍相同时，// 将书籍从队列中取出，并更新取出书籍的索引。while (!deque.isEmpty() && takeOut[takeOutCount] == deque.getFirst()) {deque.removeFirst();takeOutCount++;}}// 如果所有书籍都按照借阅顺序被取出，队列应该为空，返回 true。// 如果队列不为空，说明有书籍没有按照借阅顺序被取出，返回 false。return deque.isEmpty();}
}

最小栈

import java.util.ArrayDeque;
import java.util.Deque;/*** 定义一个MinStack类，用于实现一个栈，该栈在进行push、pop、top操作的同时，能够以O(1)的时间复杂度返回栈中的最小元素。*/
class MinStack {// 使用双栈结构，一个用于正常的栈操作，另一个用于存储当前栈的最小值Deque<Integer> stack;Deque<Integer> minStack;/*** 初始化MinStack对象。*/public MinStack() {// 初始化两个栈stack = new ArrayDeque<Integer>();minStack = new ArrayDeque<Integer>();// 初始化minStack的栈顶元素为Integer.MAX_VALUE，这样可以保证后续入栈的元素能够正确更新最小值minStack.addFirst(Integer.MAX_VALUE);}/*** 将元素val压入栈中。* @param val 要压入栈的元素*/public void push(int val) {// 将元素val压入主栈stack.addFirst(val);// 将val和当前最小值比较，将较小的值压入minStack，保持minStack的栈顶元素始终为最小值minStack.addFirst(Math.min(minStack.getFirst(), val));}/*** 弹出栈顶元素。*/public void pop() {// 弹出主栈的栈顶元素stack.removeFirst();// 弹出minStack的栈顶元素，保持两个栈的同步minStack.removeFirst();}/*** 获取栈顶元素。* @return 栈顶元素*/public int top() {// 返回主栈的栈顶元素return stack.getFirst();}/*** 获取栈中的最小元素。* @return 栈中的最小元素*/public int getMin() {// 返回minStack的栈顶元素，即当前栈中的最小值return minStack.getFirst();  }
}/*** 下面是MinStack类的使用示例：* MinStack obj = new MinStack(); // 创建MinStack对象* obj.push(val); // 将元素val压入栈* obj.pop(); // 弹出栈顶元素* int param_3 = obj.top(); // 获取栈顶元素* int param_4 = obj.getMin(); // 获取栈中的最小元素*/

用栈实现队列

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();}
}

简化路径

class Solution {public String simplifyPath(String path) {// 使用"/"作为分隔符将路径字符串分割成字符串数组String[] strs = path.split("/");// 创建一个双端队列来模拟栈，用于存储路径中的有效部分ArrayDeque<String> stack = new ArrayDeque<>();// 遍历分割后的字符串数组for(String str : strs){// 如果当前字符串是".."，表示返回上一级目录if("..".equals(str)){// 如果栈不为空，则弹出栈顶元素，即移除当前路径的最后一部分if(!stack.isEmpty()){stack.removeLast();}// 如果当前字符串长度大于0且不是"."（当前目录）}else if(str.length() > 0 && !".".equals(str)){// 将当前字符串添加到栈中，表示路径的有效部分stack.addLast(str);}}// 创建StringBuilder用于构建简化后的路径字符串StringBuilder sb = new StringBuilder();// 如果栈为空，表示路径为根目录"/"if(stack.size() == 0){sb.append("/");}// 从栈底到栈顶遍历栈中的元素for(int i = stack.size() - 1; i >= 0; i--){// 添加"/"作为路径分隔符sb.append("/");// 将栈顶元素添加到StringBuilder中sb.append(stack.removeFirst());}// 返回构建好的简化路径字符串return sb.toString();}
}

基本计算器

class Solution {public int calculate(String s) {// sign表示当前数字的符号，初始为正int sign = 1;// 创建一个栈来存储当前的符号状态ArrayDeque<Integer> stack = new ArrayDeque<>();// 初始时将1压入栈中，表示最外层的符号为正stack.addLast(1);// 获取字符串的长度int n = s.length();// 初始化索引i为0int i = 0;// 初始化结果变量res为0int res = 0;// 遍历字符串swhile(i < n){// 获取当前字符char ch = s.charAt(i);// 如果当前字符是空格，跳过if(ch == ' '){i++;// 如果当前字符是左括号'('}else if(ch == '('){// 将当前符号压入栈中stack.add(sign);i++;// 如果当前字符是右括号')'}else if(ch == ')'){// 弹出栈顶符号，表示结束当前括号内的计算stack.removeLast();i++;// 如果当前字符是加号'+'}else if(ch == '+'){// 更新当前符号为栈顶符号sign = stack.getLast();i++;// 如果当前字符是减号'-'}else if(ch == '-'){// 更新当前符号为栈顶符号的相反数sign = -stack.getLast();i++;// 如果当前字符是数字}else{// 初始化当前数字num为0long num = 0;// 循环读取连续的数字字符while(i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9'){// 将当前数字字符转换为整数并累加到num中num = num * 10 + s.charAt(i) - '0';i++;}// 将当前数字乘以符号后累加到结果中res += sign * num;}}// 返回最终的计算结果return res;}
}

单调队列

滑动窗口最大值（难）

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;    }
}

顶堆（难）

LCR 160. 数据流中的中位数 - 力扣（LeetCode）

import java.util.PriorityQueue;
import java.util.Queue;/*** MedianFinder 类用于维护一个有序队列，以便快速找到中位数。* 它使用两个优先队列 a 和 b 来存储数字，其中 a 是最小堆，b 是最大堆。* 通过这种方式，中位数总是可以在 O(1) 时间内被检索。*/
public class MedianFinder {// 最小堆，用于存储较小的一半数字Queue<Integer> a;// 最大堆，用于存储较大的一半数字Queue<Integer> b;/*** 初始化 MedianFinder 的数据结构。*/public MedianFinder() {a = new PriorityQueue<>(); // 最小堆b = new PriorityQueue<>((x, y) -> (y - x)); // 最大堆}/*** 向数据结构中添加一个新的数字。* @param num 要添加的数字*/public void addNum(int num) {// 如果 a 的大小不等于 b 的大小，则将 num 添加到 a 中，然后将 a 的顶部元素移动到 b 中if(a.size() != b.size()){a.add(num);b.add(a.poll());}else{// 如果 a 和 b 的大小相等，则将 num 添加到 b 中，然后将 b 的顶部元素移动到 a 中b.add(num);a.add(b.poll());}}/*** 查找当前的中位数。* @return 中位数*/public double findMedian() {// 如果 a 的大小不等于 b 的大小，则中位数是 a 的顶部元素if(a.size() != b.size()){return a.peek();// 如果 a 和 b 的大小相等，则中位数是 a 和 b 的顶部元素的平均值}else{return (a.peek() + b.peek()) / 2.0;}}
}

丑数 II

class Solution {public int nthUglyNumber(int n) {// 使用优先队列（最小堆）来存储丑数，确保每次都能取出最小的丑数Queue<Integer> queue = new PriorityQueue<>();// 使用HashSet来存储已经生成过的丑数，避免重复Set<Integer> set = new HashSet<>();// 定义一个数组，包含丑数的质因数2、3、5int[] up = new int[]{2, 3, 5};// 将1加入队列和集合，因为1是所有丑数的起点queue.add(1);set.add(1);// 定义一个变量ret来存储最终的结果，即第n个丑数int ret = 0;// 循环n次，每次从队列中取出当前最小的丑数，并更新retfor(int i = 0 ; i < n; i++){// 从队列中取出当前最小的丑数int temp = queue.poll();ret = temp;// 遍历丑数的质因数for(int upNum : up){// 计算temp与当前质因数的乘积int t = temp * upNum;// 如果集合中没有t，则将t加入集合和队列if(!set.contains(t)){set.add(t);queue.add(t);}}}// 返回第n个丑数return ret;}
}