参考链接：https://github.com/itcharge/LeetCode-Py

一、队列

1.1 简介

队列（Queue）：简称为队，一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。

把队列中允许插入的一端称为队尾（rear）；把允许删除的另一端称为队头（front）。当表中没有任何数据元素时，称之为空队。

队列有两种基本操作：插入操作和删除操作。

队列的插入操作又称为「入队」。
队列的删除操作又称为「出队」。

image.png

简单来说，队列是一种「先进先出（First In First Out）」的线性表，简称为「FIFO 结构」。

我们可以从两个方面来解释一下队列的定义：

第一个方面是「线性表」。
队列首先是一个线性表，队列中元素具有前驱后继的线性关系。队列中元素按照 $a_1, a_2, ... , a_n$ 的次序依次入队。队头元素为 $a_1$ ，队尾元素为 $a_n$ 。
第二个方面是「先进先出原则」。
根据队列的定义，最先进入队列的元素在队头，最后进入队列的元素在队尾。每次删除的总是队列中的队头元素，即最先进入队列的元素。也就是说，元素进入队列或者退出队列是按照「先进先出（First In First Out）」的原则进行的。

1.2 队列的顺序存储与链式存储

和线性表类似，队列有两种存储表示方法：「顺序存储的队列」和「链式存储的队列」。

顺序存储的队列：利用一组地址连续的存储单元依次存放队列中从队头到队尾的元素，同时使用指针 front 指向队头元素在队列中的位置，使用指针 rear 指示队尾元素在队列中的位置。
链式存储的队列：利用单链表的方式来实现队列。队列中元素按照插入顺序依次插入到链表的第一个节点之后，并使用队头指针 front 指向链表头节点位置，也就是队头元素，rear 指向链表尾部位置，也就是队尾元素。
注意：front 和 rear 的指向位置并不完全固定。有时候算法设计上的方便以及代码简洁，也会使 front 指向队头元素所在位置的前一个位置。rear 也可能指向队尾元素在队列位置的下一个位置。具体还是要看算法是如何实现的。

队列的基本操作

初始化空队列：创建一个空队列，定义队列的大小 size，以及队头元素指针 front，队尾指针 rear。
判断队列是否为空：当队列为空时，返回 True。当队列不为空时，返回 False。一般只用于队列中删除操作和获取队头元素操作中。
判断队列是否已满：当队列已满时，返回 True，当队列未满时，返回 False。一般只用于顺序队列中插入元素操作中。
插入元素（入队）：相当于在线性表最后元素后面插入一个新的数据元素。并改变队列顶指针 top 的指向位置。
删除元素（出队）：相当于在线性表最后元素后面删除最后一个数据元素。并改变队列顶指针 top 的指向位置。
获取队列队头元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作并不改变队列顶指针 top 的指向位置。

队列的顺序存储实现
队列最简单的实现方式就是借助于一个数组来描述队列的顺序存储结构。在 Python 中我们可以借助列表 list 来实现。

image.png

为了算法设计上的方便以及算法本身的简单，约定：队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置。

初始化时：创建一个空队列 self.queue，定义队列大小 self.size。令队头指针 self.front 和队尾指针 self.rear 都指向 -1。即 self.front = self.rear = -1。
判断队列为空：根据 self.front 和 self.rear 的指向位置关系进行判断。如果对头指针 self.front 和队尾指针 self.rear 相等，则说明队列为空。
判断队列为满：如果 self.rear 指向队列最后一个位置，即 self.rear == self.size - 1，则说明队列已满。
获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.front 指向队头元素所在位置的前一个位置，所以队头元素在 self.front 后面一个位置上，返回 self.queue[self.front + 1]。
获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 self.queue[self.rear]。
入队操作：先判断队列是否已满，已满直接抛出异常。如果不满，则将队尾指针 self.rear 向右移动一位，并进行赋值操作。此时 self.rear 指向队尾元素。
出队操作：先判断队列是否为空，为空直接抛出异常。如果不为空，则将队头指针 self.front 指向元素赋值为 None，并将 self.front 向右移动一位。

class Queue:
    # 初始化空队列
    def __init__(self, size=100):
        self.size = size
        self.queue = [None for _ in range(size)]
        self.front = -1
        self.rear = -1
        
    # 判断队列是否为空
    def is_empty(self):
        return self.front == self.rear
    
    # 判断队列是否已满
    def is_full(self):
        return self.rear + 1 == self.size
    
    # 入队操作
    def enqueue(self, value):
        if self.is_full():
            raise Exception('Queue is full')
        else:
            self.rear += 1
            self.queue[self.rear] = value
            
    # 出队操作
    def dequeue(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            self.front += 1
            return self.queue[self.front]
        
    # 获取队头元素
    def front_value(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            return self.queue[self.front + 1]
    
    # 获取队尾元素
    def rear_value(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            return self.queue[self.rear]

循环队列的顺序存储实现
在队列的顺序存储实现中，当队列中第 0 ~ size - 1 位置均被队列元素占用时，有 self.rear == self.size - 1，队列已满，再进行入队操作就会抛出队列已满的异常。

此外，由于出队操作总是删除当前的队头元素，将 self.front 进行右移，而插入操作又总是在队尾进行。经过不断的出队、入队操作，队列的变化就像是使队列整体向右移动。当队尾指针 self.rear == self.size - 1 时，此时再进行入队操作就又抛出队列已满的异常。而之前因为出队操作而产生空余位置也没有利用上，这就造成了「假溢出」问题。

为了解决「假溢出」问题，有两种做法：

第一种：每一次删除队头元素之后，就将整个队列往前移动 1 个位置。
其代码如下所示：

# 出队操作
def dequeue(self):
    if self.is_empty():
        raise Exception('Queue is empty')
    else:
        value = self.queue[0]
        for i in range(self.rear):
            self.queue[i] = self.queue[i + 1]
        return value

这种情况下，队头指针似乎用不到了。因为队头指针总是在队列的第 0 个位置。但是因为删除操作涉及到整个队列元素的移动，所以每次删除操作的时间复杂度就从 $O(1)$ 变为了 $O(n)$ 。这种方式不太可取。
第二种：将队列想象成为头尾相连的循环表，利用数学中的求模运算，使得空间得以重复利用，这样就解决了问题。
这样在进行插入操作时，如果队列的第 self.size - 1 个位置被占用之后，只要队列前面还有可用空间，新的元素加入队列时就可以从第 0 个位置开始继续插入。

约定：self.size 为循环队列的最大元素个数。队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置。则：

入队时，队尾指针循环前进 1 个位置，即 self.rear = (self.rear + 1) % self.size。
出队时，队头指针循环前进 1 个位置，即 self.front = (self.front + 1) % self.size。
注意：循环队列在一开始初始化，队列为空时，self.front 等于 self.rear。而当充满队列后，self.front 还是等于 self.rear。这种情况下就无法判断「队列为空」还是「队列为满」了。

为了区分循环队列中「队列为空」还是「队列已满」的情况，有多种处理方式：
方式 1：增加表示队列中元素个数的变量 self.count，用来以区分队列已满还是队列为空。在入队、出队过程中不断更新元素个数 self.count 的值。
队列已满条件为：队列中元素个数等于队列整体容量，即 self.count == self.size，
队空为空条件为：队列中元素个数等于 0，即 self.count == 0。
方式 2：增加标记变量 self.tag，用来以区分队列已满还是队列为空。
队列已满条件为：self.tag == 1 的情况下，因插入导致 self.front == self.rear。
队列为空条件为：在 self.tag == 0 的情况下，因删除导致 self.front == self.rear。
方式 3：特意空出来一个位置用于区分队列已满还是队列为空。入队时少用一个队列单元，即约定以「队头指针在队尾指针的下一位置」作为队满的标志。
队列已满条件为：队头指针在队尾指针的下一位置，即 (self.rear + 1) % self.size == self.front。
队列为空条件为：队头指针等于队尾指针，即 self.front == self.rear。

image.png

class Queue:
    # 初始化空队列
    def __init__(self, size=100):
        self.size = size + 1
        self.queue = [None for _ in range(size + 1)]
        self.front = 0
        self.rear = 0
        
    # 判断队列是否为空
    def is_empty(self):
        return self.front == self.rear
    
    # 判断队列是否已满
    def is_full(self):
        return (self.rear + 1) % self.size == self.front
    
    # 入队操作
    def enqueue(self, value):
        if self.is_full():
            raise Exception('Queue is full')
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = value
            
    # 出队操作
    def dequeue(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        
    # 获取队头元素
    def front_value(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            value = self.queue[(self.front + 1) % self.size]
            return value
        
    # 获取队尾元素
    def rear_value(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            value = self.queue[self.rear]
            return value

队列的链式存储实现
对于在使用过程中数据元素变动较大，或者说频繁进行插入和删除操作的数据结构来说，采用链式存储结构比顺序存储结构更加合适。

链式存储中，用一个线性链表来表示队列，队列中的每一个元素对应链表中的一个链节点。然后把线性链表的第 1 个节点定义为队头指针 front，在链表最后的链节点建立指针 rear 作为队尾指针。并且限定只能在链表队头进行删除操作，在链表队尾进行插入操作，这样整个线性链表就构成了一个队列。

image.png

约定：队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置。

初始化时：建立一个链表头节点 self.head，令队头指针 self.front 和队尾指针 self.rear 都指向 head。即 self.front = self.rear = head。
判断队列为空：根据 self.front 和 self.rear 的指向位置进行判断。根据约定，如果对头指针 self.front 等于队尾指针 self.rear，则说明队列为空。
获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.front 指向队头元素所在位置的前一个位置，所以队头元素在 self.front 后一个位置上，返回 self.front.next.value。
获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 self.rear.value。
入队操作：创建值为 value 的链表节点，插入到链表末尾，并令队尾指针 self.rear 沿着链表移动 1 位到链表末尾。此时 self.rear 指向队尾元素。
出队操作：先判断队列是否为空，为空直接抛出异常。如果不为空，则获取队头指针 self.front 下一个位置节点上的值，并将 self.front 沿着链表移动 1 位。如果 self.front 下一个位置是 self.rear，则说明队列为空，此时，将 self.rear 赋值为 self.front，令其相等。

队列的链式存储实现代码

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
class Queue:
    # 初始化空队列
    def __init__(self):
        head = Node(0)
        self.front = head
        self.rear = head
    
    # 判断队列是否为空
    def is_empty(self):
        return self.front == self.rear
    
    # 入队操作
    def enqueue(self, value):
        node = Node(value)
        self.rear.next = node
        self.rear = node
    
    # 出队操作
    def dequeue(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            node = self.front.next
            self.front.next = node.next
            if self.rear == node:
                self.rear = self.front
            value = node.value
            del node
            return value
            
    # 获取队头元素
    def front_value(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            return self.front.next.value
        
    # 获取队尾元素
    def rear_value(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        else:
            return self.rear.value

二、广度优先搜索

2.1 简介

广度优先搜索算法（Breadth First Search）：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止。

广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问，后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点，所以广度优先搜索可以通过「队列」来实现。

2.2 过程演示

以一个无向图为例，演示一下广度优先搜索的过程。

# 定义无向图结构
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

image.png

其对应的动态演示图如下所示。

image.png

2.3 基于队列实现的广度优先搜索

实现步骤

graph 为存储无向图的字典变量，start 为开始节点。
然后定义 visited 为标记访问节点的 set 集合变量。定义 q 为存放节点的队列。
首先将起始节点放入队列 q中，即 q.put(start)。并将其标记为访问，即 visited.add(start)。
从队列中取出第一个节点 node_u。访问节点 node_u，并对节点进行相关操作（看具体题目要求）。
遍历与节点 node_u 相连并构成边的节点 node_v。
- 如果 node_v 没有被访问过，则将 node_v 节点放入队列中，并标记访问，即 q.append(node_v)，visited.add(node_v)。
重复步骤 4 ~ 5，直到 q 为空。

import collections

def bfs(graph, start):
    visited = set(start)
    q = collections.deque([start])
    
    while q:
        node_u = q.popleft()
        print(node_u)
        for node_v in graph[node_u]:
            if node_v not in visited:
                visited.add(node_v)
                q.append(node_v)

2.4 应用

无向图中连通分量的数目、岛屿的最大面积等。

三、总结

本章节主要学习了队列和广度优先搜索方法，队列其实跟栈很相似，只是进出顺序不一样。总的来说，知识点很全面，但是需要自己多花时间去理解去实践应用。

【DW1月-力扣刷题】Task04 队列与广度优先搜索

【DW1月-力扣刷题】Task04 队列与广度优先搜索

一、队列

1.1 简介

1.2 队列的顺序存储与链式存储

二、广度优先搜索

2.1 简介

2.2 过程演示

2.3 基于队列实现的广度优先搜索

2.4 应用

三、总结

推荐阅读更多精彩内容