第5章队列
队列是一种先进先出的线性表，其操作规则类似于日常生活中人们的排队等候服务，在计算机系统中也有广泛的应用。本章主要介绍队列的概念、实现和应用，并简要说明双端队列和优先级队列。
视频讲解
5.1队列的基本概念
与栈一样，队列(queue)也是一种特殊的线性表。从逻辑结构角度看，队列与普通线性表和栈没有不同。将队列定义为n(n≥0)个数据元素构成的有限序列。当n=0时，称为空队列。当队列非空时，可记为Q=(a0, a1, a2,…, ai, …, an-1)，其中每个元素有一个固定的位序号。队列的特殊性是被限制在线性表的一端进行插入，在另一端进行删除，允许插入的一端称为队尾，允许删除的一端称为队首或队头。插入操作称为入队或进队，删除操作称为出队或退队，如图5.1所示。
图5.1队列示意图
队列的特点是最先入队的元素最先出队，即具有“先进先出(First In First Out，简称FIFO)”的特性。因此，队列也被称为先进先出表。例如，一队人在游乐场门口等待检票进入游乐场，最先来的人排在队头最先进入游乐场，而最后来的人排在队尾最后进入游乐场。商店、食堂、影院等服务场所也都按照队列先进先出的原则处理客户请求。
队列广泛应用于计算机系统的资源分配、数据缓冲和任务调度等场景中。例如，局域网用户申请使用网络打印机、多台终端访问Web服务器、键盘输入缓冲、操作系统的作业调度等都基于队列结构。
在程序设计中，队列也经常用于保存动态生成的多个任务或数据，以确保相应任务或数据按照先进先出的次序进行处理。
5.2队列的抽象数据类型
T类型元素构成的队列是由T类型元素构成的有限序列，并且具有以下基本操作：
(1) 构造一个空队列(__init__)。
(2) 判断一个队列是否为空(empty)。
(3) 求队列的长度(__len__)。
(4) 入队一个元素(append)。
(5) 读取队首元素并出队(serve)。
(6) 读取队首元素(retrieve)。
在以上ADT描述中，对队列逻辑结构的描述与对线性表和栈的描述完全一致，不同的是三者的操作不同，这里定义了对队列的6种操作。与栈的操作相比，不难发现，入队append操作类似于栈的push操作； 出队serve操作类似于栈的pop操作； 取队首retrieve操作则类似于栈的get_top操作。
视频讲解
5.3队列的顺序存储及实现
5.3.1物理模型法
在人们排队等候服务的物理模型中，新元素入队，即加入队列的尾部； 而当队首元素得到服务离开队列时，队列中剩余的所有元素都向前移动一个位置，从而保证队列的队首元素始终在队列的最前端，以便顺利得到服务。
在计算机中也可以参考物理模型表示队列。将队列从队首至队尾的所有元素依次存储在数组中，队首固定为0位置； 当入队一个新元素时，新元素加入数组的末尾，队尾后移一个位置； 当出队队首元素时，数组中所有的剩余元素依次前移一个位置，队尾前移一个位置。
在Python语言中，假设用列表entry存储队列，从entry的0号位置开始依次存放从队首到队尾的所有元素，entry［0］即为队首元素，列表尾部即是队尾位置，如图5.2所示。
图5.2用列表实现物理模型法表示的队列
这样，判别队列是否为空对应于判别列表entry是否为空，求队列的长度对应于对列表entry求长度； 入队操作对应于entry的append操作，出队操作对应于entry的pop(0)操作，取队首元素retrieve操作则对应于读取列表的0号元素。这些方法实现的语句都很简单，需要注意，在出队(serve)和读取队首(retrieve)方法中需要判别队列是否为空，如果为空，则需要返回操作失败的信息，这里用返回None来表示操作失败。以下是物理模型队列类PhysicalModelQueue的定义：
class PhysicalModelQueue:
def __init__(self):
self._entry = ［］
def __len__(self):
return len(self._entry)
def empty(self):
return not self._entry
def append(self, item):
self._entry.append(item)
def serve(self):
if not self.empty():
return self._entry.pop(0)
else:
return None
def retrieve(self):
if not self.empty():
return self._entry［0］
else:
return None
虽然这种方案实现起来很简单，但出队算法效率差。队列的出队操作对应于列表entry的pop(0)操作，0号位置后的n-1个元素将全部往前平移一个位置，元素的移动次数为n-1，算法的时间复杂度为O(n)。即使Python列表在实现pop操作时会采用内存批量复制的方法，性能有所提升，但时间复杂度的数量级没有变化。在Python语言中，向前平移的是元素指针； 而在C++等语言中，向前平移的是元素本身，如果每个元素个体很大，时间花费更大。总之，当队列长度较长时不建议使用物理模型法表示队列。
视频讲解
5.3.2线性顺序队列
假设使用初始容量为capacity的数组entry依次存储从队首到队尾的所有元素，并设两个整型下标front和rear分别指示队列的队首位置和队尾位置，如图5.3所示。
图5.3线性顺序队列示例
初始空队列时，生成初始容量为capacity的数组entry，front为0，rear为-1。入队时，队尾下标rear增1，元素放在新队尾位置； 出队时，获得队首元素，队首下标front增1。
当队列空时，front=rear+1，或者也可用front>rear来判别队列是否为空； 当队列满时，rear到达列表的尾端，即rear≥capacity-1。
以下为Python语言实现的线性顺序队列类LinearQueue。
class LinearQueue:
def __init__(self, cap=10):
self._capacity = cap
self._entry = ［None for x in range(0, self._capacity)］
self._front = 0
self._rear = -1
def empty(self):
return self._front > self._rear
def __len__(self):
return self._rear - self._front+1
def append(self, item):
if self._rear >= self._capacity - 1:
raise Exception("overflow")
else:
self._rear += 1
self._entry［self._rear］ = item
def serve(self):
if self.empty():
return None
else:
x = self._entry［self._front］
self._front += 1
return x
def retrieve(self):
if self.empty():
return None
else:
return self._entry［self._front］
假设队列容量capacity为6，如果对初始为空的线性顺序队列进行连续的入队和出队，通过图5.4的入队、出队操作看看会出现什么问题。
图5.4线性顺序队列的操作
从图5.4(a)的空队列开始，在经过了若干次入队和出队后，到达图5.4(d)的状态，队尾指示rear已到达数组尾部，无法再入队新的元素，是一种满的状态，如果需再入队，则会发生上溢出。也就是说，如果采用线性顺序队列存储结构，每出队一个元素，相应的空间就会遭到丢弃无法再利用。随着不断出队和入队，势必会产生这样的现象： 数组的前端还有空余位置(即front>0)，整个数组并没有占满，但队尾指示器rear已到达数组的末端而无法在当前空间入队新的元素，这种现象被称为虚溢出或假溢出。在最坏情况下，如对图5.4(d)所示的队列继续出队4次后变为图5.5所示的状态，此时队列是空的，但仍然无法在当前队列空间入队元素。
图5.5继续出队a2、a3、a4、a5
由此可见，如果队列的存储区容量固定，多次入队、出队可能会造成假溢出。即使队列存储区可以像Python中的list一样自动增长，但list首端由于出队浪费的空间无法再利用，从而导致空间利用率低下。因此必须对线性顺序队列方案加以改进才能达到实用的目的。
视频讲解
5.3.3循环队列
为了解决线性顺序队列的假溢出问题，可以将数组entry的空间假想为首尾相连，即认为capacity-1后的空间为0号位置。当rear到达数组末端capacity-1，而数组前端空间有空余(front>0)时，将入队的新元素添加到0号位置，同时队尾指示器rear调整为0。这就是队列顺序存储的循环队列方案，也是最常用、最有效的队列顺序存储方案。这种方案在线性顺序队列的基础上做了微调，入队时，如果rear下标在边界capacity-1处且数组前端空间有空余，则将rear调整为0后再入队； 出队时，如果front下标在边界capacity-1处，元素出队后将front调整为0。
在利用Python语言实现时，假设entry为存储队列元素的列表，入队新元素item的基本语句为：
self._rear = (self._rear+1) % self._capacity
self._entry［self._rear］ = item
出队队首元素的基本语句为：
item = self._entry［self._front］
self._front = (self._front+1) % self._capacity
初始化空队列的方法可为：
self._front = 0
self._rear = self._capacity -1
表5.1按照(a)~(f)的次序给出了容量为6的初始空循环队列依次入队、出队元素的过程。
对比表5.1中情况(a)和情况(c)的队空状态与情况(f)的队满状态，可以看到队空和队满时front和rear存在相同的关系，即front是rear的后一个位置，(rear+1) % capacity=front，所以无法利用rear和front区分队列的状态是空还是满。但是，在做入队操作时必须判别出队列是否已满； 在做出队操作时必须判别出队列是否为空。
为了能够区别队空和队满的不同状态，需要增加其他的处理措施。例如，可以在类中增加队空或队满标志变量，或者增加队列长度计数变量等。
假设采用损失一个空间的做法，即在如表5.1中情况(e)的状态下，在rear和front相差两个位置，即数组中还剩一个空余位置时即认为已经队满，无法继续入队。因此，
队空的判别条件为front == (rear+1) % capacity； 队满的判别条件为front == (rear+2) % capacity。
表5.1循环队列的入队、出队示例
(a) 初始化空队列，front=0，rear=5(b) 入队元素a0，front=0，rear=0
(c) 出队元素，front=1，rear=0，队列为空，rear和
front相差一个位置，即front=(rear+1)%capacity(d) 入队元素a1，front=1，rear=1
(e) 依次入队元素a2、a3、a4、a5，front=1，rear=5(f) 入队元素a6，front=1，rear=0，队列为满，
此时front和rear的关系跟情况(c)完全相同
利用Python语言实现的循环队列类CircularQueue可定义如下：
class CircularQueue:
def __init__(self, cap=10):
self._capacity = cap
self._entry = ［None for x in range(0, self._capacity)］
self._front = 0
self._rear = self._capacity -1
def empty(self):
returnself._front == (self._rear + 1) % self._capacity
def __len__(self):
return(self._rear - self._front + 1 + self._capacity) % self._capacity
def append(self, item):
if self._front == (self._rear + 2) % self._capacity:
self.resize(2 * len(self._entry))
self._rear = (self._rear + 1) % self._capacity
self._entry［self._rear］ = item
def resize(self, cap):
old = self._entry #用old指示原空间
self._entry = ［None］ * cap#entry指示新分配空间
p = self._front#p在原空间中移动
k = 0#k在新空间中移动
while p != self._rear:
self._entry［k］ = old［p］#将原空间p位置的数据复制到新空间的k位置
p = (1 + p) % self._capacity
k += 1
self._entry［k］ = old［self._rear］#最后一个队尾元素的复制
self._front = 0
self._rear = k
self._capacity = cap
def serve(self):
if self.empty():#若队列为空，则出队失败，返回None
return None
else:#非空，获得队首元素item，更新front下标，返回item
item = self._entry［self._front］
self._front = (self._front + 1) % self._capacity
return item
def retrieve(self):
if self.empty():#若队列为空，返回None
return None
else:
return self._entry［self._front］#非空，返回队首元素
在入队时遇到队满情况(还有一个剩余空间)，append方法调用resize方法扩大一倍空间，并把原队列从队首至队尾的所有元素复制到新列表空间从0号开始的连续位置。当空间已足够，接着更新rear为(rear + 1) % capacity，并将新元素item放在rear所指的位置。由于采用翻倍策略进行扩容，入队算法的摊销时间复杂度为O(1)。
在循环队列下，出队算法的时间复杂度为O(1)。
视频讲解
5.4队列的链式存储及实现
与线性表和栈的链式存储相同，当借助链表存储队列时，在存储队列中每个元素的同时附加存储一个指针，指向其后继元素。所以，队列中每个元素的存储映像也包含两部分——元素值部分和指针部分，即第3章中所描述的结点。以链式存储结构表示的队列简称为链队列。
1. 链队列结点类
链队列的结点结构与3.4.1节所描述的单链表结点结构一致，在类定义时仅修改了类名，定义如下：
class QueueNode:
def __init__(self, data, link=None):
self.entry = data
self.next = link
2. 链队列类
假设队列中有n个元素，从队首到队尾分别为a0, a1, …, an-1，则队列非空时链队列的存储示意图如图5.6(a)所示。与单链表类似，通常在链队列中加上表头结点。为方便对队列操作，给链队列设front和rear指针。当队列非空时，front和rear分别指示表头结点和队尾结点，如图5.6(a)所示； 当队列为空时，front和rear都指向表头结点，如图5.6(b)所示。
图5.6队列的链式结构
链队列类LinkedQueue的定义框架如下：
from QueueNode import QueueNode
class LinkedQueue:
def __init__(self):
def empty(self):
def __len__(self):
def append(self, item):
def serve(self):
def retrieve(self):
如下__init__方法初始化一个空队列，即生成表头结点，将指针front和rear都指向该表头结点。
def __init__(self):
self._front = self._rear = QueueNode(None)
如下empty方法判别指针front和rear是否指向同一个结点，如果是，则队列为空。
def empty(self):
return self._front == self._rear
求队列长度需要从队首结点开始顺着链对链表中的所有结点进行计数，实现代码如下：
def __len__(self):
p = self._front.next
count = 0
while p:
count += 1
p = p.next
return count
图5.7示意了链队列的入队操作。首先生成一个值为item的新结点new_rear，接着将rear所指原队尾结点的指针域指向新结点new_rear，最后将队尾指针rear指向新结点。由于加了表头结点，空队列下的操作无须特殊处理。
图5.7链队列的入队操作
入队算法的完整代码如下：
def append(self, item):
new_rear = QueueNode(item)
self._rear.next = new_rear
self._rear = new_rear
接下来看出队操作。如果队列为空，如图5.8(a)所示，则出队操作失败； 如果队列只有一个元素结点，如图5.8(b)所示，注意唯一的元素结点出队后指针rear应指向表头结点； 一般情况下，如图5.8(c)所示，则将front所指表头结点的指针域指向原队首结点的下一结点。
图5.8链队列的出队操作
出队算法的完整代码如下：
def serve(self):
if self.empty():
return None
else:
old_first = self._front.next
self._front.next = old_first.next
item = old_first.entry
if self._rear == old_first:
self._rear = self._front
del old_first
return item
获取队头元素的方法retrieve先判别队列是否为空，若为空时返回None，非空时返回队首结点的值。
def retrieve(self):
if self.empty():
return None
else:
return self._front.next.entry
与链栈一样，除了__len__算法的时间复杂度为O(n)，链队列的其他算法的时间复杂度都为O(1)。
实际上，Python标准库的queue模块中提供了FIFO队列类Queue，它采用双向块链存储结构，具体请参考5.6.3节和5.8节。
5.5队列的应用
5.5.1杨辉三角形的输出
杨辉三角形的特点是两个腰上的数字都为1，其他位置上的数字是其上一行中与之相邻(上部和左上部)的两个整数之和。例如，当n=7时，打印的杨辉三角形如下：
1
11
121
1331
14641
15 101051
16 15201561
根据杨辉三角形的特点，可用第i-1行的元素来生成第i行的元素。例如，第2行1列和第2行2列的元素都是1，则第3行2列的元素是第2行1列的元素与第2行2列的元素之和2。可以设置一个初始全为0的n+1行n+1列的二维列表y，用y［i］［j］表示三角形i行j列的元素，则：
y［i］［j］=1i=1，j=1
y［i-1］［j-1］+y［i-1］［j］i>1，j≥1，i≥j
将y［1］［1］赋值为1，通过以上迭代方法进行逐行计算，输出时只选二维列表中的杨辉三角形部分输出即可。该算法较为简单，读者可自行完成，算法的时间和空间复杂度都为O(n2)。
如果用队列依次存放杨辉三角形第i行的所有（i个）元素，然后逐个出队并打印，同时生成第i+1行的i+1个元素并入队，重复出队、输出和入队操作，即可得到杨辉三角形。
算法步骤描述如下：
(1) 初始化空队列。
(2) 1行1列的元素1预先进入队列。
(3) 外层循环执行n次，依次处理杨辉三角形的第i行(1≤i≤n)：
① 内层循环执行i次，即依次处理i行j列(1≤j≤i)元素： 出队i行j列的元素t，输出t，假设t的前一列元素的值为s(j为1时s为0)，求得i+1行j列的元素s+t并入队，s的值更新为t；
② 当第i行的i个元素全部出队并输出时，已得到i+1行的前i个元素并入队，仅需将i+1行的最后一个元素1入队；
③ 输出第i行的换行符。
具体算法如下：
def yang_hui(n):
line = CircularQueue()#采用循环队列，也可以用链队列
line.append(1)#第1行的一个数入队
for i in range(1, n+1):#输出杨辉三角形的n行
#第i行数据已存放在队列中，在出队并输出第i行的全部元素的同时
#生成第i+1行的全部i+1个元素，并入队
s = 0#s表示i行j-1列元素的值，初始为0
for j in range(1, i + 1):#对于i行j列的元素
t = line.serve()#出队
print("%5d" % t, end="")#输出
line.append(s + t)#生成i+1行j列的元素并入队
s = t#s的值更新为t，用于生成i+1行的下一个元素
line.append(1)#i+1行的最后一个数1入队
print()#换行
这是利用队列先进先出的特性，控制元素按照一定次序动态生成和输出的队列的典型应用，以后在二叉树层次遍历等算法中会多次遇到类似应用。本算法的时间复杂度为O(n2)，空间复杂度为O(n)。
5.5.2一元多项式的计算
1. 一元多项式的逻辑结构
一元多项式由若干个非零项(term)构成，每个非零项由一对系数和指数共同确定，因此一个多项式可以看成若干系数、指数二元组构成的线性表。例如，P(x)=-8x999-2x12+7x3可以表示为线性表((-8, 999), (-2, 12), (7, 3))。注意,为了方便对多项式的处理，通常将多项式的非零项按指数递减或递增顺序排序。因此，多项式是一个有序线性表，表中的每个元素包含系数和指数两部分。
假设对上述用线性表表示的多项式进行加法、乘法等运算。例如，对多项式A和B求和，得到多项式C，即通过A表和B表生成C表。很显然，当每次生成C的一个新项时，都是添加到C表的尾部，而当多项式A或多项式B的某一项被取出运算时，可将这一项从表首位置删除。因此，对相应线性表的操作方式是在头部删除、尾部插入，可以认为多项式线性表是一个队列。
2. 一元多项式的存储结构
在对两个多项式做加、减或乘等运算时，生成的目标多项式的项数事先无法确定，因此选用动态的链式存储结构会更加方便。在此将多项式类定义为链队列类的子类。
图5.9给出了多项式5x17+9x8+3x+7的存储结构示意图。
图5.9多项式的存储结构
3. 非零项Term类的定义
表示多项式非零项的Term类定义如下：
class Term:
def __init__(self, scalar=0.0, exponent=0):
self.coefficient = scalar#非零项的系数
self.degree = exponent#非零项的指数
4. 多项式Polynomial类的定义
1) 类定义及初始化方法
from LinkedQueue import LinkedQueue
class Polynomial(LinkedQueue):
def __init__(self):
super().__init__()
2) 多项式清空方法
def clear(self):
while not self.empty():
self.serve()
3) 求多项式最高次项的指数
exp方法用于求解当前多项式最高次项的指数。例如，对于图5.9表示的多项式，返回17； 对于零多项式，即链表为空时，返回-1。
def exp(self):
if self.empty():
return -1
term = self.retrieve()#多项式按非零项指数递减有序，首项即对应最高次项
return term.degree
4) 多项式的读入
def read(self):
print("请按指数递减序，一行输入一对系数和指数，输入完毕以#结束")
data = input()
while data != "#":
temp = data.split()
t = Term(float(temp［0］), int(temp［1］))
self.append(t)
data = input()
5) 多项式的复制
def copy(self):
r = Polynomial()
q = self._front.next
while q:
t = Term(q.entry.coefficient, q.entry.degree)
r.append(t)
q = q.next
return r
6) 多项式的输出
如下的print_out对链队列进行一次遍历，依次输出每个结点所表示的非零项，根据该项是否为首项、系数的值、系数的正负以及指数的值的不同情况进行不同格式的输出。在输出每个非零项时，变元X和其后非0且非1的指数之间用“^”分隔，例如3.0X^5。
def print_out(self):
print_node = self._front.next
first_term = True
while print_node is not None:
print_term = print_node.entry
#以下if…else语句输出当前项的符号
if first_term:#避免打印首项的"+"号
first_term = False
if print_term.coefficient < 0:
print("-", end="")
else:
if print_term.coefficient < 0:
print("-", end="")
else:
print("+", end="")
#以下5行语句输出当前项系数的绝对值
r = print_term.coefficient
if r < 0:#保证r是系数的绝对值
r = -r
if r != 1:#系数为1，无须输出
print(r, end="")
#以下7行语句输出X^和指数部分，当指数为1或0时特别处理
if print_term.degree > 1:
print("X^", end="")
print(print_term.degree, end="")
if print_term.degree == 1:
print("X", end="")
if r == 1 and print_term.degree == 0:
print("1", end="")
print_node = print_node.next
print()
5. 多项式的加法、减法和乘法运算
为使算法更加清晰，将多项式的加法等算术运算设计成使用Polynomial类的外部函数。
1) 多项式的加法
例如，求多项式first和second的和多项式result（图5.10），可概括为如下步骤。
图5.10多项式的加法示例
当链队列first与second至少有一个非空时，循环执行：
(1) 分别调用first.exp()和second.exp()获得first和second当前最高次项的指数exp1和exp2。
(2) 若exp1=exp2，则分别出队first链队列中的首项p和second链队列中的首项q，如果p项和q项的系数之和非0，则生成合并项添加到result的尾部。
(3) 若exp1>exp2，则出队first链队列中的首项p，生成p的复制项添加到result的尾部。
(4) 若exp1<exp2，则出队second链队列中的首项q，生成q的复制项添加到result的尾部。
以下add函数实现多项式first和second的加法，并返回结果多项式。
def add(first, second):
result = Polynomial()
while not first.empty() or not second.empty():
exp1 = first.exp()
exp2 = second.exp()
if exp1 == exp2:
p = first.serve()
q = second.serve()
if p.coefficient + q.coefficient != 0:
t = Term(p.coefficient + q.coefficient, p.degree)
result.append(t)
elif exp1 > exp2:
p = first.serve()
t = Term(p.coefficient, p.degree)
result.append(t)
else:
q = second.serve()
t = Term(q.coefficient, q.degree)
result.append(t)
return result
2) 多项式的减法
可调用加法操作完成多项式的减法。在调用add函数之前，首先生成一个多项式third，它的各非零项的系数分别为second多项式各非零项系数的相反数。以下subtract函数实现多项式first和second的减法操作，并返回结果多项式。
def subtract(first, second):
third = Polynomial()
while not second.empty():
q = second.serve()
t = Term(-q.coefficient, q.degree)
third.append(t)
return add(first, third)
3) 多项式与单个非零项的乘法
在介绍多项式乘法之前，首先说明多项式与一个非零项的乘法。例如，求多项式current与非零项t相乘的结果result，则依次出队current的每项p，将p和t的系数相乘、指数相加，以得到的新系数和新指数生成一个新项，依次入队到结果多项式result中。代码如下：
def mult_term(current, t):
result = Polynomial()
while not current.empty():
p = current.serve()
result.append(Term(p.coefficient * t.coefficient,
p.degree + t.degree))
return result
4) 多项式的乘法
可调用加法操作和上述mult_term函数完成多项式的乘法。依次出队first多项式中的每项t，将t项与second多项式的备份third相乘的结果temp依次加到结果result中。因为在做mult_term运算时多项式会逐渐出队而变空，所以不能直接用second对象参与mult_term运算。这也反映了采用队列表示多项式的一个缺点，即在做各种运算时可能会破坏当前的多项式，读者可思考多项式的其他表示方法。
def multiply(first, second):
result = Polynomial()
while not first.empty():
t = first.serve()
third = second.copy()
temp = mult_term(third, t)
result = add(result, temp)
return result
5.5.3基于队列的迷宫求解
1. 广度优先搜索迷宫求解策略
在第4章中利用栈进行回溯实现了迷宫求解，采用的是回溯法搜索迷宫的策略，接下来介绍一种基于广度优先搜索策略求解迷宫问题的方法。该方法的基本思想如下：
(1) 假设当前到达下标为(i, j)的可通位置P，如P为出口，则找到并输出路径，否则依次探索P位置的东、南、西、北4个邻居位置，假设为P0、P1、P2、P3，若该邻居位置已为出口，则输出对应路径，算法结束； 若该邻居位置不通或已经走过，则跳过该位置； 若所有Pi位置都不通或已经走过，说明无法从P到达终点，接下来只能通过其他位置继续探索。
（2） 如果P有可通邻居，则依次从P0、P1、P2、P3（假设都可通）位置开始重复步骤（1），即在还没有找到终点并且还有未探索位置的情况下依次探索P0的4个相邻位置P00、P01、P02、P03； P1的4个相邻位置P10、P11、P12、P13； P2的4个相邻位置P20、P21、P22、P23； P3的4个相邻位置P30、P31、P32、P33。如果还没有找到路径并且还有未探索位置，则再按刚才各探索位置Pij的次序探索各可通位置Pij的可通未走过邻居位置，以此类推，直到找到一条路径或者所有可通位置都已探索但仍没有找到路径为止。
如图5.11所示，从位置(i, j)开始迷宫探索，依次探测其东、南、西、北4个相邻位置(A、B、C、D)； 接着从东邻位置A(i, j+1)探测它的相邻位置，由于其西邻居位置已经走过无须探索，所以依次探测其东、南、北3个相邻位置(E、F、G)； 然后从南邻位置B(i+1, j)探测它的相邻位置，由于东、北邻居位置已经走过无须探索，所以依次探测其南、西两个相邻位置(H、I)； 接着从西邻位置C(i, j-1)探测它的未走过的西、北两个相邻位置(J、K)； 最后从北邻位置D(i-1, j)探测它的未走过的北邻位置(L)； 再依次探测这8个位置的未走过的各个相邻位置，在这个过程中遇到出口位置则求解结束。如果所有可通位置全部探测完毕但仍没有遇到出口，则整个迷宫没有可通的路径。在以上描述中，假设各个位置都是可通的，若某位置不可通，则直接跳过该位置。
图5.11从(i, j)位置开始探测迷宫示意图
可以用如图5.12所示的树形结构图表示从(i, j)位置开始的迷宫探索过程。树中的每个方框称为结点，在此表示一个位置，带箭头的线段连接上、下两个结点P和Q，表示从P可以走到其邻居位置Q，在树形结构中，称Q是P的孩子(请参考第9章)。由于每个位置最多有东、南、西、北4个可通的相邻位置，所以在该树中每个结点最多有4个孩子，实际情况是由于部分孩子结点已经走过或不可通，某结点的孩子结点经常少于4个。从第0层的根结点开始探测，然后依次是第1层从左到右的4个位置，接着是第2层从左到右的各个未探测位置； 以此类推，即按照从上到下、从左到右的次序对可通且未走过的位置进行探索，当遇到出口或已没有可通位置时求解结束。图中各结点旁标注的编号即是探测的次序。若第2层的8个有效结点都已探测但还没找到出口，则继续探测第2层结点的各个未探测可通邻居位置，图中由于篇幅关系，后续层次没有画出。
图5.12从(i, j)位置开始探测迷宫示意图
2. 算法步骤
类似于杨辉三角形打印，可以利用队列先进先出的特性得到这个从上到下、从左到右的次序。
为了得到第i+1层的每个位置的坐标，可以在队列中依次存放第i层的所有可通位置的坐标； 然后逐个出队各位置pos，同时得到pos位置的各个未走过可通相邻位置并入队，当i层位置全部出队时，第i+1层的位置则全部入队。重复出队和入队操作，直到遇到出口或队列为空。若遇到出口，则输出迷宫路径。另外，采用一个字典precedent记录每个可通位置的前驱位置，以方便最后输出路径。算法步骤可描述为：
(1) 若入口位置不通，找不到路径，输出相应信息，返回。
(2) 若入口位置即为出口位置，输出相应信息，返回。
(3) 初始化字典precedent； 小乌龟移动到入口位置，对该位置做已走过标记(黑色小圆点)； 将入口位置放入初始为空的队列q中。
(4) 当队列q非空时循环(外层)执行：
① 出队当前位置pos；
② 小乌龟移动到该位置(其运动轨迹不显示)；
③ 循环(内层)检查pos的4个相邻位置nextPos，如果nextPos可通且未走过，则：
小乌龟从pos移动到nextPos，同时显示出其运动轨迹，并对nextPos位置做已走过标记(黑色圆点)；
若nextPos为出口，则调用buildPath方法显示出路径,算法结束；
否则，将nextPos位置入队，同时在precedent字典中设置nextPos的前驱为pos，并且为了能在可视化界面中看清小乌龟将从pos走向下一个位置，此时将小乌龟再次定位到pos位置。
(5) 若队列为空，则没有找到路径。
3. 算法实现
根据上述分析，设计Maze类的基于队列的迷宫求解方法findRouteByQueue。算法如下：
def findRouteByQueue(self):
pos = self.startPosition
if self［pos［0］］［pos［1］］ == OBSTACLE:
print("入口不通")
return
if self.isExit(pos):#起点即为终点
print("入口即出口")
return ［pos］
q = CircularQueue()#建立辅助队列q
precedent = dict()#创建各位置的前驱字典precedent
#小乌龟移动到pos位置，做黑色小圆点标记
self.updatePosition(pos［0］, pos［1］, TRIED)
q.append(pos)#将起点入队
while not q.empty():#队列非空时
pos = q.serve()#出队一个位置
self.gotoStart(pos［0］, pos［1］)#小乌龟移动到pos位置，不显示轨迹
for i in range(4):#依次试探它的4个邻居nextPos
nextPos = (pos［0］ + DIRECTIONS［i］［0］,
pos［1］ + DIRECTIONS［i］［1］)
if self.isPassable(nextPos):#如果该邻居可通
#小乌龟移动到nextPos位置，做黑色小圆点标记
self.updatePosition(nextPos［0］, nextPos［1］, TRIED)
if self.isExit(nextPos):#若已经到达出口
precedent［nextPos］ = pos#出口位置的前驱位置为pos
return self.buildPath(precedent)#完成路径输出，返回
q.append(nextPos)#该邻居位置入队
precedent［nextPos］ = pos#该邻居的前驱位置设为pos
self.gotoStart(pos［0］, pos［1］)#小乌龟回到pos，不显示轨迹
print("没有找到通过迷宫的路径")
4. Maze类的其他方法
在上述迷宫求解算法中，遇到出口时调用buildPath方法，该方法动态显示并返回迷宫路径。具体算法如下：
def buildPath(self, precedent):
"""根据precedent中的位置前驱信息，产生起点到终点的路径存储到列表path中，
同时将路径上的各个位置做灰色大圆点标记"""
start = self.startPosition
end = self.endPosition
path = ［end］
pos = end
while pos != start:
#对路径上的各位置做灰色大圆点标记
self.updatePosition(pos［0］, pos［1］, PATH_PART)
path.append(pos)
pos = precedent［pos］
path.append(start) #此时得到的是end到start的路径
self.updatePosition(start［0］, start［1］, PATH_PART)#起点位置做灰色大圆点标记
self.wn.exitonclick()
path.reverse()#列表逆置
return path
Maze类的数据成员和其他方法与4.5.4节相同。对图4.9所示的迷宫，采用广度优先搜索路径的算法，从起点(1, 4)到终点(10, 10)的路径搜索过程如图5.13所示。其中，灰色大圆点连接的路径为迷宫路径。
视频讲解
图5.13用队列实现迷宫求解的结果截图
5.6双端队列
5.6.1双端队列的基本概念
5.1节中介绍的队列只允许在表的一端进行删除，在另一端进行插入。接下来介绍一个类队列结构，它支持在线性表的两端进行插入和删除，这就是双端队列(doubleended queue 或者deque，其发音为deck)。图5.14为双端队列示意图，可以认为双端队列是栈和队列的泛化，栈和队列是双端队列的特例。
图5.14双端队列示意图
T类型元素构成的双端队列是由T类型元素构成的有限序列，并且具有以下基本操作：
(1) 构造一个空双端队列(__init__)。
(2) 判断一个双端队列是否为空(empty)。
(3) 求双端队列的长度(__len__)。
(4) 在双端队列的尾部入队一个元素(append)。
(5) 在双端队列的头部入队一个元素(appendleft)。
(6) 在双端队列的尾部出队一个元素(pop)。
(7) 在双端队列的头部出队一个元素(popleft)。
(8) 读取双端队列的头部元素(getleft)。
(9) 读取双端队列的尾部元素(getright)。
双端队列可以用顺序存储或链式存储方式进行存储，读者可以自行尝试用Python的list或链表等多种方式实现双端队列。
5.6.2Python的双端队列类
在Python的标准模块collections中提供了一个双端队列类deque，在Python内部实现时采用双向块链表结构，即在双向链表中每个结点的数据域中存放多个元素，此时结点被称为块(block)。Python双端队列的块结构如
图5.15Python双端队列的块结构
图5.15所示，data是一个长度为64的数组，可存放64个元素(64个Python对象的指针)，leftlink指针指向前驱块，rightlink指针指向后继块。
如图5.16所示为一个含有多个块的非空deque对象，它是一个双向非循环链表，主要包含leftblock、rightblock、leftindex和rightindex等数据成员。其中，在leftblock指针指示的块中，data［leftindex］位置的元素对应于图5.14中的a0； 在rightblock指针指示的块中，data［rightindex］位置的元素对应于图5.14中的an-1。
图5.16含有多个块的非空双端队列示意图
当生成一个初始空双端队列时即生成一个块，leftblock和rightblock指针都指向该块，并且初始leftindex和rightindex为data数组的中间相邻位置，如图5.17所示。此时，如果在双端队列尾部入队(append)，则rightindex增1，将元素放在data［rightindex］位置； 如果在双端队列头部入队(appendleft)，则leftindex减1后将元素放在该位置。当该块的64个空间用完后，若需要尾部入队(append)，则再生成新块插入在rightblock的右边并调整rightblock； 若需要头部入队(appendleft)，则再生成新块插入在leftblock的左边并调整leftblock。
图5.17初始空双端队列示意图
总之，deque对象的数据存储在长度固定的块构成的双链表中，并具有以下优点：
(1) 从基本操作的时间性能来看，双向块链表结构可以确保不管做哪个方向的append或pop操作，除了被操作的数据元素之外，任何其他元素都不会被移动，因此append、appendleft、pop和popleft算法的时间复杂度为O(1)。
(2) 与顺序存储实现相比，链表结构可以完全避免顺序结构在初始分配空间用完时需重新分配更大空间并进行元素复制(类似于resize方法的功能)的问题，从而提高了性能的可预测性。
(3) 与第3.4.3节中介绍的双向链表的实现相比，原双向链表的每个结点中存储一个数据元素和两个指针，存储密度为1/3，并且每次元素的插入或删除都对应于一次结点的动态分配或回收(对应于底层实现时C语言的malloc()和free()函数)。而使用固定长度的块，元素的存储密度得到提高，同时避免了频繁调用malloc()和free()函数，提高了时间效率。
虽然list对象也支持两端的插入和删除操作，但由于采用顺序存储方案，其pop(0)和insert(0, v)操作会产生O(n)内存移动成本，且会改变其他数据的位置。因此，在使用Python语言编写程序时，若需在表的两端做插入或删除，应优先选择deque而不是list。Python的deque对象支持的主要方法如表5.2所示。
表5.2Python deque对象支持的主要方法
方法说明
__len__()返回元素个数
clear()删除deque中的所有元素，让它的长度为0
append(x)在deque的右边插入x
appendleft(x)在deque的左边插入x
pop()从deque的右侧删除并返回一个元素，如果不存在元素，则引发一个IndexError
popleft()从deque的左侧删除并返回一个元素，如果不存在元素，则引发一个IndexError
［j］索引访问，在两端都是O(1)，但在中间减慢到O(n)，对于快速随机访问，请使用列表代替
5.6.3双端队列的应用
基于上述双端队列类deque，可以实现4.2节介绍的栈的抽象数据类型和5.2节介绍的队列的抽象数据类型。
以下用Python的双端队列deque实现普通队列类，入队算法调用deque的append方法，出队算法则调用deque的popleft方法，类定义和各方法的具体实现如下：
from collections import deque
class Queue:
def __init__(self):
self._entry = deque()
def empty(self):
return len(self._entry) == 0
def __len__(self):
return len(self._entry)
def append(self, value):
return self._entry.append(value)
def serve(self):
if not self.empty():
return self._entry.popleft()
else:
retwn None
def retrieve(self):
if not self.empty():
return self._entry［0］
else:
retwn None
def clear(self):
return self._entry.clear()
如5.4节中所述，Python标准库queue模块中的Queue类即采用双端队列实现。
5.7优先级队列
5.1节讨论的队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要每次从队列中取出具有最高优先级的元素，这种队列就是优先级队列(priority queue)，也称为优先权队列或优先队列。
优先级队列是0个或多个元素的集合，每个元素都有一个与之关联的优先级。对于优先级队列,主要的操作有：
(1) 查找优先级最高的值。
(2) 出队优先级最高的值。
(3) 入队一个任意优先级的值。
假设数值越小，表明该元素的优先级越高，则在如图5.18所示的优先级队列中，最先出队的是元素10，入队新元素则可以直接放在30之后。
假设用无序表表示优先级队列，入队操作的时间复杂度可以为O(1)，但查找和出队操作都为O(n)。如果用有序表表示优先级队列，查找和出队操作的效率可以为O(1)，但入队操作的时间复杂度为O(n)。在第8章中将会介绍用“堆”实现优先级队列，此时入队和出队操作的时间效率都为O(log2n)。
图5.18优先级队列示例
5.8Python提供的多种队列
在Python标准库的queue模块中提供了FIFO队列类Queue、LIFO队列类LifoQueue、优先级队列类PriorityQueue； 另外，标准库collections模块中提供了双端队列类deque。当然Python标准库中各个类的功能比我们所定义的抽象数据类型中的功能更强大，比如队列模块实现多生产者、多消费者队列，该模块中的Queue类可以在多个线程之间安全地交换信息，在多线程编程中特别有用。
从数据结构的逻辑结构和存储结构对这4个类进行分析，可以得出表5.3所列的对应关系。其中，LIFO队列类LifoQueue对象的操作方法与栈相同。
表5.3Python中的各队列及对应数据结构
类引 入 语 句逻 辑 结 构存 储 结 构
LifoQueuefrom queue import LifoQueue栈顺序表，用list实现
Queuefrom queue import Queue队列双向块链结构，用deque实现
PriorityQueuefrom queue import PriorityQueue优先级
队列二叉堆，用heapq实现，详见8.5节
dequefrom collections import deque双端队列双向块链结构
5.9上机实验
5.9.1循环队列的实现
实现一个循环队列类，并设计测试程序，验证所设计的队列类是否正确。具体要求：
(1) 实现入队、出队、读取队首、求队列元素个数、清空队列、显示队列内容等功能。
(2) 给出友好用户界面，每次执行可以循环接受多次命令，直至用户按“Q”或“q”退出程序。
5.9.2链队列的实现
用双向循环链表实现队列，设计并实现该链队列类，具体要求与5.9.1节相同。
5.9.3猜猜我的QQ号
根据设定的规则，由给定的一串数字得出一个QQ号。规则如下：
首先将第1个数删除，接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数放到这串数的末尾，再将第5个数删除，以此类推，直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，将这些删除的数连在一起就是我的QQ号。
例如，给出的数字串是631758924，则我的QQ号是615947283。
5.9.4字符串的匹配
编写程序，从终端读取一行字符，然后按其特征输出对应的标记符号。假设输入由两部分组成，之间用西文冒号“:”分开。标记符号及其对应特征如下。
(1) N： 行中没有冒号。
(2) L： 左边部分(冒号前)比右边部分长。
(3) R： 右边部分(冒号后)比左边部分长。
(4) D： 左边部分和右边部分不同但有同样的长度。
(5) S： 左边部分和右边部分完全相同。
提示： 在读取右边部分时，可使用队列跟踪行的左边部分。
要求： 采用循环队列进行存储，读取一行输入，然后产生判断结果。
5.9.5制作糖果
假设某糖果公司正在制作世界上最大的糖果。制作糖果的原料用货车运送到山顶，最后倒入日内瓦湖中。制作糖果的原料含有编号1至n共n种成分，编号为i的糖果原料已放在i号车，离湖最近的车可以直接开到湖边将原料倒入湖中，或者开到分支后再从分支开出将原料倒入湖中。成功制作糖果要求必须按照1, 2, 3, …, n的编号顺序将各原料倒入湖中，但现在山顶货车的排列顺序是随机的。编写程序，判别山顶的任意车厢序列是否可以成功制作出糖果？
如图5.19所示，n=4，即糖果共有4种成分，4辆原料车已按照4132的顺序停在山顶。为了在湖中得到1234的原料次序，首先将4号车开到分支，1号车原料直接倒入湖中，3号车进入分支，2号车的原料倒入湖中，然后3号车从分支倒入湖中，接着4号车从分支倒入湖中，即可得到1234这样的顺序，成功制作出糖果。
图5.19制作糖果示意图
如果一开始山顶上这4辆车是反过来的次序，即从下到上2314的次序，则不能成功。因为首先需要的是1号车，这样排在最前面的2号车和3号车都只能依次进入分支，然后1号车原料倒入湖中，接下来需要的2号车无法从分支出来。
提示： 山顶可以看成是队列，分支则是一个栈。
测试数据：
输入序列4132，结论为成功；
输入序列2314，结论为失败；
输入序列1234，结论为成功；
输入序列134256，结论为失败。
5.9.6纸牌游戏
A和B两个同学玩小猫钓鱼纸牌游戏，每人手里有n张牌，两人轮流出牌并依次排列在桌面上，每次出掉手里的第1张牌，出牌后如果发现桌面上有跟刚才打出的牌的数字相同的牌，则把到相同的那张牌结束的全部牌按次序放在自己手里牌的末尾。当一人手中的牌先出完时，游戏结束，对方获胜。
如n为4，A手里的牌依次为2356，B手里的牌依次为1542。
A出2，B出1； 此时桌子上从前往后依次为21，A手里是356，B手里是542。
A出3，B出5； 此时桌子上从前往后依次为2135，A手里是56，B手里是42。
接着A出5，发现前面有一张5，则把两个5都拿掉，这时他手里有655； 桌子上的牌依次为213； 接着B出4，桌子上的牌是2134，他手里的牌是2。
接着A出6，A手里剩55，B出2，发现前面有2，全部收到自己手里，他手里的牌即是264312，桌子上没有牌； 以此类推，直到某人先出完牌为止，则对方是胜者。
编写程序，模拟显示出桌子上和A、B两位同学手里的牌的变化过程，并判断谁是胜者以及此时胜者手里的牌的状态。如上例中，每次A和B各出一张牌后，桌子上和手里的牌的变化状态如下：
The cards on the desk:2 1
The cards in a's hand:3 5 6
The cards in b's hand:5 4 2
************************
The cards on the desk:2 1 3 5
The cards in a's hand:5 6
The cards in b's hand:4 2
************************
The cards on the desk:2 1 3 4
The cards in a's hand:6 5 5
The cards in b's hand:2
************************
The cards on the desk:
The cards in a's hand:5 5
The cards in b's hand:2 6 4 3 1 2
************************
The cards on the desk:5 2
The cards in a's hand:5
The cards in b's hand:6 4 3 1 2
************************
The cards on the desk:6
The cards in a's hand:5 2 5
The cards in b's hand:4 3 1 2
************************
The cards on the desk:6 5 4
The cards in a's hand:2 5
The cards in b's hand:3 1 2
************************
The cards on the desk:6 5 4 2 3
The cards in a's hand:5
The cards in b's hand:1 2
************************
The cards on the desk:6 1
The cards in a's hand:5 3 2 4 5
The cards in b's hand:2
************************
The cards on the desk:6 1 5 2
The cards in a's hand:3 2 4 5
The cards in b's hand:
************************
胜者为A，A剩下的牌从上到下依次为3245。
本章习题
一、 选择题
1. 已知循环队列存储在初始容量为n的列表entry中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，现要求最先进入队列的元素存储在entry［0］处，则初始时front和rear的值分别是。
A. 0,0B. 0, n-1C. n-1, 0D. n-1, n-1
2. 以下概念不涉及具体存储结构的是。
A. 循环队列B. 链表C. 顺序栈D. 双端队列
3. 以下现实生活中的例子不符合队列特性的是。
A. 在杂货店结账的顾客B. 洗车店一字排开的汽车
C. 一摞硬币D. 若干个人过独木桥从河东到河西
4. 在解决计算机主机与打印机之间的速度不匹配问题时通常设置一个打印缓冲区，该缓冲区的逻辑结构是。
A. 栈B. 队列
C. 数组D. 普通线性表
5. 循环队列。
A. 不会产生上溢出B. 不会产生下溢出
C. 不会产生假溢出D. 以上都不对
6. 以下最不适合用于存储队列的结构是。
A. 只带队首指针的双向非循环链表B. 只带队首指针的双向循环链表
C. 只带队尾指针的双向循环链表D. 只带队尾指针的单向循环链表
7. 下列叙述中正确的是。
A. 队列可以用链式存储结构的单链表实现
B. 有两个指针域的链表称为二叉链表
C. 链队列设队首指针和队尾指针，是一个双重链表
D. 结点中具有多个指针域的链表称为多重链表
8. 在用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时。
A. 队头、队尾指针都可能要修改
B. 仅修改队头指针
C. 仅修改队尾指针
D. 队头、队尾指针都必须要修改
9. 若用长度为6的列表存储循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A. 3和4B. 3和0 C. 5和0D. 5和1
10. (多选)设一个队列的入队顺序是1, 2, 3, 4, 5，下列不可能是出队序列的有。
A. 1, 2, 3, 5, 4B. 3, 4, 5, 1, 2
C. 5, 4, 3, 2, 1D. 1, 2, 3, 4, 5
11. (多选)设某个队列允许在两端入队，但仅允许在一端出队，若入队顺序是1, 2, 3, 4, 5，下列可能是出队序列的有。
A. 2, 1, 3, 4, 5B. 4, 2, 1, 3, 5
C. 5, 3, 2, 1, 4D. 4, 2, 3, 1, 5
12. (多选)队列的先进先出特性是指。
A. 最后插入队列中的元素总是最后被删除
B. 当同时进行插入、删除操作时，总是插入操作优先
C. 每当有删除操作时，总是先做一次插入操作
D. 每次从队列中删除的总是最早插入的元素
二、 判断题
()1. 栈和队列都是特殊的线性表，共同点是只允许在表尾端进行插入和删除。
()2. 队列中元素的入队次序和出队次序一致。
()3. 不管使用何种存储方案，队列入队和出队操作的时间效率都为O(1)。
()4. 对于链队列，可以根据队首、队尾指针计算出队列中元素的个数。
()5. 双端队列是栈和队列功能的扩展，可以用双端队列来实现栈或队列。
()6. 借助栈和队列求解出的迷宫路径一定是相同的。
()7. 如需经常对线性表的两端做插入和删除操作，从时间效率考虑，在Python语言中应优先选择deque而不是list。
()8. 读取Python双端队列中任意位置元素的性能都是O(1)。
三、 填空题
1. 队列是一种具有特性的线性表，在出队算法中需要判断。
2. 在采用顺序存储结构实现队列时，通常将数组看成是首尾相连的空间，这样做是为了避免产生的现象。
3. 设在循环队列中用front和rear分别指示队头元素和队尾元素的位置，若当前队列空间的容量为n，则队列中元素的个数为； 若用损失一个空间的方法来区分队空和队满，则当时表示队满。
4. 现采用长度为10的列表实现一个循环队列。设在某一时刻，队列为空且此时front和rear分别为5和4，后经过若干操作后，front为8，rear为2，此时队列中有个元素。
5. 假设队列用不带头结点的单链表实现，且仅设指向链表首结点的队首指针，则出队算法的时间复杂度为,入队算法的时间复杂度为。
四、 应用题
1. 分析以下函数的功能，其中参数q为队列。
def algo1(q):
s = ArrayStack()
while not q.empty():
x = q.serve()
s.push(x)
while not s.empty():
x = s.get_top()
s.pop()
q.append(x)
2. 假设调用下列函数，请给出其输出结果。
def algo2():
x = 'e'
y = 'c'
q = CircularQueue()
q.append('h')
q.append('r')
q.append(y)
x = q.serve()
q.append(x)
x = q.serve()
q.append('a')
while not q.empty():
y = q.serve()
print(y, end="")
3. 假设某公司于20××年1月、4月、9月分别购进A材料100吨，并在当年6月、11月分别卖出100吨。这5个月的材料成交价格见表5.4。
表5.4A材料价格表
时间1月4月6月9月11月
单价$10$30$20$50$30
请计算如果采用以下策略，一年总共盈利或亏损多少？假设这一年公司剩余的100吨材料不计算在内。
(1) 采用先进先出的策略进行买卖，即6月卖出的材料是1月买入的。
(2) 采用后进先出的策略进行买卖，即6月卖出的材料是4月买入的。
4. 在用循环队列实现时，可以用哪些方法来区分队空和队满，对应队空和队满的条件分别是什么？简述之。
五、 算法题
1. 使用栈或队列的方法完成下列操作：
(1) 将队列中的所有元素移动到栈中。
(2) 将栈中的所有元素逆置。
2. 采用线性数组实现队列，并利用front和rear下标分别指示队头和队尾位置，当rear下标到达数组尾部时，将队列中所有的元素平移到数组的最前端。设计此队列类，并实现主要算法。
3. 采用循环数组实现队列，使用front和rear下标分别指示队头和队尾位置，增加一个标记变量flag来表明当前队列是否为满，重新设计并实现循环队列类。
4. 使用已学的各种数据结构及基本操作设计算法reverseOdd，对参数所给定的队列中的整数进行操作，将队列中奇数的顺序进行逆置，偶数的顺序维持不变。例如，给定队列从队头至队尾的元素为14, 13, 17, 8, 4, 10, 11, 4, 15, 18, 19，调用该函数后，队列内容变为(14, 19, 15, 8, 4, 10, 11, 4, 17, 18, 13)。
5. 修改链式队列类，用单向循环链表表示队列，并只设尾指针。设计出队算法(serve)和队列清空算法(clear)。
6. 调用栈或队列类的方法，设计算法删除队列中最后一个值为item的元素，即离队首最远的值为item的元素。
7. 设计算法，判断一个字符串是否为回文词。回文词是指正读和反读都一样的词。
8. 某汽车轮渡口，过江渡船每次能载10辆车过江，过江车辆分为客车类和货车类。上渡船有如下规定： 同类车先到先上船； 客车先于货车上船，且每上4辆客车才允许上1辆货车； 若等待客车不足4辆，则以货车代替； 若无货车等待，则允许客车都上船。设计一个算法模拟渡口管理。