理论基础
Stack
在 Java 中，栈（Stack）是一种后进先出（LIFO）的数据结构，用于存储元素。在栈中，只有栈顶的元素是可见的和可访问的，其他元素都被隐藏起来，直到栈顶的元素被移除或弹出。
Java 中的 java.util.Stack 类实现了栈的数据结构，并且是线程安全的，继承自 Vector 类。
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。
出栈：栈的删除操作叫做出栈。 出数据在栈顶 。
快速上手：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
stack.push("Java");
stack.push("Python");
stack.push("C++");
String topLanguage = stack.pop();
System.out.println("弹出栈顶元素：" + topLanguage);
String currentTop = stack.peek();
System.out.println("当前栈顶元素：" + currentTop);
if (stack.isEmpty()) {
System.out.println("栈为空");
} else {
System.out.println("栈不为空");
}
}
}
|
这个示例展示了栈的基本操作，包括压栈、弹栈、查看栈顶元素和判空。栈在 Java 中常用于处理需要后进先出顺序的场景，例如表达式求值、逆序输出等。
Queue
在 Java 中，队列（Queue）是一种先进先出（FIFO）的数据结构，用于存储元素，是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。
队列在 java.util 包中有多种实现，如 LinkedList、ArrayDeque 和 PriorityQueue，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear） 。
出队列：进行删除操作的一端称为队头（Head/Front）。
总之队列的头部是指最先被取出的元素，而尾部是指最先被插入的新元素。
快速上手：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5);
System.out.println(q.size());
System.out.println(q.peek());
q.poll();
System.out.println(q.poll());
if(q.isEmpty()){
System.out.println("队列空");
}else{
System.out.println(q.size());
}
}
|
这个示例展示了队列的基本操作，包括入队、出队、查看队头元素和判空。队列在 Java 中常用于实现任务调度、消息传递等场景，能够有效管理元素的顺序和执行顺序。
Deque
在 Java 中，Deque（双端队列）是一个接口，表示一种允许从队列两端进行插入和删除操作的集合。它继承自 Queue 接口，提供了比普通队列更灵活的操作方式，适用于需要在队列两端进行频繁插入和删除的场景。
常见的实现类有：
- ArrayDeque：基于动态数组实现，通常比
LinkedList 更快，特别是在大多数操作（如插入、删除）上，因为它不需要频繁地进行指针操作（如链表中的指针更新）。它的空间效率较高，但在某些极端情况下（如需要频繁扩容）低效。
- LinkedList：基于双向链表实现，适合用于需要频繁修改队列中间部分的场景。插入和删除操作的时间复杂度为常数时间
O(1)，但相对于 ArrayDeque，其内存开销较大，因为每个元素都需要存储额外的指针。
| 方法 |
功能 |
| offerFirst(E e) |
将元素插入队列的头部。 |
| offerLast(E e) |
将元素插入队列的尾部。 |
| pollFirst() |
删除并返回队列头部的元素。 |
| pollLast() |
删除并返回队列尾部的元素。 |
| peekFirst() |
返回队列头部的元素，不删除。 |
| peekLast() |
返回队列尾部的元素，不删除。 |
快速上手：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| import java.util.*;
public class DequeExample {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
System.out.println(deque);
deque.addFirst(0);
System.out.println(deque);
int first = deque.removeFirst();
System.out.println("Removed from front: " + first);
System.out.println(deque);
int last = deque.removeLast();
System.out.println("Removed from end: " + last);
System.out.println(deque);
int peekFirst = deque.getFirst();
int peekLast = deque.getLast();
System.out.println("First: " + peekFirst + ", Last: " + peekLast);
}
}
|
相互实现
用栈实现队列
232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class MyQueue {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
public void push(int x) {
stackIn.push(x);
}
public int pop() {
dumpstackIn();
return stackOut.pop();
}
public int peek() {
dumpstackIn();
return stackOut.peek();
}
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
private void dumpstackIn(){
if (!stackOut.isEmpty()) return;
while (!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
|
用队列实现栈
225.用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty())
queue2.offer(queue1.poll());
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
|
有效的括号
20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
思路
一开始我的思路是使用哈希表，因为只有三种括号，六个字符，可以创建一个长度为3的数组，每一位都代表一种括号。最后判断每一位是否为0。这种思路是错误的，因为括号存在顺序，需要匹配相对应的类型。
事实上，如果不匹配，只有三种情况：
- 括号类型不匹配
[ ( ] )
- 左边的括号多了
{{ }`
3. 右边的括号多了 `{ }}
思路是，遇到左括号就把对应类型的右括号放入栈里，这样依次向右遍历；遇到右括号就检查栈顶元素是否匹配，如果匹配则将此元素出栈，继续遍历，不匹配则直接终止判断返回false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()){
if (c == '(') {
stack.push(')');
} else if (c == '{'){
stack.push('}');
} else if (c == '['){
stack.push(']');
} else if ( stack.isEmpty() || c != stack.pop()){
return false;
}
}
return stack.isEmpty();
}
}
|
删除相邻重复项
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入：”abbaca”
输出：”ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：
1 <= s.length <= 105s 仅由小写英文字母组成。
思路
暴力
真的很暴力。超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public String removeDuplicates(String S) {
int now = S.length();
int next = 1;
while (now != next) {
now = S.length();
S = S.replace("aa", "").replace("bb", "").replace("cc", "").replace("dd", "")
.replace("ee", "").replace("ff", "").replace("gg", "").replace("hh", "")
.replace("ii", "").replace("jj", "").replace("kk", "").replace("ll", "")
.replace("mm", "").replace("nn", "").replace("oo", "").replace("pp", "")
.replace("qq", "").replace("rr", "").replace("ss", "").replace("tt", "")
.replace("uu", "").replace("vv", "").replace("ww", "").replace("xx", "")
.replace("yy", "").replace("zz", "");
next = S.length();
}
return S;
}
}
|
栈
将这个字符串里的每一位字符依次入栈，一旦发现栈顶的字符和将要入栈的字符一样，就直接出栈。在遍历完整个字符串以后，就可以保证整个栈里没有相邻重复项了。处理一下栈里的元素，反转成字符串即可。
栈的目的就是存放遍历过的元素，当遍历当前这个元素时，去栈里检查我们是不是遍历过相同数值的相邻元素。然后再去做对应的消除操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Solution {
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack<>();
for( char c : s.toCharArray() ) {
if( !stack.isEmpty() && stack.peek() == c ){
stack.pop();
}else {
stack.push(c);
}
}
StringBuilder result = new StringBuilder();
while ( !stack.isEmpty() ) {
result.append(stack.pop());
}
return result.reverse().toString();
}
}
|
逆波兰表达式求值
150. 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = [“2”,”1”,”+”,”3”,”*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,”13”,”5”,”/“,”+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
思路
典中典之逆波兰表达式，没做过的感觉没上过数据结构课。
五星上将麦克阿瑟说过：遇到这种逆波兰表达式，根据规则用栈处理就秒了。
注意减法和除法存在顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String s : tokens) {
if("+".equals(s)){
stack.push( stack.pop() + stack.pop() );
}else if("-".equals(s)){
stack.push( -(stack.pop() - stack.pop()) );
}else if("*".equals(s)){
stack.push( stack.pop() * stack.pop() );
}else if ("/".equals(s)) {
int num1 = stack.pop();
int num2 = stack.pop();
stack.push(num2 / num1);
}else{
stack.push(Integer.parseInt(s));
}
}
return stack.pop();
}
}
|
滑动窗口最大值
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
思路
暴力
最简单的思路就是每次更新窗口都遍历一次，找到最大值返回。这样的时间复杂度是O(n * k)，超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0)
return new int[0];
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
int max = nums[i];
for (int j = i + 1; j < i + k; j++)
max = Math.max(max, nums[j]);
result[i] = max;
}
return result;
}
}
|
单调队列
为了降低时间复杂度到O(n)，我们需要使用单调队列的方法。
简单来讲，就是需要自定义一个队列，这个队列内含有窗口里的元素，随着窗口的移动，队列也一进一出，每次移动之后，可以返回队列里面的最大值是什么。
首先我们知道要查询最大值，所以队列里的元素一定是要排序的，而且必须从队头到队尾递减，保证最大值放在队头，这样才可以在peek这个队列时直接返回最大值。但窗口移动的时候，队列就需要弹出元素，我们已经进行了排序，现在无法得知应该弹出哪一位元素。
其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素，同时保证队列里的元素数值是由大到小的。这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。这里我们需要保证从队头到队尾递减，也就是一个单调递减的队列。
就是说，我们需要实现以下功能：
add( )
向队列里加入新进入窗口的元素。为了保证单调递减，如果这个元素大于左侧元素，就意味着左侧的这个元素在新元素加入后，必不可能成为任何一个窗口内的最大值，可以把它从队列里直接删去。
poll( )
删除队列里离开窗口的元素。现在poll( )需要处理的一定是队列里的最大值。最大值需要主动从队列里删除的情况有且只有此元素已经不在窗口内，否则早就被更新掉了。
peek( )
返回队列里最大的值，就是返回队头的元素，peek一下就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) return nums;
int len = nums.length - k + 1;
int[] res = new int[len];
int num = 1;
MyQueue myQueue = new MyQueue();
for(int i = 0; i < k ; i++ ){
myQueue.add(nums[i]);
}
res[0] = myQueue.peek();
for (int i = k; i < nums.length; i++) {
myQueue.poll(nums[i - k]);
myQueue.add(nums[i]);
res[num++] = myQueue.peek();
}
return res;
}
}
class MyQueue{
Deque<Integer> deque = new LinkedList<>();
void poll(int val){
if( !deque.isEmpty() && val == deque.peek() ){
deque.poll();
}
}
void add(int val){
while(!deque.isEmpty() && val > deque.peekLast()){
deque.pollLast();
}
deque.offerLast(val);
}
int peek(){
return deque.peek();
}
}
|
实现的单调队列并不仅仅是对窗口里面的数进行排序，它的核心在于维护一个窗口。如果只是排序的话，和优先级队列就没有区别了。
