队列的基本概念
队列的定义
队列（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 指向队尾元素的下一个位置。
队列的顺序存储类型可描述为
代码语言：javascript复制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。
为了区分队空还是队满的情况，有三种处理方式：
- 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。队满条件：(self.rear 1)%self.max_size==self.front。队空条件仍：self.front==self.rear。队列中元素的个数：(self.rear-self.front self.max_size)%self.max_size。
- 类型中增设表示元素个数的数据成员，这样，队空的条件为 self.size==0；队满的条件为 self.size==self.max_size。这两种情况都有 self.front==self.rear。
- 类型中增设 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]
队列的链式存储结构
队列的链式存储
队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同）。
队列的链式存储类型可描述为
代码语言：javascript复制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 站账号：新时代的运筹帷幄，喜欢的可以关注一下，看完视频不要忘记一键三连啊！
