第五讲　队列

教材与参考资料 第4章 栈与队列（4.4,4.5,4.6） 普通高等教育:“十一五”国家级规划教材 普通高等教育精品教材 　普通高等教育精品教材 《算法与数据结构— C语言描述》（第2版） 张乃孝 编著, 高等教育出版社 2008. 第4章 栈与队列（4.4,4.5,4.6） 普通高等教育:“十一五”国家级规划教材配套参考书 《算法与数据结构》（第2版）学习指导与习题解析 　张乃孝 编著, 高等教育出版社 2009. 2

4.4 队列及其抽象数据类型 4.4.1 基本概念 队列是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。 允许进行删除的这一端叫队列的头，允许进行插入的这一 端叫队列的尾。 当队列中没有任何元素时，称为空队列。 队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。

基本概念(续) 队列也称作先进先出表(First In First Out表，简称FIFO表）

4.4.2 抽象数据类型 ADT Queue is operations Queue createEmptyQueue (void ) 创建一个空队列。 int isEmptyQueue ( Queue qu ) 判队列qu是否为空队列。 void enQueue ( Queue qu, DataType x ) 往队列qu尾部插入一个值为x的元素。 void deQueue ( Queue qu ) 从队列qu头部删除一个元素。 DataType frontQueue ( Queue qu ) 求队列qu头部元素的值。 end ADT Queue

4.5 队列的实现 队列实现时通常采用: 顺序表示 链接表示。

4.5.1 顺序表示 存储结构 struct SeqQueue{ /* 顺序队列类型定义 */ int MAXNUM; /* 队列中最大元素个数 */ int f,r; DataType *q; }; /*为了算法设计上的方便：f 指出实际队头元素所在的位置，r 指出实际队尾元素所在位置的下一个位置。*/ typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */

存储结构 假设paqu是PSeqQueue类型的变量， paqu->f存放即将要被删除的元素的下标， paqu->r存放即将要被插入的元素的下标。 paqu->q[paqu->f]表示当前队列头部的元素； paqu->q[paqu->r]表示当前队列尾部的（即将要插入的）元素。 初始时paqu->f = paqu->r = 0。 当前队列中元素的个数=paqu->r - paqu->f 当paqu->r = paqu->f时，元素的个数为0，即为空队列。

举例 张乃孝精讲：“数据结构”第五讲 队列

溢 出 与顺序表类示，在队列中，同样由于数组是静态结构，而队列是动态结构，也可能出现队列溢出问题. 当队列满时，再作进队操作，这种现象称为上溢； 当队空时，作删除操作，这种现象称为下溢。

假溢出 由于队列中经常要执行插入和删除运算，而每运行一次插入或删除，paqu->r或paqu->f就增加1，使得队列中的元素被删除后，其空间就永远使用不到了。 当paqu->r = MAXNUM时，再作插入运算就会产生溢出，而实际上这时队列的前端可能还有许多空的（可用的）位置，因此，这种现象称为假溢出。

环形队列 解决假溢出通常采用的方法是： 把数组paqu->q[MAXNUM]从逻辑上看成一个环，这种队列也称为环形队列。 当表中已有MAXNUM －1个结点时，如果还要插入，paqu->r和paqu->f就会重合，而这与空队列的情形相混。 为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM－1个结点时就称满，再要插入就发生溢出.

环形队列 (a) (b) 图4.11 环形队列paqu

队列基本运算的实现 1. 创建一个空队列。 PSeqQueue createEmptyQueue_seq( int m ) 具体实现与算法2.1类似，需要为队列申请空间，不同之处是需要将对变量f和r均赋值为0。 请读者自己给出。

2. 判断是否为空队列 int isEmptyQueue_seq( PSeqQueue paqu ) 判断paqu所指的队列是否为空队列。   2. 判断是否为空队列 int isEmptyQueue_seq( PSeqQueue paqu ) 判断paqu所指的队列是否为空队列。 当paqu->f == paqu->r时，返回1，否则返回0。

3. 进队运算 void enQueue_seq( PSeqQueue paqu, DataType x ) {   3. 进队运算 void enQueue_seq( PSeqQueue paqu, DataType x ) { /* 在队尾插入元素x */ if( (paqu->r + 1) % MAXNUM == paqu->f ) printf( "Full queue.\n" ); else { paqu->q[paqu->r] = x; paqu->r = (paqu->r + 1) % MAXNUM; }

4. 出队列运算 void deQueue_seq( PSeqQueue paqu ) { /* 删除队列头部元素 */ if( paqu->f == paqu->r ) printf( "Empty Queue.\n" ); else paqu->f = (paqu->f + 1) % MAXNUM; }

5. 取队列头部元素 DataType frontQueue_seq( PSeqQueue paqu ) { 5. 取队列头部元素  DataType frontQueue_seq( PSeqQueue paqu ) { if( paqu->f == paqu->r ) printf( "Empty Queue.\n" ); else return (paqu->q[paqu->f]); }

4.5.2 链接表示 存储结构 队列的链接表示就是用一个单链表来表示队列，队列中的每个元素对应链表中的一个结点，结点的结构与单链表中结点的结构一样。 为了强调队头和队尾都是队列的属性，这里对队列增加了一层封装，引入LinkQueue结构的定义。这样存储的队列简称链接队列。

存储结构 struct Node; typedef struct Node *PNode; struct Node { /* 结点结构 */ DataType info; PNode link; }; struct LinkQueue { /* 链接队列类型定义 */ PNode f; /* 头指针 */ PNode r; /* 尾指针 */ typedef struct LinkQueue *PLinkQueue; /*链接队列类型的指针类型*/

存储结构 假设plqu是PLinkQueue类型的变量 plqu->f为队列的头指针，指向队列中第一个结点 plqu->r是队列尾指针，指向队列中最后一个结点(注意：这一点与顺序队列不同！) 当plqu->f 为 NULL时队列为空。

存储结构 队列的链接表示

基本运算的实现 1. 创建一个空队列 PLinkQueue createEmptyQueue_link( void ) { PLinkQueue plqu; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue)); if (plqu!=NULL) { plqu->f = NULL; plqu->r = NULL; } else printf("Out of space!! \n"); return plqu ;

2. 判断队列是否为空 int isEmptyQueue_link( PLinkQueue plqu ) {   2. 判断队列是否为空 int isEmptyQueue_link( PLinkQueue plqu ) { return (plqu->f == NULL); }

3. 进队列运算 void enQueue_link( PLinkQueue plqu, Datatype x ) { PNode p; p = (PNode )malloc( sizeof( struct Node ) ); /*申请新结点空间*/ if ( p == NULL ) printf("Out of space!"); /*申请新结点失败*/ else { p->info = x; p->link = NULL; /*填写新结点信息*/ if (plqu->f == NULL) plqu->f = p; /*插入前是空队列*/ else plqu->r->link = p; /*将新结点插入*/ plqu->r = p; /*修改对尾指针*/ }

4. 出队列运算 void deQueue_link( PLinkQueue plqu ) { PNode p;   4. 出队列运算 void deQueue_link( PLinkQueue plqu ) { PNode p; if( plqu->f == NULL ) printf( "Empty queue.\n " ); /*队列已空*/ else { p = plqu->f; plqu->f = p ->link; /*修改队头指针*/ free(p); /*释放已经删除结点空间*/ }

5.取队列头部结点的值 Datatype frontQueue_link( PLinkQueue plqu ) {   5.取队列头部结点的值 Datatype frontQueue_link( PLinkQueue plqu ) { if( plqu->f == NULL ) printf( "Empty queue.\n " ); /*队列已空*/ else return (plqu->f->info); }

4.6 队列的应用——农夫过河问题 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。河中只有一条小船，小船只能容下农夫和一件物品，只有农夫能撑船。 请问农夫该采取什么方案才能将所有的东西全部安全运到北岸。 *上机题：详细讲解使用队列求一个解的方法，理解后改用栈求出全部解 。

算法选择： 求解这个问题的最简单的方法是:一步一步进行试探，每一步都搜索当前可能的选择，对当前合适的选择再考虑下一步的各种方案。

开始状态---全部在南岸

带羊到北岸

空手回南岸

带菜到北岸

带羊回南岸

带狼到北岸

空手回南岸

带羊到北岸—终止状态

状态的表示 要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。 一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。 例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。

确定每个角色位置的函数 用整数location表示上述四位二进制描述的状态， 用下面的四个函数从上述状态中得到每个角色所在位置的代码。 函数返回值为真表示所考察的人或物在河的北岸，否则在南岸。

    确定每个角色位置的函数 int farmer(int location) { return (0 != (location & 0x08)); }   int wolf(int location) { return (0 != (location & 0x04)); } int cabbage(int location) { return (0 != (location & 0x02)); }   int goat(int location) { return (0 !=(location & 0x01)); }

算法实现中需要使用以下位运算: 假设x和y都是8位的字符，其值分别是： X= 01010111 Y= 11011010。 各种字位运算，得到的结果如下： ~x 10101000(求补) x & y 01010010 x ^ y 10001101(按位加/异或) x | y 11011111 x << 3 10111000 y >> 5 00000110

判断状态是否安全的函数 还应该分析问题中所有角色的各种可能位置构成的状态，确定其中哪些是安全的哪些是不安全的。 根据原题的描述我们知道，单独留下白菜和羊，或单独留下狼和羊在某一岸的状态是不安全的。 由此可以编一个函数，通过位置分布的代码来判断状态是否安全。

  安全状态的判断函数 int safe(int location) { // 若状态安全则返回1,否则0. // 羊吃白菜 if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location)) ) return (0); // 狼吃羊 if ((goat(location) == wolf(location)) && (goat(location) != farmer(location))) return (0); return (1); // 其他状态是安全的 }

问题的描述： 从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。

广度优先： 在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。 为避免不必要的瞎费功夫，要求在序列中不应该出现重复的状态.

农夫 狼 白菜 羊的状态变化 0000→1000 1001 → 0000 1010 0001 →1001 1100 1011 →0001 0010 →1010 0011 1011 1110 →0010 0110 →1110 1111 0100 1101 →0001 0100 →1100 0101 1101 → ×

队列的设计与使用 为了实现广度优先搜索，算法中需要使用了一个队列moveTo，它的每个元素表示一个可以安全到达的中间状态。 程序执行中,把下一步所有可能达到的安全状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的安全状态放在队列里……。 由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。

记录解的数据结构 由于需要列举的所有状态(二进制0000 ~ 1111)一共16种，所以构造一个包含16个元素的数组route来记录问题的解。 route的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把数组中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的(下标)值。 route的第i个元素记录状态i是否已被访问过，若已被访问过,则在这个数组元素中记入前驱状态值。 最后我们可以利用route元素的值建立起正确的状态路径(问题的解)。

算法4.27 农夫过河问题的求解 void farmerProblem( ) { int i, movers, location, newlocation, route[16]; PSeqQueue moveTo; moveTo=createEmptyQueue_seq( ); enQueue_seq(moveTo,0x00); for(i=0;i<16;i++) route[i]=-1; route[0]=0; while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1)) { location=frontQueue_seq(moveTo); deQueue_seq(moveTo); for(movers=1;movers<=8;movers<<=1) if ((0!=(location & 0x08))==(0!=(location & movers))) { newLocation=location^(0x08|movers); if(safe(newLocation)&&(route[newLocation]==-1)) { route[newLocation]=location; enQueue_seq(moveTo,newlocation); } } } if(route[15]!=-1) { printf("The reverse path is : \n"); for(location=15;location>=0;location=route[location]) { printf("The location is : %d\n",location); if (location==0) exit(0); } else printf("No solution.\n");

执行结果 The reverse path is : The location is : 15 The location is : 6 The location is : 14 The location is : 2 The location is : 11 The location is : 1 The location is : 9 The location is : 0

队列与栈 对队列来说，它的插入运算在表的一端进行，而删除运算却在表的另一端进行。根据队列的这一特点，在使用顺序存储结构时，用了环形队列，这样可解决假溢出问题，但要特别注意队列满和队列空的条件及描述。 对于栈来说，它的插入和删除都是在表的同一端进行的，用顺序存储结构时，要注意栈满、栈空的条件。

限制存取点的表 栈和队列的运算都限制在它们的端点上进行，所以也称为限制存取点的表。除栈和队列以外，实用的限制存取点的表还有多种.

双端队列 双端队列是一种特殊的线性表，对它所有的插入和删除都限制在表的两端进行。这两个端点分别记作end1和end2。 它好象一个特别的书架，取书和存书限定在两边进行。

双栈 双栈是一种加限制的双端队列，它规定从end1插入的元素只能从end1端删除，而从end2插入的元素只能从end2端删除。 它就好象两个底部相连的栈。

超队列 它好象一种特殊的队列，允许有的最新插入的元素最先删除。 超队列是一种输出受限的双端队列，即删除限制在一端(例如end1)进行，而插入仍允许在两端进行。 它好象一种特殊的队列，允许有的最新插入的元素最先删除。

超栈 它可以看成对栈溢出时的一种特殊的处理，即当栈溢出时，可将栈中保存最久（end1端）的元素删除。

本讲重点： 两种不同的搜索策略： 队列的ADT，存储表示和算法的实现 提高使用计算机完成问题求解的能力 一种是（使用队列实现的）广度优先(breadth_first) 搜索 另一种是（使用栈实现的）深度优先(depth_first)搜索。 本讲内容非常重要！！