T7-栈与队列(队列)

队列第三章：栈与队列

主讲：周翔什么是队列排队排队买票时，排在前面的人先买到票离开排队的队伍，然后轮到后面的人买；如果又有人来买票，就依次排到队尾。买票的过程中，队伍中的人从头到尾依次出列。什么是队列队列（Queue）像排队这样，先来的先离开，后来的排在队尾后离开，在数据结构中，也有一种数据结构遵循这一原则，那就是队列队列是只允许在一端删除，在另一端插入的线性表。允许删除的一端称为队头，允许插入的一端称为队尾。向队列中插入元素称为入队，从队列中删除元素称为出队。什么是队列队列（Queue）定义：只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表逻辑结构：与线性表相同，仍为一对一关系存储结构：用顺序队列或链队存储均可运算规则：先进先出（FIFO）实现方式：关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同队列的抽象数据类型ADTQueue

{

数据元素：可以是任意类型的数据，但必须属于同一个数据对象

数据关系：队列中数据元素之间是线性关系

基本操作： InitQueue(&Q);//设置一个空队 EnterQueue(&Q,x);//进队

DeleteQueue(&Q,&x);//出队

GetHead(Q,&x);//取队头元素 ……}队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行队列的表示和实现顺序队列循环队列链式队列队列的表示和实现——顺序队列使用顺序表实现的队列称作顺序队列。顺序队列的实现和顺序表的实现相似，只是在顺序队列中只允许在一端进行插入，在另一端进行删除。定义两个变量front与rear分别标识队头与队尾，当删除队头元素时，front后移到下一个位置；当插入新元素时，在rear指示的位置插入，插入后，rear向后移动指向下一个存储位置。队列的表示和实现——顺序队列顺序队列元素入队：队列的表示和实现——顺序队列顺序队列元素出队：队列的表示和实现——顺序队列队列的表示和实现——循环队列队列也可像顺序栈那样，采用顺序存储结构，但若按如下设计队列的存储，会发生什么情况呢？01234

elementfrontrear空队，front=rear=0队列的表示和实现——循环队列依次将元素｛a,b,c,d,e｝进队此时队满，rear=MAX_SIZE。那么能用rear=MAX_SIZE来判断队满吗？01234

elementfrontrearabcde队列的表示和实现——循环队列出队两个元素此时队不满，但仍有rear=MAX_SIZE这种现象叫做“假溢出”真正队满的条件是：rear-front=MAX_SIZE01234

elementfrontrearabcde队列的表示和实现——循环队列队列的“溢出”有两种情况，一种为真“溢出”，一种为假“溢出”真“溢出”是指当前队列分配的空间已满，此时再往里存储元素则会出现“溢出”，这种“溢出”是真的再无空间来存储元素，是真“溢出”假“溢出”是指队列尚有空间而出现的“溢出”情况。当front端有元素出队时，front向后移动；当rear端有元素入队时，rear向后移动，若rear已指到队列中下标最大的位置，此时虽然front前面有空间，但再有元素入队也会出现“溢出”，这种“溢出”叫作“假溢出”队列的表示和实现——循环队列如何解决数组前面出现空单元的现象？每出队一个元素，就将数组中其他所有元素都向前移动一个位置。如果这样操作，那么当队列中有n个元素时，该操作需要O(n)时间。更好的解决方案？循环队列队列的表示和实现——循环队列循环队列队列的表示和实现——循环队列队列存放数组被当作首尾相接的表处理。element[0]接在element[MAXSIZE-1]的后面。将队列中元素从队首到队尾按顺时针方向存放在循环数组的一段连续的单元中。如图所示，当元素存至element[7]后，只需通过(7+1)%8运算，即可得到element[0]单元。01234567a(1)a(2)a(3)队列的表示和实现——循环队列如何指示队首与队尾位置？如何表示空队列？如何表示满队列？队列的表示和实现——循环队列front：始终指示队头元素的位置rear：始终指示队尾元素的后面位置如图中，队列{a(1),a(2),a(3)}，front=1，rear=4frontrear01234567a(1)a(2)a(3)队列的表示和实现——循环队列在图中依次将元素作出队操作，则最终front与rear的位置怎样？frontrear01234567a(1)a(2)a(3)frontfrontfront此时有front=rear队列的表示和实现——循环队列在图中依次将元素{a(4),a(5),a(6),a(7),a(8)}进队，最终front与rear的位置怎样？frontrear01234567a(1)a(2)a(3)a(4)a(5)a(6)a(7)a(8)rear此时仍有front=rear因此无法仅靠front=rear判断队列“满”与“空”的状态队列的表示和实现——循环队列区分满队列和空队列的方法方法1：另设一个布尔量来注明队列是空还是满。方法2：约定当循环数组中元素个数达到MAXSIZE-1时队列为满。采用第2种处理方法队列的表示和实现——循环队列front指示队头元素所在；rear指示队尾元素所在单元的下一个位置；队头取下一个位置：(front+1)%MAXSIZE队尾取下一个位置：(rear+1)%MAXSIZE队空：front==rear队满：元素个数达到MAXSIZE-1(rear+1)%MAXSIZE==front01234567a(1)a(3)a(2)a(7)a(5)a(4)a(6)rearfront队列的表示和实现——循环队列按以上约定，完成以下进队、出队的操作队列的表示和实现——循环队列B,C进队01234567frontrearfrontrear01234567BC空队列A进队A退队B退队D,E,F,G,H,I进队frontrear01234567CBfront01234567Crearfrontrear01234567DEFGHIfrontrear50123467AAC队列的表示和实现——链式队列用链表来实现的队列也称为链式队列，在链式队列中也用指针front与rear分别指示队头与队尾，在队头front处删除元素，在队尾rear处插入元素。与顺序队列不同，链式队列的rear指针指向最后一个元素。队列的表示和实现——链式队列用指针实现队列采用带头结点的链表结构front：队头指针rear：队尾指针队头在链头，队尾在链尾。fronta1a2an0rear队列的表示和实现——链式队列空队列的表示

0frontrear队列的表示和实现——优先队列所谓优先队列，就是根据元素的优先级以及在队列中的当前位置决定元素出队的顺序。优先队列是0个或多个元素的集合，每个元素都有一个优先权值，元素的优先权越高，则会越早出队（被操作）。队列应用杨辉三角形（Pascal’striangle）特点：每一行的第一个元素与最后一个元素均为1其他位置上的数字是其上一行中与之相邻的两个整数之和队列应用杨辉三角形(Pascal’striangle)观察：队列中元素为n=3行元素，则在输出n=3行的元素的同时，将n=4行的元素存入队列中n=1n=2n=3n=4n=5n=61

21队列应用算法步骤：步骤1：将4行第1个数字进队步骤2：输出3行数字，同时产生4行中间的2个数字1：打印3行数字，即队头数字出队2：“打印的数字+队头数字＝4行中间元素”，得到的数字进队3：(1)(2)步骤循环，循环次数为“行数-2”次，即2次步骤3：打印3行最后一个数字，即队头数字出队步骤4：将4行最后一个数字进队n=1n=2n=3n=4n=5n=61

211331队列应用杨辉三角形(Pascal’striangle)观察：队列中元素为n=4行元素，则在输出n=4行的元素的同时，将n=5行的元素存入队列中n=1n=2n=3n=4n=5n=61331队列应用算法步骤：步骤1：将5行第1个数字进队步骤2：输出4行数字，同时产生5行中间的3个数字1：打印4行数字，即队头数字出队2：“打印的数字+队头数字＝5行中间元素”，得到的数字进队3：(1)(2)步骤循环，循环次数为“行数-2”次，即3次步骤3：打印4行最后一个数字，即队头数字出队步骤4：将5行最后一个数字进队n=1n=2n=3n=4n=5n=6133114641队列应用算法步骤总结：步骤1：将n行第1个数字进队步骤2：输出n-1行数字，同时产生n行中间的n-2个数字1：打印n-1行数字，即队头数字出队2：“打印的数字+队头数字＝n行中间元素”，得到的数字进队3：(1)(2)步骤循环，循环次数为“行数-2”次，即n-2次步骤3：打印n-1行最后一个数字，即队头数字出队步骤4：将n行最后一个数字进队