队列和栈

先入先出的数据结构

在 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
// 定义一个队列类 MyQueue
class MyQueue {
    // 用于存储队列中的元素
    private List<Integer> data;         
    // 指向队列的起始位置（队头元素的索引）
    private int p_start;            

    // 构造函数，初始化队列
    public MyQueue() {
        data = new ArrayList<Integer>(); // 初始化一个空的 ArrayList 来存储元素
        p_start = 0; // 初始化队头指针为 0
    }

    /**
     * 将元素插入队列的末尾
     * @param x 要插入的元素
     * @return 总是返回 true，表示操作成功
     */
    public boolean enQueue(int x) {
        data.add(x); // 将元素添加到列表的末尾
        return true; // 返回 true 表示插入成功
    }

    /**
     * 删除队列的队头元素
     * @return 如果队列为空，返回 false；否则返回 true
     */
    public boolean deQueue() {
        if (isEmpty() == true) { // 如果队列为空
            return false; // 返回 false 表示删除失败
        }
        p_start++; // 移动队头指针，表示删除队头元素
        return true; // 返回 true 表示删除成功
    }

    /**
     * 获取队列的队头元素
     * @return 队头元素的值
     */
    public int Front() {
        return data.get(p_start); // 返回队头指针指向的元素
    }

    /**
     * 检查队列是否为空
     * @return 如果队列为空，返回 true；否则返回 false
     */
    public boolean isEmpty() {
        return p_start >= data.size(); // 如果队头指针超出列表范围，队列为空
    }     
};

// 主类，用于测试 MyQueue 的功能
public class Main {
    public static void main(String[] args) {
        MyQueue q = new MyQueue(); // 创建一个 MyQueue 对象

        q.enQueue(5); // 将元素 5 插入队列
        q.enQueue(3); // 将元素 3 插入队列

        // 如果队列不为空，输出队头元素
        if (q.isEmpty() == false) {
            System.out.println(q.Front()); // 输出队头元素 5
        }

        q.deQueue(); // 删除队头元素 5

        // 如果队列不为空，输出队头元素
        if (q.isEmpty() == false) {
            System.out.println(q.Front()); // 输出队头元素 3
        }

        q.deQueue(); // 删除队头元素 3

        // 如果队列不为空，输出队头元素
        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
// "static void main" 必须定义在一个 public 类中。
public class Main {
    public static void main(String[] args) {
        // 1. 初始化一个队列。
        Queue<Integer> q = new LinkedList();
        // 2. 获取第一个元素 - 如果队列为空，返回 null。
        System.out.println("第一个元素是: " + q.peek());
        // 3. 添加新元素。在尾部添加
        q.offer(5);
        q.offer(13);
        q.offer(8);
        q.offer(6);
        // 4. 移除一个元素。移除的是头元素
        q.poll();
        // 5. 获取第一个元素。
        System.out.println("第一个元素是: " + q.peek());
        // 6. 获取队列的大小。
        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;       // 从根节点到当前节点所需的步数
    // 初始化
    将根节点添加到队列中;
    // 广度优先搜索 (BFS)
    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;          // 如果没有从根节点到目标节点的路径，返回 -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;       // 从根节点到当前节点所需的步数
    // 初始化
    将根节点添加到队列中;
    将根节点添加到已访问集合中;
    // 广度优先搜索 (BFS)
    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：岛屿数量

给你一个由 ‘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);//的作用是将二维坐标 (i, 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
解释：无法旋转到目标数字且不被锁定

栈：后入先出的数据结构

image-20250311140028616

在 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
// "static void main" 必须定义在一个 public 类中。
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);
    }
    /** 删除栈顶元素。如果操作成功，返回 true。 */
    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); // 将元素 1 压入栈
        s.push(2); // 将元素 2 压入栈
        s.push(3); // 将元素 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
// "static void main" 必须定义在一个 public 类中。
public class Main {
    public static void main(String[] args) {
        // 1. 初始化一个栈。
        Stack<Integer> s = new Stack<>();
        // 2. 添加新元素。
        s.push(5);
        s.push(13);
        s.push(8);
        s.push(6);
        // 3. 检查栈是否为空。
        if (s.empty() == true) {
            System.out.println("栈为空！");
            return;
        }
        // 4. 移除栈顶元素。
        s.pop();
        // 5. 获取栈顶元素。
        System.out.println("栈顶元素是: " + s.peek());
        // 6. 获取栈的大小。
        System.out.println("栈的大小是: " + s.size());
    }
}

栈和DFS

与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径。在本文中，我们提供了示例来解释 DFS 是如何工作的以及栈是如何逐步帮助 DFS 工作的。

队列 & 栈 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

DFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

总结

栈常用的API：

1
2
3
4
5
Stack<Integer> s1 = new Stack<>();
s1.peek();
s1.push();
s1.pop();
s1.isEmpty();

队列常用的API：

1
2
3
4
5
6
Queue<Integer> q1 = new LinkedList<>();
q1.offer(1);
q1.peek()); 
q1.poll(); 
q1.isEmpty();
q1.size();