C语言数据结构-第04讲 栈.ppt

《C语言数据结构-第04讲 栈.ppt》由会员分享，可在线阅读，更多相关《C语言数据结构-第04讲 栈.ppt（82页珍藏版）》请在三一办公上搜索。

1、实用数据结构基础,第3章 栈,第 3 章 栈,知 识 点 栈的定义和特点栈的基本运算和算法栈的典型应用难 点 后缀表达式的算法数制的换算利用本章的基本知识设计相关的应用问题,要 求 掌握栈的特点掌握栈的基本运算熟悉栈的各种实际应用 能设计栈的应用的典型算法了解栈的运算时间复杂度分析,第3章 目录,3-1 栈的定义与运算 3-2 栈的存储和实现 3-3 栈的应用举例小 结实验3 栈子系统习题3,3-1 栈的定义和运算,3-1-1 栈（Stack）的定义1.栈的定义 栈是限制在表尾进行插入和删除的线性表。,进栈,出栈,图3-1栈的 示意图,2.栈的特性（1）栈的主要特点是“后进先出”（2）允许插入

2、、删除的这一端称为栈顶（Top），另一端称为栈底（Bottom）。3.应用实例（1）分币筒；（2）铁路调度站。,3-1-2 栈的运算1进栈：Push（&s，x）初始条件：栈s已存在且非满。操作结果：在栈顶插入一个元素x，栈中多了一个元素。2出栈：Pop（&s）初始条件：栈s存在且非空。操作结果：删除栈顶元素，栈中少了一个元素。3读栈顶元素：ReadTop（s，&e）初始条件：栈s已存在且非空。操作结果：输出栈顶元素，但栈中元素不变。,4.判栈空：SEmpty（s）初始条件：栈s已存在。操作结果：若栈空则返回为0，否则返回为1。5.判栈满：SFull（s）初始条件：栈s已存在。操作结果：若栈满则

3、返回为0，否则返回为1。6.显示栈元素：ShowStack(s)初始条件：栈s已存在，且非空。操作结果：显示栈中所有元素。,3-2 栈的存储和实现,3-2-1 顺序栈1 顺序栈的实现（1）用一维数组实现顺序栈 设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C+）语言描述如下：#define MAXLEN 10/分配最大的栈空间 char sMAXLEN；/数据类型为字符型 int top；/定义栈顶指针,（2）用结构体数组实现顺序栈 顺序栈的结构体描述：#define MAXLEN 10/分配最大的栈空

4、间 typedef struct/定义结构体 datatype dataMAXLEN;/datatype可根据用需要定义类型 int top；/定义栈顶指针 SeqStack；再定义一个指向顺序栈的指针：SeqStack*S；/定义S为结构体类型的指针变量,（3）栈操作的示意图如图3-3所示。,top=-1,top=0,top=5,top=3,top=9,(a)(b)(c)(d)(e),当top=-1时，表示栈空，如图3-3（a）；当top=0时，表示栈中有一个元素，如图3-3（b）表示栈中已输入一个元素A；入栈时，栈顶指针上移，指针top加1，如图3-3（c）是6个元素入栈后的状况；出栈时，

5、栈顶指针下移，指针top减1，如图3-3（d）是在F、E相继出栈后的情况。此时栈中还有A、B、C、D 4个元素，top=3，指针已经指向了新的栈顶。但是出栈的元素F、E仍然在原先的存储单元，只是不在栈中了，因为栈是只能在栈顶进行操作的线性表。当top=9时，即top=MAXLEN1，表示栈满，如图3-3（e）。,2顺序栈运算的基本算法（1）置空栈 首先建立栈空间，然后初始化栈顶指针。SeqStack*Snull（）SeqStack*s；s=new(SeqStack)；/在C语言中用s=malloc（sizeof（SeqStack）；s-top=1；/置栈空 return s；,（2）进栈 进栈

6、运算是在栈顶位置插入一个新元素x，其算法步骤为：(a)判栈是否为满，若栈满，作溢出处理，并返回0；(b)若栈未满，栈顶指针top加1；(c)将新元素x送入栈顶，并返回1。int Push(SeqStack*s，datatype x)if（s-top=MAXLEN1）return 0；/栈满不能入栈，且返回 0 else s-top+；s-datas-top=x；/栈不满，则压入元素x return 1；/进栈成功，返回1,（3）出栈 出栈运算是指取出栈顶元素，赋给某一个指定变量x，其算法步骤为：(a)判栈是否为空，若栈空，作下溢处理，并返回0；(b)若栈非空，将栈顶元素赋给变量x；(c)指针t

7、op减1，并返回1。int Pop（SeqStack*s，datatype*x）if(SEmpty(s)return 0；/若栈空不能出栈，且返回0 else*x=s-datas-top；/栈不空则栈顶元素存入*x s-top-；return 1；/出栈成功，返回1,（4）读栈顶元素datatype ReadTop（SeqStack*s）if(SEmpty(s)return 0；/若栈空，则返回0 else return(s-datas-top)；/否则，读栈顶元素，但指针未移动（5）判栈空int SEmpty（SeqStack*s）if（s-top=1）return 1；/若栈空，则返回1

8、else return 0；/否则返回0,（6）判栈满 int SFull（SeqStack*s）if（s-top=MAXLEN1）return 1；/若栈满，则返回1 else return 0；/否则返回0 3-2-2 链栈1链栈的实现 用链式存储结构实现的栈称为链栈。因为链栈的结点结构与单链表的结构相同，通常就用单链表来实现，在此用LinkStack表示，即有：typedef struct stacknode/栈的存储结构 datatype data;/定义数据类型 struct stacknode*next;/定义一个结构体的链指针 stacknode;，*Linkstack；Link

9、stack top；/top为栈顶指针,由于栈中的操作只能在栈顶进行的，所以用链表的头部做栈顶是最合适的。链栈结构如图3-4所示。,图3-4 链栈示意图,2链栈基本操作：（1）入栈 void Push(linkstack*s,int x)stacknode*p=new stacknode;/申请一个新结点p-data=x;/数据入栈p-next=s-top;/修改栈顶指针s-top=p;,（2）出栈 int Pop(linkstack*s)int x;/定义一个变量x，用以存放出栈的元素 stacknode*p=s-top;/栈顶指针指向p x=p-data;/栈顶元素送x s-top=p-n

10、ext;/修改栈顶指针 delete p;/回收结点p return x;/返回栈顶元素,（3）显示 void ShowStack(linkstack*s)stacknode*p=s-top;if(p=NULL)/若栈空，作“栈空”显示 printf(栈为空);else printf(栈元素为：);while(p!=NULL)/栈非空，则显示栈中所有元素 printf(%6d,p-data);/输出一个元素 p=p-next;/修改栈顶指针 printf(n);,3-3.栈的应用举例,3-3-1 数制转换 数值进位制的换算是计算机实现计算和处理的基本问题。比如将十进制数N转换为j进制的数，其解

11、决的方法很多，其中一个常用的算法是除j取余法。将十进制数每次除以j，所得的余数依次入栈，然后按“后进先出”的次序出栈便得到转换的结果。其算法原理是：N=（N/j）*j+N%j 其中：/为整除，%为求余,【例3-1】将十进制数138转换为二进制数 N N/2（整除）N%2（求余）138 69 0 69 34 1 34 17 进 0 出 17 8 栈 1 栈 8 4 次 0 次 4 2 序 0 序 2 1 0 1 0 1（138）10=（10001010）2,1算法思想如下：（1）若 N0，则将N%j 取得的余数压入栈s中，执行（2）；若N=0，将栈s的内容依次出栈，算法结束。（2）用N/j 代替

12、 N（3）当N0，则重复步骤（1）、（2）。,2.算法的实现：void Conversion(int n)/将十进制数n转换为二进制数 linkstack s;int x;s.top=NULL;do x=n%2;/除2取余 n=n/2;stacknode*p=new stacknode;/申请一个新结点 p-next=s.top;/修改栈顶指针 s.top=p;s.top-data=x;/入栈,while(n);printf(转换后的二进制数值为：);while(s.top)/余数出栈处理 printf(%d,s.top-data);/输出栈顶的余数 stacknode*p=s.top;/修改

13、栈顶指针 s.top=s.top-next;delete p;/回收一个结点，C语言中用free p,3-3-2 表达式求值表达式是由运算对象、运算符、括号等组成的有意义的式子。1中缀表达式（Infix Notation）一般我们所用表达式是将运算符号放在两运算对象的中间，比如：a+b，c/d等等，我们把这样的式子称为中缀表达式。2后缀表达式（Postfix Notation）后缀表达式规定把运算符放在两个运算对象（操作数）的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次次序进行。3中缀表达式转换为后缀表达式 其转换方法采用运算符优先算法

14、。转换过程需要两个栈：一个运算符号栈和一个后缀表达式输出符号栈。,（1）读入操作数，直接送输出符号栈。（2）读入运算符，压入运算符号栈。(a)若后进的运算符优先级高于先进的，则继续进栈；(b)若后进的运算符优先级不高于先进的，则将运算符号栈内高于或等于后进运算符级别的运算符依次弹出后，自己进栈。（3）括号处理：(a)遇到开括号“（”，进运算符号栈；(b)遇到闭括号“）”，则把最靠近的开括号“（”，以及其后进栈的运算符依次弹出到输出符号栈（括号均不压入输出符号栈）。（4）遇到结束符“#”，则把运算符号栈内的所有运算符号依次弹出，并压入输出符号栈。（5）若输入为+、单目运算符，改为0与运算对象在前

15、，运算符在后。例如：A，转换为：0A。,【例3-2】A/B C+D*EA*C,【例3-3】3+4/（25（6+15）*8,得到后缀表达式为：3 4 25 6 15+/8*+4后缀表达式求值 后缀表达式求值的运算要用到一个数栈stack和一个存放后缀表达式的字符型数组exp。其实现过程就是从头至尾扫描数组中的后缀表达式：（1）当遇到运算对象时，就把它插入到数栈stack中；（2）当遇到运算符时，就执行两次出栈的操作，对出栈的数进行该运算符指定的运算，并把计算的结果压入到数栈stack。把它插入到数栈stack中；（3）重复（1）、（2），直至扫描到表达式的终止符“#”，在数栈的栈顶得到表达式的值

16、。,以例【例3-3】的结果看后缀表达式的计算过程：3 4 25 6 15+-/8*+第1次计算结果为：21 第2次计算结果为：4 第3次计算结果为：1 第4次计算结果为：8 第5次计算结果为：11,3-3-3 子程序调用（Subroutine Call）在计算机程序设计中，子程序的调用及返回地址就是利用堆栈来完成的。在C(或C+)语言的主函数对无参子函数的嵌套调用过程中，在调用子程序前，先将返回地址保存到堆栈中，然后才转去执行子程序。当子函数执行到return语句（或函数结束）时，便从栈中弹出返回地址，从该地址处继续执行程序。例如：主函数调用子函数a()时，则在调用之前先将a函数返回地址压入栈

17、中；在子函数a()中调用子函数b()时，又将b函数返回地址压人栈中；同样，在子函数b()中调用子函数c()时，又将c函数返回地址压人栈中。其调用返回地址进栈示意图如图3-5所示。,图3-5 无参函数嵌套调用返回地址进栈示意图 当执行完子函数c()以后，就从栈顶弹出c()函数返回地址，回到子函数b()；子函数b()执行完毕返回时，又从栈顶弹出b函数返回地址，回到子函数a()；子函数a()返回时，再在栈顶弹出a函数返回地址，回到主函数，继续执行主函数程序。无参函数嵌调用返回示意图如图3-6所示。,返回地址栈：,图3-6 无参函数嵌套调用返回示意图,3-3-4 递归调用1递归 一个直接调用自己，或者

18、通过一系列调用语句间接地调用自己的函数称为递归函数。在程序设计中，有许多实际问题是递归定义的，使用递归的方法编写程序将使许多复杂的问题大大简化。所以，递归是程序设计中的一个强有力的工具。2典型例子（1）2阶斐波那契（Fibonacci）数列,0 n=01 n=1Fib(n1)+Fib(n2)其它情况,Fib(n)=,（2）阶乘函数 n!的定义为：,Fac(n)=,1 n=0/递归终止条件,n*Fac(n-1)n0/递归步骤,根据定义不难写出相应的递归函数：int fac(int n)if(n=0)return 1；else return(n*fac(n1)；,3-3-5 中断处理和现场保护1.

19、中断处理（Interrupt Processing）在C+语言中，系统调用是通过中断来进行，中断调用示意图如图3-8所示。,图3-8 中断调用示意图如 如果把中断处理想象成函数调用，则中断处理程序可以看成被调用的函数。,2.现场保护和恢复 执行中断时，微处理机有时必须对状态寄存器，累加器，以及相关的寄存器对进行现场保护（压栈）；中断处理完毕，则必须按后进先出的原则恢复现场（出栈）。下面，我们以汇编语言来说明现场保护和恢复的原理：；接受中断处理 PUSH AX；保护现场 PUSH BX PUSH CX PUSH BP PUSHF；F状态寄存器进栈；中断处理 POPF；恢复现场，后进栈的先出栈 P

20、OP BP POP CX POP BX POP AX,（1）栈是一种运算受限制的线性表，它只允许在栈顶进行插入和删除等操作。（2）栈的逻辑结构和线性表相同，数据元素之间存在一对一的关系，其主要特点是“后进先出”。（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。（4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。（5）熟悉栈在计算机的软件设计中的各种应用，能灵活应用栈的基本原理解决一些综合性的应用问题。,小 结,实验3 栈子系统,1实验目的（1）掌握栈的特点及其描述方法。（2）用链式存储结构实现一个栈。（3）掌握建栈的各种等基本操作。（4）掌握

21、栈的几个典型应用的算法。2.实验内容（1）设计一个字符型的链栈；（2）编写进栈、出栈、显示栈中全部元素的程序；（3）编写一个把十进制整数转换成二进制数的应用程序；（4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序；（5）设计一个选择式菜单，以菜单方式选择上述操作。,栈 子 系 统*1-进 栈*2-出 栈*3-显 示*4-数制转换*5-逆波兰式*0-返 回*请选择菜单号：*教材p64第3行void Stack()，在作为子系统上机时上机时改为：void main(),习题3,参考习题解答,返回,实用数据结构基础,第4章 队列,第4章 队列,知 识 点 队列的定义和特点队列的存储实现

22、及运算实现队列的应用举例 难 点 循环队列的特点及判断溢出的条件利用队列的特点设计相关的应用问题,要 求 熟练掌握以下内容：队列的特点和基本运算 循环队列的特征和基本运算 了解以下内容：队列运算的时间复杂性分析 队列的实际应用,第 4 章 目录,4-1 队列的定义和基本运算4-2 队列的存储及运算的实现 4-3 队列的应用举例小 结实验4 队列子系统习题4,4-1 队列的定义和基本运算,4-1-1 队列（Queue）的定义1队列的定义 设有n个元素的队列Q=（a1，a2，a3，an），则称a1为队首元素，an为队尾元素。队列中的元素按，a1，a2，a3，an1，an的次序进队，按a 1，a2，

23、a3，an1，an次序出队，即队列的操作是按照“先进先出”的原则进行的。2.队列的特性（1）队列的主要特性是“先进先出”。（2）队列是限制在两端进行插入和删除操作的线性表。能够插入元素的一端称为 队尾（Rear），允许删除元素的一端称为 队首（Front）。,图4-1 队列示意图,a1 a2 a3 a4 a5 an,入队,出队,4.队列的实例（1）如车站排队买票或自动取款机排队取款。（2）在计算机处理文件打印时，为了解决高速的CPU与低速的打印机之间的矛盾，对于多个请求打印文件，操作系统把它们当作可以被延迟的任务，提出打印任务的先后顺序，就是它们实际打印的先后顺序。即按照“先进先出”的原则形成

24、打印队列。,4-1-2 队列的基本运算（1）入队操作：InQueue（q，x）初始条件：队q存在且未满。操作结果：输入一个元素x到队尾，长度加1。（2）出队操作：OutQueue（q，x）初始条件:队q存在，且非空。操作结果：删除队首元素，长度减1。（3）读队头元素：ReadFront（q，x）初始条件：队q存在且非空。操作结果：读队头元素，队列不变。,（4）显示队列中元素ShowQueue(q）初始条件：队列q存在，且非空。操作结果：显示队列中所有元素。（5）判队空操作：QEmpty（q）初始条件：队q存在。操作结果：若队空则返回为0，否则返回为1。（6）判队满操作：QFull（q）初始条件

25、：队q存在。操作结果：若队满则返回为0，否则返回为1。（7）求队列长度Qlen（q）初始条件：队列q存在。操作结果：返回队列的长度。,4-2 队列的存储实现及运算实现,4-2-1 顺序队列1顺序队列 顺序队列是用内存中一组连续的存储单元顺序存放队列中各元素。所以可以用一维数组QMAXLEN作为队列的顺序存储空间，其中MAXLEN为队列的容量，队列元素从Q0单元开始存放，直到QMAXLEN1单元。因为队头和队尾都是活动的，因此，除了队列的数据以外，一般还设有队首（front）和队尾（rear）两个指针。,顺序队可以用C+语言定义：#define MAXLEN 10/队列的最大容量 typedef

26、 struct datatype QMAXLEN；/datatype 可根据用户需要定义 int front=1,rear=1；/定义队头、队尾指针，并置队列为空 Queue；Queue*p；/定义一个指向队的指针变量 p=new Queue；/申请一个顺序队的存储空间/在C中用p=malloc（sizeof（Queue）设：队头指针：p-front 指向队头元素前面一个位置 队尾指针：p-rear 指向队尾元素。,（1）判队空 当p-front=p-rear=1时表示队空。如图4-2（a）（2）入队 在无溢出的情况下，队尾指针加1，新元素即可入队：p-rear+；/先将队尾指针加1 p-Qp

27、-rear=x；/入队（3）出队。在队列非空的情况下允许出队，出队时队头指针加1，队头元素即可输出：p-front+；x=p-Qp-front；/队头元素送x（4）队列的长度：m=(p-rear)(p-front)；（5）判队满：m=MAXLEN；判队空：m=0。,Rear=-1front=-1(a),rear=4,rear=7,rear=9,front=-1,front=4,front=4,(b)(c)(d),图4-2,从示意图中可以看到，随着入队、出队操作的进行，整个队列会整体向后移动，这样就出现了图4-2（d）中的现象：队尾指针虽然已经移到了最后，而队列却未真满的“假溢出”现象，使得队列

28、的空间没有得到有效的利用。2循环队列 为了解决上述队列的“假溢出”现象，要做移动操作，当移动数据较多时将会影响队列的操作速度。一个更有效的方法是将队列的数据区Q0.MAXLEN-1看成是首尾相连的环，即将表示队首的元素Q0与表示队尾的元素QMAXLEN1连接起来，形成一个环形表，这就成了循环队列，如图4-3所示。,图4-3 循环队列示意图,MAXLEN-1,图4-4是假设长度为10的循环队列操作示意图。因为是头尾相接的循环结构，所以将入队时的队尾指针加1操作修改为：p-rear=(p-rear+1)%MAXLEN；将出队时的队头指针加1操作修改为：p-front=(p-front+1)%MAX

29、LEN；在图4-4（a）中，此时front=4，rear=8，队列中具有:a6、a7、a8、a9四个元素；随着a10a15相继入队，此时 front=4，rear=4，队列已满，如（b）所示，可见在队满情况下有：front=rear。,若在（a）的情况下，a6a9相继出队，此时队空，front=8，rear=8，如（c）所示，也有：front=rear，也就是说，仅根据等式front=rear 无法有效判别是“队满”还是“队空”。两种常用的方法：（1）规定：当front=rear，表示循环队列为空；当front=（rear+1）%MAXLEN，表示循环队列为满。（2）在定义结构体时，附设一个存

30、储循环队列中元素个数的变量n，当n=0时表示队空；当n=MAXLEN时为队满。,循环队列的结构体类型定义如下：typedef structdatatype dataMAXLEN；/定义数据的类型及数据的存储区 int front，rear；/定义队头、队尾指针 int n；/用以记录循环队列中元素的个数 csequeue；/循环队列变量名 3.循环队列的基本运算（1）置空队 csequeue*IniQueue()q=new csequeue;/在c语言中用malloc(sizeof(csequeue)q-front=q-rear=MAXLEN1；q-n=0；return q；,（2）入队int

31、 InQueue(csequeue*q,datatype x)if(n=MAXLEN)printf(队满)；return 0；/队满不能入队，返回0 else q-rear=(q-rear+1)%MAXLEN；q-dataq-rear=x；q-n+；return 1；/入队完成，返回1,（3）出队int Outsequeue(csequeue*q,datatype*x)if(n=0)printf(队空)；return 0；/队空不能出队，返回0 else q-front=(q-front+1)%MAXLEN；*x=q-dataq-front；/读出队头元素 q-n；return 1；/出队完成

32、，返回1,（4）判队空 int Empsequeue(csequeue*q)if(q-n=0)return 1；else return 0；4-2-2 链队列1链队列的结构 队列的链式存储结构称为链队列（或链队），实际上它是一个带有头指针（front）和尾指针（rear）的单链表。为了处理方便，也可以给链队列附加一个头结点。链队列为空的条件是front=rear，即队列的头指针和尾指针均指向表头结点，如图4-5（a）所示。,图4-5 链队列的入队、出队,图4-5中头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，有时也两个指针封装在一个结构中。2链队的描述：typedef

33、struct queuenodedatatype data;/datatype为特定的类型，根据具体情况可以是char或int等 struct queuenode*next;queuenode;/链队结点的类型datatypetypedef structqueuenode*front,*rear;linkqueue;/将头指针、尾指针封装在一起的链队,3头指针和尾指针封装在一个结构中的链队列 如图4-6所示为头指针和尾指针封装在一个结构中的链队列。,图4-6 链队列示意图,4链队的基本运算：（1）入队（进队）void InQueue(linkqueue*q)/进队函数 int x;/定义入队元

34、素类型 queuenode*p=new queuenode;/申请一个新结点 p-data=x;/输入元素p-next=NULL;/修改指针if(q-front=NULL)q-front=p;elseq-rear-next=p;q-rear=p;,（2）出队int OutQueue(linkqueue*q,int*v)/出队函数queuenode*p;if(q-front=NULL)/判队空 return 0;else p=q-front;/若队不空，则作出队处理*v=p-data;q-front=p-next;if(q-front=NULL)q-rear=NULL;delete p;/回收结

35、点 return 1;/返回1,（3）读队头元素void ReadFront(linkqueue*q)/读队首元素函数if(q=NULL|q-front=NULL)/判队空 printf(队空!);else printf(q-front-data);/若队不空，则读队头元素,（4）显示队列中元素void ShowQueue(linkqueue*q)/显示队列queuenode*p=q-front;if(p=NULL)/判队空printf(队列为空!);else while(p!=NULL)/若队不空，则输出队中元素 printf(p-data);p=p-next;/修改指针 printf(n)

36、;,队列是一种应用广泛的数据结构，凡具有“先进先出”需要排队处理的问题，都可以使用队列来解决。1.队列在输入、输出管理中的应用 在计算机进行数据输入、输出处理时，由于外部设备的速度远远低于CPU数据处理的速度，此时可以设定一个“队列缓冲区”进行缓冲。当计算机要输出数据时，将计算机的数据按块（例如每块512B）逐个添加到“队列缓冲区”的尾端，而外部设备则按照其输出速度从队首逐个取出数据块输出。这样，虽然输出数据速度较慢，但却能保证与计算机输出的数据有完全相同的次序，而不致发生输出次序的混乱或数据的丢失。,4-3 队列应用举例,2.对CPU的分配管理 一般的计算机系统只有一个CPU，如果在系统中有

37、多个进程都满足运行条件，这就可以用一个就绪队列来进行管理。当某个进程需要运行时，它的进程名就被插入到就绪队列的尾端。如果此队列是空的，CPU就立即执行该进程；如果此队列非空，则该进程就需要排在队列的尾端进行等待。CPU总是首先执行排在队首的进程，一个进程分配的一段时间执行完了，又将它插入到队尾等待，CPU转而为下一个出现在队首的进程服务。如此，按“先进先出”的原则一直进行下去，直到执行完的进程从队列中逐个删除掉。,3优先队列（Priority Queue）在实际应用中，有时往往需要根据任务的优先级别来决定先做那些最重要的事情，此时必须对这种“先进先出”的规则进行适当的修改。假设每个元素都有一个

38、相当于权的数据项，那么我们就可以根据权值的大小来决定元素出队的顺序。也就是说，在队列中哪一个优先级最高，那一个就优先出队。这种按优先级高低来决定出队顺序的队列，称为优先队列。优先队列的一个典型的应用就是批处理操作系统中的作业处理。每个作业都有一个优先级，系统在处理文件的时候，并不是根据一般队列的“先进先出”原则，而是根据文件优先级的高低来选择处理对象。,在优先队列中的每一个元素都有一个被称为权的数据项，权的大小决定了元素的优先级。实现优先队列有两种方法：（1）按权的大小进行插入，使整个队列始终保持按优先级次序排列的状态，而删除操作则和普通队列一样，只删除队首元素。（2）插入操作和普通队列一样，

39、只在队尾进行插入，而删除操作则是根据元素的优先级来进行的，即只能删除优先级最高的元素。限于篇幅，有关优先队列具体算法的实现，在此不作介绍了。,4双队列（Double-ends Queue）操作系统的工作调度所采用的则是双队列，这种队列的两端都可以存取数据，其结构如图4-7所示。取出 取出 存入 存入 图4-7 双队列结构 如果将图4-7切成左、右两部分，则成了两个独立的栈，所以双队列就是将两个栈的栈底结合起来而构成的。与队列相同的是双队列也需要两个指针分别指向结构的两端。CPU的调度在多人使用的计算机系统中是一种重要的概念，其调度的方法也可分为：输入限制性双队列和输出限制性双队列等形式。,输入

40、限制性双队列由双向队列数据输入、从队头输出数据、从队尾输出数据三部分组成，可以由用户按照提示自由选择“从队头输出”或“从队尾输出”，以模拟各种可能的输出结果。（1）向队列数据输入InQueue()void InQueue(int val)/输入队列数据 rear=(rear+)%MAXLEN;if(front=rear)printf(队列已满!);elsequeuerear=val;,（2）队头输出数据 OutQueue_front()int OutQueue_front()/从队头输出队列数据 int t;if(front=rear)return-1;t=queue+front;if(fro

41、nt=MAXLEN)front=0;return t;,（3）从队尾输出数据 OutQueue_rear()int OutQueue_rear()/从队尾输出队列数据 int t;if(front=rear)return-1;t=queuerear-;if(rear0,（1）队列是一种运算受限制的线性表，一般队列只允许在队尾进行插入操作，在队头进行删除操作。（2）队列的逻辑结构和线性表也相同，数据元素之间存在一对一的关系，其主要特点是“先进先出”。（3）队列的存储结构也有顺序存储结构和链接存储结构，要求能用C（或C+）语言描述它们的存储结构。（4）重点掌握在顺序队列和链队列上的进队、出队、判队

42、空、判队满、求队列长度和读队头元素等操作。（5）熟悉队列在计算机的软件设计中的应用，能灵活应用队列的基本原理解决一些综合性的应用问题。,小 结,1实验目的(1)掌握队列的特点及其描述方法。(2)用链式结构实现一个队列。(3)掌握队列的各种基本操作。(4)掌握队列的简单应用程序。2.实验内容(1)设计一个字符型的链队列；(2)编写队列的进队、出队、读队头元素、显示队列中全部元素程序；(3)设计一个输入限制性的双队列，要求：输入只能在一端进行，而输出可以选择从队头输出或队尾输出，全部选择完毕后能显示所选择的输出结果。,实验4 队列子系统,(4)设计一个选择式菜单，以菜单方式选择队列的各种基本操作。菜单形式如下：队 列 子 系 统*1-进 队*2-出 队*3-读 队 头 元 素*4-显 示*5-双 队 列*0-退 出*请选择菜单号：,习 题 4,见习题参考答案,返回,