堆栈(Stack)和队列(Queue),这里Stack可以叫做堆栈,也可以叫做栈。但是不能叫做堆,因为堆是Heap,是另外一种数据结构。
Stack
FILO: First In Last Out 先入后出
- Array or Linked List
最近相关性都可以是用栈解决
Queue
FIFO: First In First Out 先入先出
- Array or Doubly Linked List
Common Data Structure Operations
图片来源 http://www.bigocheatsheet.com/
- Time complexity 时间复杂度
- Space Complexity 空间复杂度
- Average 平均
- Worst 最坏
- Access 获取
- Search 搜索
- Insertion 插入
- Deletion 删除部分
有效的括号
给定一个只包括 '(',')','{','}','[',']'
的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
1 | 示例 1: |
1 | private static Map<Character, Character> baseBracketMap = new HashMap<>(); |
在学习stack之前,是没有想到太好的使用别的数据结构解决该问题的,但是使用到stack后就可以相对轻松的解决该问题。
- 开括号需要push到stack中
- 闭括号要pop出进行匹配是否为对应括号类型
- 最后匹配完全部元素后,stack需要是空的,否则说明存在没有闭和的开括号
- 代码优化点: Map使用闭括号作为key,方便进行第一次合法比较
复杂度分析
- 时间复杂度:O(n),因为我们一次只遍历给定的字符串中的一个字符并在栈上进行O(1) 的推入和弹出操作。
- 空间复杂度:O(n),当我们将所有的开括号都推到栈上时以及在最糟糕的情况下,我们最终要把所有括号推到栈上。例如
((((((((((
用栈实现队列
1 | 使用栈实现队列的下列操作: |
双栈处理
主要的思路是通过双栈的数据结构,通过不断pop和push的操作来调换位置。
入队 - O(n), 出队 - O(1),在push的时候做文章
pop、peek还是通过s1直接进行操作,但在push的时候,通过两个栈对数据位置进行调换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
38class MyQueue2 {
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();
private Integer front;
public MyQueue2() {
}
public void push(int x) {
if (s1.empty()) {
front = x;
}
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
s2.push(x);
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
public int pop() {
int i = s1.pop();
if (!s1.empty()) {
front = s1.peek();
}
return i;
}
public int peek() {
return front;
}
public boolean empty() {
return s1.isEmpty();
}
}
复杂度分析
入队
- 时间复杂度:O(n): 对于除了新元素之外的所有元素,它们都会被压入两次,弹出两次。新元素只被压入一次,弹出一次。这个过程产生了 4n + 2 次操作,其中n是队列的大小。由于 压入 操作和 弹出 操作的时间复杂度为 O(1), 所以时间复杂度为 O(n)。
- 空间复杂度:O(n): 需要额外的内存来存储队列中的元素。
出队、判空
- 时间复杂度:O(1)
- 空间复杂度:O(1)
入队 - O(1),出队 - 摊还复杂度 O(1),在pop的时候做文章
新元素总是压入 s1 的栈顶,同时我们会把 s1 中压入的第一个元素赋值给作为队首元素的 front 变量。
根据栈 LIFO 的特性,s1 中第一个压入的元素在栈底。为了弹出 s1 的栈底元素,我们得把 s1 中所有的元素全部弹出,再把它们压入到另一个栈 s2 中,这个操作会让元素的入栈顺序反转过来。通过这样的方式,s1 中栈底元素就变成了 s2 的栈顶元素,这样就可以直接从 s2 将它弹出了。一旦 s2 变空了,我们只需把 s1 中的元素再一次转移到 s2 就可以了。&oq=根据栈 LIFO 的特性,s1 中第一个压入的元素在栈底。为了弹出 s1 的栈底元素,我们得把 s1 中所有的元素全部弹出,再把它们压入到另一个栈 s2 中,这个操作会让元素的入栈顺序反转过来。通过这样的方式,s1 中栈底元素就变成了 s2 的栈顶元素,这样就可以直接从 s2 将它弹出了。一旦 s2 变空了,我们只需把 s1 中的元素再一次转移到 s2 就可以了。
极客时间中覃超讲解该题也是用的这个方法,简单理解就是两个Input栈、Output栈。push都放到Input,pop从Output出。如果output为空,则从input逐个pop到input中(顺序正好会调转)。
1 | class MyQueue3 { |
复杂度分析
入队
- 时间复杂度:O(1) 向栈压入元素的时间复杂度为O(1)
- 空间复杂度:O(n) 需要额外的内存来存储队列元素
出队
- 时间复杂度: 摊还复杂度 O(1),最坏情况下的时间复杂度 O(n)
在最坏情况下,s2 为空,算法需要从 s1 中弹出 n 个元素,然后再把这 n 个元素压入 s2,在这里nn代表队列的大小。这个过程产生了 2n 步操作,时间复杂度为 O(n)。但当 s2 非空时,算法就只有 O(1) 的时间复杂度。所以为什么叫做摊还复杂度O(1) 呢? 读了下一章你就知道了。 - 空间复杂度 :O(1)
使用队列实现栈
1 | 使用队列实现栈的下列操作: |
双队列 压入 -O(1), 弹出 -O(n)
双队列 压入 -O(n), 弹出 -O(1)
列出其中一种pop的时候做处理,push、top的时候从第一个队列中直接取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
35public class MyStack {
private Queue<Integer> q1 = new LinkedList();
private Queue<Integer> q2 = new LinkedList();
private int top;
public MyStack() {
}
public void push(int x) {
q1.add(x);
top = x;
}
public int pop() {
while (q1.size() > 1) {
top = q1.remove();
q2.add(top);
}
int i = q1.remove();
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
return i;
}
public int top() {
return top;
}
public boolean empty() {
return q1.isEmpty();
}
}
PriorityQueue 优先队列
正常入,按照优先级出。优先级是优先队列本身的一个属性,可以是最大的先出、最小的先出,或者是设置每个元素出现的次数等等。
- 插入操作: O(1)
- 取出操作: O(logN) 按照元素的优先级取出
实现机制
- Heap
- Binary 二叉堆
- Binomial 多项式堆
- Fibonacci 斐波那契堆
- Binary Search Tree 二叉搜索树