队列和栈
先入先出的数据结构
在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。
如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。
队列 - 实现
为了实现队列，我们可以使用动态数组和指向队列头部的索引。
如上所述，队列应支持两种操作：入队和出队。2*入队会向队列追加一个新元素，而出队会删除第一个元素。 所以我们需要一个索引来指出起点。
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
class MyQueue {
private List<Integer> data;
private int p_start;
public MyQueue() {
data = new ArrayList<Integer>();
p_start = 0;
}
public boolean enQueue(int x) {
data.add(x);
return true;
}
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
p_start++;
return true;
}
public int Front() {
return data.get(p_start);
}
public boolean isEmpty() {
return p_start >= data.size();
}
};
public class Main {
public static void main(String[] args) {
MyQueue q = new MyQueue();
q.enQueue(5);
q.enQueue(3);
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
}
}
|
队列常用API
List接口中常用方法：
增加：add(int index, E element)
删除：remove(int index) remove(Object o)
修改：set(int index, E element)
查看：get(int index)
list.toArray(),list.size()
Math.random随机数、Math.abs绝对值、Math.ceil向上取值、Math.floor向下取值、Math.round四舍五入,Math.max,Math.min
循环队列
此前，我们提供了一种简单但低效的队列实现。
更有效的方法是使用循环队列。 具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。 目的是重用我们之前提到的被浪费的存储。
让我们通过一个示例来查看循环队列的工作原理。 你应该注意我们入队或出队元素时使用的策略。
问题1：设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
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
| class MyCircularQueue {
int size, p_start, p_end;
int[] nums;
public MyCircularQueue(int size) {
this.size = size;
nums = new int[size];
}
public boolean enQueue(int value) {
if (isFull())
return false;
nums[p_end % size] = value;
++p_end;
return true;
}
public boolean deQueue() {
if (isEmpty())
return false;
++p_start;
return true;
}
public int Front() {
return isEmpty() ? -1 : nums[p_start % size];
}
public int Rear() {
return isEmpty() ? -1 : nums[(p_end - 1) % size];
}
public boolean isEmpty() {
return p_start == p_end;
}
public boolean isFull() {
return p_end - p_start == size;
}
}
|
大多数流行语言都提供内置的队列库，因此您无需重新发明轮子。
如前所述，队列有两个重要的操作，入队 enqueue 和出队 dequeue。 此外，我们应该能够获得队列中的第一个元素，因为应该首先处理它。
下面是使用内置队列库及其常见操作的一些示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList();
System.out.println("第一个元素是: " + q.peek());
q.offer(5);
q.offer(13);
q.offer(8);
q.offer(6);
q.poll();
System.out.println("第一个元素是: " + q.peek());
System.out.println("队列的大小是: " + q.size());
}
}
|
队列和BFS
队列 & 栈 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
BFS模板
模板1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int BFS(Node root, Node target) {
Queue<Node> queue;
int step = 0;
将根节点添加到队列中;
while (队列不为空) {
step = step + 1;
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = 队列中的第一个节点;
如果 cur 是目标节点，则返回 step;
for (Node next : cur 的邻居节点) {
将 next 添加到队列中;
}
从队列中移除第一个节点;
}
}
return -1;
}
|
有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题。这是修改后的伪代码：
模板2
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
|
int BFS(Node root, Node target) {
Queue<Node> queue;
Set<Node> used;
int step = 0;
将根节点添加到队列中;
将根节点添加到已访问集合中;
while (队列不为空) {
step = step + 1;
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = 队列中的第一个节点;
如果 cur 是目标节点，则返回 step;
for (Node next : cur 的邻居节点) {
if (next 未被访问过) {
将 next 添加到队列中;
将 next 添加到已访问集合中;
}
}
从队列中移除第一个节点;
}
}
return -1;
}
|
问题1：岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
利用广度搜索的思想。
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| import java.util.LinkedList;
import java.util.Queue;
public class Solution {
private final static int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
private int rows;
private int cols;
private char[][] grid;
private boolean[][] visited;
public int numIslands(char[][] grid) {
rows = grid.length;
if (rows == 0) {
return 0;
}
cols = grid[0].length;
this.grid = grid;
visited = new boolean[rows][cols];
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
bfs(i, j);
count++;
}
}
}
return count;
}
private void bfs(int i, int j) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(i * cols + j);
visited[i][j] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
int curX = cur / cols;
int curY = cur % cols;
for (int k = 0; k < 4; k++) {
int newX = curX + DIRECTIONS[k][0];
int newY = curY + DIRECTIONS[k][1];
if (inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]) {
queue.offer(newX * cols + newY);
visited[newX][newY] = true;
}
}
}
}
private boolean inArea(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}
|
问题2：打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
1
2
3
4
5
6
| 输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
|
示例 2:
1
2
3
| 输入: deadends = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可 "0000" -> "0009"。
|
示例 3:
1
2
3
| 输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定
|
栈：后入先出的数据结构
在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。
与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 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
|
class MyStack {
private List<Integer> data;
public MyStack() {
data = new ArrayList<>();
}
public void push(int x) {
data.add(x);
}
public boolean isEmpty() {
return data.isEmpty();
}
public int top() {
return data.get(data.size() - 1);
}
public boolean pop() {
if (isEmpty()) {
return false;
}
data.remove(data.size() - 1);
return true;
}
};
public class Main {
public static void main(String[] args) {
MyStack s = new MyStack();
s.push(1);
s.push(2);
s.push(3);
for (int i = 0; i < 4; ++i) {
if (!s.isEmpty()) {
System.out.println(s.top());
}
System.out.println(s.pop());
}
}
}
|
栈常用API
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
s.push(5);
s.push(13);
s.push(8);
s.push(6);
if (s.empty() == true) {
System.out.println("栈为空！");
return;
}
s.pop();
System.out.println("栈顶元素是: " + s.peek());
System.out.println("栈的大小是: " + s.size());
}
}
|
栈和DFS
与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径。在本文中，我们提供了示例来解释 DFS 是如何工作的以及栈是如何逐步帮助 DFS 工作的。
队列 & 栈 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
