1、第四章 栈和队列一一、教学内容：、教学内容：1 1、栈和队列的定义及特点；、栈和队列的定义及特点；2 2、栈的顺序存储表示和链接存储表示及操作；、栈的顺序存储表示和链接存储表示及操作；3 3、队列的顺序存储表示及操作；队列的链接存、队列的顺序存储表示及操作；队列的链接存储表示及操作；储表示及操作；4 4、栈和队列的应用举例、栈和队列的应用举例。二、教学要求：二、教学要求：1、掌握栈和队列的定义、特性，并能正确应用它们解决实、掌握栈和队列的定义、特性，并能正确应用它们解决实 际问题；际问题；2、熟练掌握栈的顺序表示、链表表示以及相应操作的实、熟练掌握栈的顺序表示、链表表示以及相应操作的实 现。特
2、别注意栈空和栈满的条件；现。特别注意栈空和栈满的条件；3、熟练掌握队列的顺序表示、链表表示以及相应操作的实、熟练掌握队列的顺序表示、链表表示以及相应操作的实 现。特别是循环队列中队头与队尾指针的变化情况。现。特别是循环队列中队头与队尾指针的变化情况。栈和队列是两种特殊的线性表，是的线性表，称限定性数据结构。内容如下：队列的应用队列的应用4.1 栈（栈（stack）一、一、栈的定义：限定仅在表的一端进行插入和删栈的定义：限定仅在表的一端进行插入和删除操作的线性表，允许进行插入和删除的一端称除操作的线性表，允许进行插入和删除的一端称为为栈顶栈顶，另一端称为，另一端称为栈底栈底，不含元素的空表称空，
3、不含元素的空表称空栈。栈。特点：先进后出（特点：先进后出（FILO）或后进先出（）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)栈的特点栈的特点根据栈的定义可知，最先放入栈中元素在栈根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放好相反，最后放入的元素最先删除，最先放入的元素最后删除。入的元素最后删除。也就是说，栈是一种后进先出也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为的线性表，简称为LIFO表。表。栈的基本操作栈的基本
4、操作1.初始化栈：初始化栈：INISTACK(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：出栈：POP(&S)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：取栈顶元素：GETTOP(S,&e)取栈S中栈顶元素。5.判栈空：判栈空：StackEmpty(S)判断栈S是否为空，若为空，返回值为true，否则返回值为false。例例1：对于一个栈，给出输入项对于一个栈，给出输入项A、B、C，如果输入项序列，如果输入项序列由由ABC组成，试给出所有可能的输出序列。组成，试给
5、出所有可能的输出序列。A进进 A出出 B进进 B出出 C进进 C出出 ABCA进进 A出出 B进进 C进进 C出出 B出出 ACBA进进 B进进 B出出 A出出 C进进 C出出 BACA进进 B进进 B出出 C进进 C出出 A出出 BCAA进进 B进进 C进进 C出出 B出出 A出出 CBA不可能产生输出序列不可能产生输出序列CAB例例2：一个栈的输入序列是一个栈的输入序列是12345，若在入栈的过程中，若在入栈的过程中允许出栈允许出栈，则栈的输出序列则栈的输出序列43512可能实现吗？可能实现吗？12345的输出呢？的输出呢？43512不可能实现，主要是其中的不可能实现，主要是其中的12顺序
6、不能实顺序不能实现；现；12345的输出可以实现，只需压入一个立即弹出的输出可以实现，只需压入一个立即弹出一个即可。一个即可。435612中到了中到了12顺序不能实现；顺序不能实现；135426可以实现。可以实现。例例3：如果一个栈的输入序列为如果一个栈的输入序列为123456，能否得到，能否得到435612和和135426的出栈序列？的出栈序列？答：答：答：答：例例4：设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：则可得到出栈的元素序列是：A、D可以（可以（B、C不行）。不行）。答：答：二、二、顺序栈顺序栈 由于栈是操作受限的线性表，因此线
7、性表的由于栈是操作受限的线性表，因此线性表的存储结构对栈也适应。存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，因此，可栈的顺序存储结构简称为顺序栈，因此，可用数组来实现顺序栈。因为栈底位置是固定不变用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量变化的，故需用一个整型变量top来指示当前栈顶来指示当前栈顶的位置，通常称的位置，通常称top为栈顶指针。为栈顶指针。因此，顺序栈的类型定义只需将顺序表的因此，顺
8、序栈的类型定义只需将顺序表的类型定义中的长度属性改为类型定义中的长度属性改为top即可。顺序即可。顺序栈的类型定义如下：栈的类型定义如下：#define N 10 typedef struct ElemType dataN;int top;SeqStack;或或 typedef struct seqlist ElemType *elem;int top;seqstack;top=-1123450栈空栈空栈顶指针top,指向实际栈顶，初值为-1top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为设数组维数为Mtop=-1,栈空，此时出栈，则下溢（栈空，此时出栈，则下溢（und
9、erflow)top=M-1,栈满，此时入栈，则上溢（栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空栈顶栈顶top 的值为栈顶元素下标，的值为栈顶元素下标，top为为-1表示空栈。表示空栈。设设S是是SeqStack类型的指针变量。即类型的指针变量。即 sdata0是栈底元素，那么栈顶指针是栈底元素，那么栈顶指针stop是是正向增加的，即进栈时需将正向增加的，即进栈时需将stop加加1，退栈时，退栈时需将需将stop 减减1。stop=-1表示空栈表示空栈(下溢下溢)，stop=N-1表示栈满。当栈满
10、时（上溢）不能再做进栈运算表示栈满。当栈满时（上溢）不能再做进栈运算;当栈空时不能再做退栈运算，此时当栈空时不能再做退栈运算，此时s-top=-1。下溢常常用来作为程序控制转移的条件。下溢常常用来作为程序控制转移的条件。1 1、初始化空栈、初始化空栈 sqstack*initstack()/创建一个空栈创建一个空栈 sqstack*s;s=(sqstack*)malloc(sizeof(sqstack);s-top=-1;return s;或void init(seqstack&l)/初始化 l.elem=new intN;l.top=-1;2 2、判断栈空、判断栈空 int sempty(s
11、eqstack*l)if(l-top=-1)return 0;else return 1;或void emptys(seqstack&s)if(s.top top=N-1)printf(“overflow!”);return;top+;s-datatop=item;或int push(seqstack&s,int x)/将x入栈if(s.top=N-1)return(0);s.top+;s.elems.top=x;return 1;4 4、退栈、退栈 void pop(seqstack*l)/出栈出栈 if(l-top=-1)printf(dont delete!“);return;else
12、l-top-;或或int pop(seqstack&s)/出栈出栈 if(s.toptop!=-1)return(s-datas.top);else exit(1);或或void gettop(seqstack&s,int&m)/取栈顶元素取栈顶元素 if(s.top=0)m=s.elems.top;栈的共享存储单元栈的共享存储单元 有时，一个程序设计中，需要使用多个同一类型有时，一个程序设计中，需要使用多个同一类型的栈的栈,这时候，可能会产生一个栈空间过小，容量发这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元生溢出，而另一个栈空间过大，造成大量存储单元浪
13、费的现象。浪费的现象。为了充分利用各个栈的存储空间，这为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优一个足够大的存储空间，让多个栈实现存储空间优势互补。势互补。栈1 顶 栈2 顶 栈1 底 栈2 底 图 两个栈共享存储单元示意图 三三 链栈链栈 栈的链式存储结构称为链栈，是插入和删栈的链式存储结构称为链栈，是插入和删除操作仅限制在表头位置上进行的单链。除操作仅限制在表头位置上进行的单链。由于只能在链表头部进行操作，栈顶指针由于只能在链表头部进行操作，栈顶指针就是链表的头指针。就
14、是链表的头指针。链栈的结点定义链栈的结点定义:typedef struct stacknode ElemType data;struct node *next;LinkStack,s1;栈的链接存储结构栈的链接存储结构 链式栈 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处进行 链式栈的栈顶在链头 适合于多栈操作 链栈的出栈算法：链栈的出栈算法：即是删除链表中的第一个元素即是删除链表中的第一个元素 链栈的入栈算法：链栈的入栈算法：即是在单链表中第一个元素的位置即是在单链表中第一个元素的位置 上添加一个元素。上添加一个元素。其他算法同单链表中相应算法。其他算法同单链表中相应算法。链栈的进栈算
15、法链栈的进栈算法struct stacknode*pushlstack(struct stacknode*t,int x)/入栈（入栈（x加入到加入到t作头指针的链栈中作头指针的链栈中)struct stacknode*node;if(node=(struct stacknode*)malloc(sizeof(s1)!=NULL)node-next=t;t=node;t-data=x;return(t);建立空链栈：建立空链栈：struct stacknode*top=NULL;/初始化空栈初始化空栈,不带头结点不带头结点从空栈始，依次调用进栈算法建立含有若干个元素的从空栈始，依次调用进栈算法
16、建立含有若干个元素的非空栈。非空栈。4.2 栈的应用举例栈的应用举例 栈结构具有的后进先出特性，致使栈成为程序栈结构具有的后进先出特性，致使栈成为程序设计中常用的工具。设计中常用的工具。一、栈的应用举例一、栈的应用举例-数制转换数制转换 十进制十进制N和其它进制数的转换是计算机实现计和其它进制数的转换是计算机实现计算的基本问题算的基本问题,其解决方法很多其解决方法很多,其中一个简单算其中一个简单算法基于下列原理法基于下列原理:N=(n div d)*d+n mod d (其中其中:div为整除运算为整除运算,mod为求余运算为求余运算)例如例如(1348)10=(2504)8，其运算过程如下：
17、其运算过程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2二、栈的应用举例文字编辑器二、栈的应用举例文字编辑器seqstack s;EDIT()char c;SETNULL(&s);cgetchar();while(c!=*)if(c=#)POP(&s);else if(c=)SETNULL(&s);else PUSH(&s,c);cgetchar();表达式求值的算法是表达式求值的算法是 “算符优先法算符优先法”。例如：例如：3*（7 2）（1）要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则：a.从左
18、算到右从左算到右 b.先乘除，后加减先乘除，后加减 c.先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为：3*（7 2）=3*5=15三、栈的应用举例表达式计算三、栈的应用举例表达式计算（2）根据上述三条运算规则，在运算的每一步）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符中，对任意相继出现的算符 1和和 2，都要比较，都要比较优先权关系。优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53表表3.1 （是提供给计算机用的表！）（是提供给计算机用的表！）（3）算法思想：）算法思想：设定两栈
19、：设定两栈：操作符栈操作符栈 OPTR，操作数栈，操作数栈 OPND 栈初始化栈初始化：设操作数栈：设操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈底的栈底元素为表达式起始符元素为表达式起始符#；依次读入字符：依次读入字符：是操作数则入是操作数则入OPND栈，是操作符则要判断：栈，是操作符则要判断：if 操作符操作符 栈顶元素栈顶元素，压入，压入OPTR栈。栈。OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3)#*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,
20、*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)背包问题求解：背包的体积为背包的体积为T,有有n件物品，其体积分别为件物品，其体积分别为Wi,i=1,2,n.从从中找出若干件刚好装满背包，则此为一组解。中找出若干件刚好装满背包，则此为一组解。方法：回溯法方法：回溯法 用栈解决用栈解决 void knap(int w,int T,int n)int k=0;do for(;T0&k=0)Push(
21、sp,k);T-=wk;if(T=0)print(sp);Pop(sp,k);T+=wk;+k;while(sp.top!=-1)|(k1 时时,则则x y zx y znn 1Void Hanoi (int n,char x,char y,char z )/将将 n 个个 编号从上到下为编号从上到下为 1n 的盘子从的盘子从 x 柱，借助柱，借助 y 柱柱 /移到移到 z 柱柱 if(n =1 )move(x,1,z );/将编号为将编号为 1 的盘子从的盘子从 x 柱移到柱移到 z 柱柱 else /将将 n-1个个 编号从上到下为编号从上到下为1n-1的盘子从的盘子从 x 柱，借助柱，借
22、助 /y 柱移到柱移到 z 柱柱 Hanoi(n-1,x,z ,y );move(x,n,z);/将编号为将编号为 n 的盘子从的盘子从 x 柱移到柱移到 z 柱柱 /将将 n-1个个 编号从上到下为编号从上到下为 1n-1的盘子从的盘子从 y 柱，借助柱，借助 x /柱移到柱移到 z 柱柱 Hanoi(n-1,y,x,z);/Hanoi4.3 4.3 队列队列4.3.1 4.3.1 队列的定义队列的定义 也是一种运算受限的线性表。它也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为除。允许删除的一端称为，允许
23、插入，允许插入的一端称为的一端称为。先进入队列的成员总是先离开队列。因此队列亦称作先先进入队列的成员总是先离开队列。因此队列亦称作先进先出进先出(First In First Out)(First In First Out)的线性表，简称的线性表，简称FIFOFIFO表。表。当队列中没有元素时称为当队列中没有元素时称为。在空队列中。在空队列中依次加入元素依次加入元素a a1 1,a,a2 2,a,an n之后，之后，a a1 1是是，a an n是是。显然退出队列的次序也只能是。显然退出队列的次序也只能是a a1 1,a,a2 2,a,an n 。下图是队列的示意图：队列的基本运算队列的基本运
24、算 队列可定义如下五种基本运算：1初始化队列初始化队列 InitQueue(&Q)将队列Q设置成一个空队列。2入队列入队列 EnQueue(&Q,X)将元素X插入到队尾中，也称“进队”，“插入”。3出队列出队列 DeQueue(&Q,&e)将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。4取队头元素取队头元素 GetHead(Q,&e)得到队列Q的队头元素之值，并用e返回其值。5判队空判队空 QueueEmpty(Q)判断队列Q是否为空，若为空返回1，否则返回0。4.4.2 非循环队列和循环队列（顺序队列）非循环队列和循环队列（顺序队列）队列的顺序存储结构称为顺序队列，和顺序队
25、列的顺序存储结构称为顺序队列，和顺序表一样，顺序队列也是必须用一个数组空间来存表一样，顺序队列也是必须用一个数组空间来存放当前队列中的元素。放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指要设两个指针和分别指示队头和队尾元素在队列中的位置，可约示队头和队尾元素在队列中的位置，可约定队头指针指向队头元素的前一个位置，定队头指针指向队头元素的前一个位置，队尾指针指向队尾元素，队尾指针指向队尾元素，它们的初始值在队它们的初始值在队列初始化时均应置为列初始化时均应置为-1。入队时尾指针加，将新元素插入在尾指针入队时尾指针加，将新元素插入在尾指针所指的位置上。出队时头指针
26、加。由此可见，所指的位置上。出队时头指针加。由此可见，当头尾指针相等时队列为空。当头尾指针相等时队列为空。队列的顺序存储结构定义：队列的顺序存储结构定义：#define N 100typedef struct elemtype aN;int front;int rear;sequeue;typedef struct queue int*queue;int front;int rear;cyclequeue;0 1 2 3FrontrearabcFront rear(a)(a)队列初始为空（队列初始为空（b b）A,B,CA,B,C入队入队 b c front rear front rear (
27、c)a(c)a出队出队 (d)b,c(d)b,c出队，队为空出队，队为空 n队空：队空：Q.front=Q.rearn队满：队满：Q.rear=N-1（假溢出）（假溢出）求队长：求队长：Q.rear-Q.frontn 入队：将队尾指针加一入队：将队尾指针加一,新元素按新元素按 rear n 指示位置加入指示位置加入.n 出队：将队头指针加一，出队：将队头指针加一，n 即即front=front+1非循环队列非循环队列 为充分利用向量空间，克服上述假上溢现象，为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循
28、环向量，存储在其中的队列称为称这种向量为循环向量，存储在其中的队列称为循环队列（循环队列（Circular Queue)。在循环队列中进行在循环队列中进行出队、入队操作时，头尾指针仍要加出队、入队操作时，头尾指针仍要加1，朝前移动。，朝前移动。只不过当头尾指针指向向量上界（只不过当头尾指针指向向量上界（QueueSize-1）时，其加时，其加1操作的结果是指向向量的下界操作的结果是指向向量的下界0。显然，因为循环队列元素的显然，因为循环队列元素的空间可以被重新利用，除非向空间可以被重新利用，除非向量空间真的被队列元素全部占量空间真的被队列元素全部占用，否则不会上溢。因此，除用，否则不会上溢。因
29、此，除一些简单的应用外，真正实用一些简单的应用外，真正实用的顺序队列是循环队列。的顺序队列是循环队列。由于入队时尾指针向前追赶头指针，出队时头由于入队时尾指针向前追赶头指针，出队时头指针向前追赶队尾指针，故队空和队满时头尾指针指针向前追赶队尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过均相等。因此，我们无法通过Q.front=Q.rear来来判断队列判断队列“空空”还是还是“满满”。解决此问题的方法至少有两种：解决此问题的方法至少有两种：其一是另设一个布尔变量以区别队列的空和满；其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾其二是少用一个元素的
30、空间，约定入队前，测试尾指针在循环意义下加指针在循环意义下加1取模后是否等于头指针，若取模后是否等于头指针，若相等则认为队满（注意：相等则认为队满（注意：rear所指的单元始终为空）所指的单元始终为空）012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态初始状态J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外设一个标志以区别队空、队满另外设一个标志以区别队空、队满2.少用一个元素空间：少用一个元素空间：队空：队空：fron
31、t=rear 队满：队满：(rear+1)%N=front队空：Q.front=Q.rear队满：Q.front=(Q.rear+1)%N入队:Q.rear=(Q.rear+1)%N出队:Q.front=(front+1)%N;求队长:(Q.rear-Q.front+N)%N循环队列循环队列循环队列的基本运算实现循环队列的基本运算实现1 初始化空队列初始化空队列只要将只要将front 和和rear相等即可。相等即可。void initqueue(cyclequeue&Q)/初始化空队列初始化空队列Q Q.queue=new intN;Q.front=0;Q.rear=0;2 入队入队（1）检查
32、队列是否已满，若队满，则进行溢出错误）检查队列是否已满，若队满，则进行溢出错误 处理；处理；（2）将队尾指针后移一个位置（即加）将队尾指针后移一个位置（即加1），指向下），指向下 一单元。一单元。（3）将新元素赋给队尾指针所指单元；）将新元素赋给队尾指针所指单元；void append(cyclequeue&Q,int x)/入队入队 if(Q.rear+1)%N)!=Q.front)Q.rear=(Q.rear+1)%N;Q.queueQ.rear=x;int del(cyclequeue&Q,int&x)/出队出队 if(Q.rear=Q.front)return 0;x=Q.queue(
33、Q.front+1)%N;Q.front=(Q.front+1)%N;return 1;3.出队出队（1）检查队列是否为空，若队空，则进行下溢错误处理；）检查队列是否为空，若队空，则进行下溢错误处理；（2）取队首元素的值。）取队首元素的值。（3）将队首指针后移一个位置（即加）将队首指针后移一个位置（即加1）；）；4 取队头元素取队头元素int qempty(cyclequeue&Q，int&x)/取队头元素取队头元素 if(Q.rear=Q.front)retuen 0;else x=Q.elemrear;return 1;5 判队列空否判队列空否 int qempty(cyclequeue&
34、Q)/队空和满的判定队空和满的判定 if(Q.rear=Q.front)return 0;else return(1);6 求队列的长度求队列的长度 int length(cyclequeue&Q)/求长度求长度 return(N+(Q.rear-Q.front)%N);7 输出队列中的所有元素输出队列中的所有元素void printout(cyclequeue&Q)/输出队列中的所有元素输出队列中的所有元素 int i;i=(Q.front+1)%N;while(i!=(Q.rear+1)%N)printf(%6d,Q.queuei);i=(i+1)%N;printf(n);4.3.3 4.
35、3.3 链队列链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。nullQQ.frontQ.rear非空队列Q.frontQ.rearnull空队列Q链队列示意图 和顺序队列类似，我们也是将这两个指和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型定义为：针封装在一起，将链队列的类型定义为：typedef struct qnode /定义链表中结点定义链表中结点结构结构int data;struct qnode*next
36、;qnodetype;typedef struct fr /定义队列头尾指针的存储类型定义队列头尾指针的存储类型 qnodetype*front;qnodetype*rear;linkqueue;下面给出链队列上实现的基本运算：下面给出链队列上实现的基本运算：建立空链队列：void initqueue(linkqueue&Q)/建立链式队列，带头节点建立链式队列，带头节点 struct qnode*s;s=new struct qnode;/开辟头结点开辟头结点 s-next=NULL;Q.rear=s;Q.front=s;Q.frontQ.rearnullVoid emptyqueue(li
37、nkqueue&Q)/链式队列判空链式队列判空 if(Q.front=Q.rear)return 1;else return 0;队列的判空：void qappend(linkqueue&Q,int x)/将x入队qnodetype*p;p=new struct qnode;p-data=x;p-next=NULL;Q.rear-next=p;/入队 Q.rear=p;入队操作nullQQ.frontQ.rearxnullsnullQQ.rearxnullQ.frontp出队出队int qdelete(linkqueue&Q,int&x)/出队出队 qnodetype*p;if(Q.front
38、-next=NULL)return(0);p=Q.front-next;Q.front-next=p-next;x=p-data;if(Q.rear=p)Q.rear=Q.front;delete(p);return(1);输出其中的所有元素void write(linkqueue&Q)struct qnode*p;p=Q.front-next;do printf(%5d,p-data);/输出其中的所有元素 p=p-next;while (p!=NULL);队列的应用队列的应用 队列在日常生活中和计算机程序设计中，有着队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方
39、面例子非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。来说明它，其它应用在后面章节中将会遇到。第一个例子就是第一个例子就是CPU资源的竞争问题。在具有多资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终各自运行自己的程序，它们分别通过各自终端向操作系统提出使用端向操作系统提出使用CPU的请求，操作系统按的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个照每个请求在时间上的先后顺序，将其排成一个队列，每次把队列，每次把CPU分配给队头用户使用，当相应分配给队
40、头用户使用，当相应的程序运行结束，则令其出队，再把的程序运行结束，则令其出队，再把CPU分配给分配给新的队头用户，直到所有用户任务处理完毕。新的队头用户，直到所有用户任务处理完毕。第二个例子就是主机与外部设备之间速度不匹配的第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决打印，由于速度不匹配，显
41、然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。的正确，又使主机提高了效
42、率。队列应用举例队列应用举例 划分子集问题划分子集问题问题描述：已知集合问题描述：已知集合A=a1,a2,an，及集合上的，及集合上的关系关系R=(ai,aj)|ai,aj A,i j，其中，其中(ai,aj)表示表示ai与与aj间存在冲突关系。要求将间存在冲突关系。要求将A划分成划分成互不相交的互不相交的子集子集A1,A2,Ak,(k n)，使任何子集中的元素均无冲突，使任何子集中的元素均无冲突关系，同时要求关系，同时要求分子集个数尽可能少。分子集个数尽可能少。例例 A=1,2,3,4,5,6,7,8,9 R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9)
43、,(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集划分为：可行的子集划分为：A1=1,3,4,8 A2=2,7 A3=5 A4=6,9 算法思想：利用循环筛选。从第一个元素开始，算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组直到所有元素进组所用数据结构所用数据结构冲突关系矩阵冲突关系矩阵rij=1,i,j有冲突有冲突rij=0,i,j无冲突无冲突循环队列循环队列cqn数组数组resultn存放
44、每个元素分组号存放每个元素分组号工作数组工作数组newrn本章小结本章小结线性表、栈与队的异同点线性表、栈与队的异同点相同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。线性表（只是对插入、删除运算加以限制）。不同点：不同点：运算规则不同，线性表为随机存取，而栈是只允许在一运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表端进行插入和删除运算，因而是后进先出表LIFOLIFO；队列；队列是只允许在一端进行插入、另一端进行删除运算，因而是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表是先进先出表FIFOFIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。和简化设计等。本章作业P82 1，3，4，6，9，10，11，12
