一、知识
栈是一种”操作受限”的线性表，只允许在一端插入和删除数据。后进者先出，先进者后出，这就是典型的“栈”结构。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
栈的空间复杂度为O(1)（这里需要n个空间保存数据并不是说空间复杂度即为O(n)，而是该n个空间是必须的无法省略），不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1) 。
Java中栈的实现：Vector类具有动态扩容和随机访问的特性，因此，继承了Vector类的Stack也同样具有这些特性，这恰好违背了Stack数据结构的设计原理，正因为如此，Java中的Stack一直被认为是糟糕的实现，官方也将Stack标志为“弃用”。官方推荐使用Deque（双端队列）接口来实现Stack。
二、应用
使用map存储配对的字符，当字符为map中的key时字符入栈，当字符不为map的key时字符出栈进行对比。
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
| public static boolean isValid(String s) {
int length = s.length();
if (length % 2 != 0) {
return false;
}
Map<Character, Character> map = new HashMap<>() {
{
put('(', ')');
put('[', ']');
put('{', '}');
}
};
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < length; i++) {
char elt = s.charAt(i);
if (map.containsKey(elt)) {
stack.push(elt);
continue;
}
if (stack.isEmpty() || map.get(stack.pop()) != elt) {
return false;
}
}
return stack.isEmpty();
}
|
使用两个栈，一个栈存储数据，一个栈存储最小值这样在常数时间内能找到最小值。
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
| class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack() {
stack = new LinkedList();
minStack = new LinkedList();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(minStack.peek(), val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
|
使用两个栈来实现队列，一个栈（tail）实现数据的入队，另外一个栈（head）实现数据的出队，当出队数据为空时判断tail栈是否存在数据，将数据添加至head栈实现数据的正序。
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
| public class MyQueue {
Deque<Integer> head;
Deque<Integer> tail;
public MyQueue() {
head = new LinkedList();
tail = new LinkedList();
}
public void push(int x) {
tail.push(x);
}
public int pop() {
exchange();
return head.pop();
}
public int peek() {
exchange();
return head.peek();
}
public boolean empty() {
return (head.isEmpty() && tail.isEmpty());
}
public void exchange() {
if (!head.isEmpty()) {
return;
}
if (!tail.isEmpty()) {
while (!tail.isEmpty()) {
head.push(tail.pop());
}
}
}
}
|
将括号前的符号存入栈中，括号中的计算都要变换符号，当括号结束再出栈变为括号之前的符号。
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
43
| class Solution {
public int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
int ret = 1;
int sum = 0;
int i = 0;
while (i < s.length()) {
char elt = s.charAt(i);
switch (elt) {
case ' ':
i++;
break;
case '+':
ret = stack.peek();
i++;
break;
case '-':
ret = -stack.peek();
i++;
break;
case '(':
stack.push(ret);
i++;
break;
case ')':
stack.pop();
i++;
break;
default:
long num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
i++;
}
sum += ret * num;
}
}
return sum;
}
}
|
逆波兰表达式主要有以下两个优点：
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
| public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque();
int length = tokens.length;
for (int i = 0; i < length; i++) {
String temp = tokens[i];
if (!isNumber(temp)) {
stack.push(Integer.valueOf(temp));
} else {
int num1 = stack.pop();
int num2 = stack.pop();
switch (temp) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num2 - num1);
break;
case "/":
stack.push(num2 / num1);
break;
case "*":
stack.push(num1 * num2);
break;
}
}
}
return stack.pop();
}
public boolean isNumber(String temp) {
return "+".equals(temp) || "*".equals(temp) || "-".equals(temp) || "/".equals(temp);
}
|
单调栈+哈希表：首先从后遍历数组nums2，单调栈用于存储当前位置后比当前元素大的元素，每次进行比较，当前元素小于栈内元素则当前元素后的最大元素为栈顶元素，否则将元素出栈找到最大的元素，不存在则为-1，使用map可以在遍历nums1数组时找到nums2对应位置的下个最大元素（也可以存储下标代替值）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int length = nums1.length;
int[] arr = new int[length];
Deque<Integer> stack = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = nums2.length - 1; i >= 0; i--) {
int temp = nums2[i];
while (!stack.isEmpty() && stack.peek() <= temp) {
stack.pop();
}
map.put(temp, stack.isEmpty() ? -1 : stack.peek());
stack.push(temp);
}
for (int i = 0; i < length; i++) {
arr[i] = map.get(nums1[i]);
}
return arr;
}
}
|
栈：将 ( 的下标压入栈中，当遇到 ) 时将出栈，通过栈是否为空判断是否为该 ) 是否存在对应的 (
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque();
int max = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
char elt = s.charAt(i);
if (elt == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
max = Math.max(max, i - stack.peek());
}
}
}
return max;
}
}
|