数据结构（4）：队列（上）

上回说到，栈常见的三个应用：括号匹配、表达式求值以及递归。这一会我们来看一看另一个操作受限的线性表：队列！

队列的基本概念

队列的定义

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操作特性是先进先出（First In Last Out，FIFO）。

队头（Front）。允许删除的一端，又称队首。

队尾（Rear）。允许插入的一端。

空队列。不含任何元素的空表。

队列常见的基本操作

__init__(self)：初始化队列，构造一个空队列 self。

is_empty(self)：判队列空，若队列 self 为空返回 True，否则返回 False。

en_queue(self, x)：入队，若队列 self 未满，将 x 加入，使之成为新的队尾。

de_queue(self)：出队，若队列 self 非空，删除队头元素，并返回。

get_head(self)：读队头元素，若队列 self 非空，则将队头元素返回。

队列的顺序存储结构

队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。

队列的顺序存储类型可描述为

class SqQueue:
    def __init__(self, max_size=50):
        self.max_size = max_size  # 定义队列中元素的最大个数
        self.data = [None]*max_size  # 存放队列元素
        self.front = self.rear = 0  # 队头指针和队尾指针

初始状态（队空条件）：self.front==self.rear==0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1。

出队操作：队不空时，先取队头元素值，再将队头指针加 1。

图（a）所示为队列的初始状态，有 self.front==self.rear==0 成立，该条件可以作为队列判空的条件。但能否用 self.rear==self.max_size 作为队列满的条件呢？显然不能，图（c）中，队列中仅有一个元素，但仍满足该条件。这时入队出现“上溢出”，但这种溢出并不是真正的溢出，在 self.data 数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。

循环队列

前面已指出了顺序队列的缺点，这里引出循环队列的概念。将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针 self.front=self.max_size-1 后，再前进一个位置就自动到 0，这可以利用除法取余运算（%）来实现。

初始时：self.front=self.rear=0。

队首指针进 1：self.front=(self.front+1)%self.max_size。

队尾指针进 1：self.rear=(self.rear+1)%self.max_size。

队列长度：(self.rear+self.max_size-self.front)%self.max_size。

那么，循环队列队空和队满的判断条件是什么呢？显然队空的条件是 self.front==self.rear。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，此时可以看出队满时也有 self.front==self.rear。

为了区分队空还是队满的情况，有三种处理方式：

1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。队满条件：(self.rear+1)%self.max_size==self.front。队空条件仍：self.front==self.rear。队列中元素的个数：(self.rear-self.front+self.max_size)%self.max_size。
2. 类型中增设表示元素个数的数据成员，这样，队空的条件为 self.size==0；队满的条件为 self.size==self.max_size。这两种情况都有 self.front==self.rear。
3. 类型中增设 tag 数据成员，以区分队满还是队空。self.tag 等于 0 时，若因删除导致 self.front==self.rear，则为队空；self.tag 等于 1 时，若因插入导致 self.front==self.rear，则为队满。

循环队列的操作

初始化

def __init__(self, max_size=50):  # 初始化
        self.max_size = max_size  # 定义队列中元素的最大个数
        self.data = [None]*max_size  # 存放队列元素
        self.front = self.rear = 0  # 队头指针和队尾指针

判队空

def is_empty(self):  # 判队空
        if self.rear == self.front:  # 队空条件
            return True
        return False

入队

def en_queue(self, x):  # 入队
        if (self.rear+1) % self.max_size == self.front:  # 队满则报错
            return
        self.data[self.rear] = x
        self.rear = (self.rear+1) % self.max_size  # 队尾指针加 1 取模

出队

def de_queue(self):  # 出队
        if self.rear == self.front:  # 队空则报错
            return
        x = self.data[self.front]
        self.front = (self.front+1) % self.max_size  # 队头指针加 1 取模
        return x

读队头元素

def get_head(self):  # 读队头元素
        if self.front == self.rear:
            return
        return self.data[self.front]

队列的链式存储结构

队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同）。

队列的链式存储类型可描述为

class LinkNode:  # 链式队列结点
    def __init__(self, data=0):
        self.data, self.next = data, None




class LinkQueue:  # 链式队列
    def __init__(self):
        self.front = self.rear = LinkNode()  # 队列的队头和队尾指针

当 self.front==None 且 self.rear==None 时，链式队列为空。

出队时，首先判断队是否为空，若不空，则取出队头元素，将其从链表中摘除，并让 self.front 指向下一个结点（若该结点为最后一个结点，则置 self.front 和 self.rear 都为 None）。入队时，建立一个新结点，将新结点插入到链表的尾部，并改让 self.rear 指向这个新插入的结点（若原队列为空队，则令 self.front 也指向该结点）。

不难看出，不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。

用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题。

链式队列的基本操作

初始化

def __init__(self):  # 初始化
        self.front = self.rear = LinkNode()  # 队列的队头和队尾指针

判队空

def is_empty(self):  # 判队空
        return True if self.front == self.rear else False

入队

def en_queue(self, x):  # 入队
        s = LinkNode(x)  # 创建新结点，插入到链尾
        self.rear.next = s
        self.rear = s

出队

def de_queue(self):
        if self.front == self.rear:  # 空队
            return
        p = self.front.next
        x = p.data
        self.front.next = p.next
        if self.rear == p:
            self.rear = self.front  # 若原队列中只有一个结点，删除后变空
        return x

读队头元素

def get_head(self):
        if self.front == self.rear:
            return
        return self.front.next.data

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。

总结

关于队列的定义以及基本操作的实现就介绍到这里，下回我们看到队列的应用。

当然，我从今年开始已经入驻 B 站了！下面给出 B 站账号：新时代的运筹帷幄，喜欢的可以关注一下，看完视频不要忘记一键三连啊！

今天的文章有不懂的可以后台回复“加群”，备注：Python 机器学习算法说书人，不备注可是会被拒绝的哦~！