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

实用数据结构基础 第3章 栈 第 3 章 栈 知 识 点 栈的定义和特点 栈的基本运算和算法 栈的典型应用 难 点 后缀表达式的算法 数制的换算 利用本章的基本知识设计相关的应用 问题 要 求 掌握栈的特点 掌握栈的基本运算 熟悉栈的各种实际应用 能设计栈的应用的典型算法 了解栈的运算时间复杂度分析 第3章 目录 31 栈的定义与运算 32 栈的存储和实现 33 栈的应用举例 小 结 实验3 栈子系统 习题3 3-1 栈的定义和运算 311 栈（Stack）的定义 1. 栈的定义 栈是限制在表尾进行插入和删除的线性表 。 a1 a2 a3 进栈出栈 图31栈的 示意图 2. 栈的特性 （1）栈的主要特点是“后进先出” （2）允许插入、删除的这一端称为栈顶（ Top），另一端称为栈底（Bottom）。 3. 应用实例 （1）分币筒； （2）铁路调度站。 312 栈的运算 1进栈： Push（ / datatype可根据用需要定义 类型 int top； / 定义栈顶指针 SeqStack； 再定义一个指向顺序栈的指针： SeqStack *S； / 定义S为结构体类型的指针 变量 （3）栈操作的示意图如图33所示。 A F E D C B A F E D C B A J I H G F E D C B A top=-1 top=0 top=5 top=3 top=9 (a) (b) (c) (d) (e) 当top = 1时，表示栈空，如图33（a）； 当top=0时，表示栈中有一个元素，如图33（b）表 示栈中已输入一个元素A； 入栈时，栈顶指针上移，指针top加1，如图33（c） 是6个元素入栈后的状况； 出栈时，栈顶指针下移，指针top减1， 如图33（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 ）； stop= 1； / 置栈空 return s； （2） 进栈 进栈运算是在栈顶位置插入一个新元素x，其算法步 骤为： (a) 判栈是否为满，若栈满，作溢出处理，并返回0； (b) 若栈未满，栈顶指针top加1； (c) 将新元素x送入栈顶，并返回1。 int Push (SeqStack *s， datatype x) if （stop= =MAXLEN1） return 0； / 栈满不能入栈，且返回 0 else stop+； sdatastop=x； / 栈不满，则压入元素x return 1； / 进栈成功，返回1 （3）出栈 出栈运算是指取出栈顶元素，赋给某一个指定变 量x，其算法步骤为： (a) 判栈是否为空，若栈空，作下溢处理，并返回0 ； (b) 若栈非空，将栈顶元素赋给变量x； (c) 指针top减1，并返回1。 int Pop（SeqStack *s， datatype *x） if (SEmpty ( s ) ) return 0； / 若栈空不能出栈 ，且 返回0 else *x=sdatastop； / 栈不空则栈顶元素存 入*x stop ； return 1； / 出栈成功，返回1 （4）读栈顶元素 datatype ReadTop（SeqStack *s） if (SEmpty ( s ) ) return 0； / 若栈空，则返回0 else return (sdatastop )； / 否则，读栈顶元素，但指针 未移动 （5）判栈空 int SEmpty（SeqStack *s） if （stop= = 1） return 1； / 若栈空，则返回1 else return 0； / 否则返回0 （6）判栈满 int SFull（SeqStack *s） if （stop= =MAXLEN1） return 1；/ 若栈满，则返 回1 else return 0； / 否则返回0 322 链栈 1链栈的实现 用链式存储结构实现的栈称为链栈。因为链栈的结 点结构与单链表的结构相同，通常就用单链表来实现，在此 用LinkStack表示，即有： typedef struct stacknode / 栈的存储结构 datatype data; / 定义数据类型 struct stacknode *next; / 定义一个结构体的链指 针 stacknode;，* Linkstack； Linkstack top； / top为栈顶指针 由于栈中的操作只能在栈顶进行的，所以用 链表的头部做栈顶是最合适的。链栈结构如图34所 示。 图34 链栈示意图 top 4 3 2 1 2链栈基本操作： （1）入栈 void Push(linkstack *s,int x) stacknode *p=new stacknode; / 申请一个新结点 pdata=x; / 数据入栈 pnext=stop; / 修改栈顶指针 stop=p; （2） 出栈 int Pop(linkstack *s) int x; / 定义一个变量x，用以存放出栈 的元素 stacknode *p=stop; / 栈顶指针指向p x=pdata; / 栈顶元素送x stop=pnext; / 修改栈顶指针 delete p; / 回收结点p return x; / 返回栈顶元素 （3） 显示 void ShowStack (linkstack *s) stacknode *p=stop; if (p= =NULL) / 若栈空，作“栈空”显 示 printf (“栈为空“); else printf (“栈元素为：“); while (p!=NULL) /栈非空，则显示栈中所 有元素 printf (“%6d“,pdata); / 输出一个元素 p=pnext; / 修改栈顶指针 printf (“n“); 33. 栈的应用举例 331 数制转换 数值进位制的换算是计算机实现计算和处理 的基本问题。比如将十进制数N转换为j进制的数， 其解决的方法很多，其中一个常用的算法是除j取余 法。将十进制数每次除以j，所得的余数依次入栈， 然后按“后进先出”的次序出栈便得到转换的结果。 其算法原理是： N =（N / j）* j + N % j 其中： / 为整除，%为求余 【例31】将十进制数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，则重复步骤（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; / 申请一个新结点 pnext=s.top; / 修改栈顶指针 s.top=p; s.topdata=x; / 入栈 while(n); printf(“转换后的二进 制数值为：“); while(s.top) / 余数出栈处理 printf(“%d“,s.topdata); / 输出栈顶的余数 stacknode* p=s.top; / 修改栈顶指针 s.top=s.topnext; delete p; / 回收一个结点，C语言中用free p 332 表达式求值 表达式是由运算对象、运算符、括号等组成的有意义的 式子。 1中缀表达式（Infix Notation） 一般我们所用表达式是将运算符号放在两运算对象 的中间，比如：a+b，c/d等等，我们把这样的式子称为中缀 表达式。 2后缀表达式（Postfix Notation） 后缀表达式规定把运算符放在两个运算对象（操作 数）的后面。在后缀表达式中，不存在运算符的优先级问题 ，也不存在任何括号，计算的顺序完全按照运算符出现的先 后次次序进行。 3中缀表达式转换为后缀表达式 其转换方法采用运算符优先算法。转换过程需要两 个栈：一个运算符号栈和一个后缀表达式输出符号栈。 （1）读入操作数，直接送输出符号栈。 （2）读入运算符，压入运算符号栈。 (a) 若后进的运算符优先级高于先进的，则继续进栈； (b) 若后进的运算符优先级不高于先进的，则将运算符号 栈内高于或等于后进运算符级别的运算符依次弹出后，自己进 栈。 （3）括号处理： (a) 遇到开括号“（”，进运算符号栈； (b)遇到闭括号“）”，则把最靠近的开括号“（”，以及其 后进栈的运算符依次弹出到输出符号栈（括号均不压入输出符 号栈）。 （4）遇到结束符“#”，则把运算符号栈内的所有运算符号 依次弹出，并压入输出符号栈。 （5）若输入为+、单目运算符，改为0与运算对象在前， 运算符在后。 例如：A，转换为：0A。 【例3-2】A / B C + D * EA*C 输输入符号运算符栈栈输输出结结果操作说说明 A A输输出A / A/ 进进栈栈 B/ A,B输输出B /, A,B优优先级级高于/，继续进继续进 栈栈 C/, A,B,C输输出C + A,B,C, ,/，/依次弹弹出 D+ A,B,C, ,/,D输输出D *+,* A,B,C, ,/,D*优优先级级高于+，继续进继续进 栈栈 E+,* A,B,C, ,/,D,E输输出E A,B,C, ,/,D,E,*,+*，+ 依次弹弹出， 进栈进栈 A A,B,C, ,/,D,E,*,+,A输输出A *,* A,B,C, ,/,D,E,*,+,A*优优先级级高于 ，继续进继续进 栈栈 C,* A,B,C, ,/,D,E,*,+,A,C输输出C # A,B,C, ,/,D,E,*,+,A,C,*, 遇到结结束符#，依次弹弹出*， 【例3-3】3 + 4 /（25（6 + 15）* 8 输输入符号运算符栈栈 输输出结结果操作说说明 33输输出3 +3+进栈进栈 4+3,4输输出4 /+,/3,4/ 继续进栈继续进栈 (+,/,(3,4（进栈进栈 25+,/,(3,4,25输输出25 +,/,(,3,4,25 进栈进栈 (+,/,(,(3,4,25（再进栈进栈 6+,/,(,(3,4,25,6输输出6 +,/,(,(,+3,4,25,6+进栈进栈 15+,/,(,(,+3,4,25,6,15输输出15 )+,/,(,3,4,25,6,15,+ 遇），依次弹弹出第2个（后的符号 )+,/3,4,25,6,15,+, 遇），依次弹弹出第1个（后的符号 *+,*3,4,25,6,15,+,/弹弹出/，但*高于+，继续进栈继续进栈 8+.*3,4,25,6,15,+,/,8输输出8 #3,4,25,6,15,+,/,8,*,+遇到结结束符#，依次弹弹出*，+ 得到后缀表达式为：3 4 25 6 15 + / 8 * + 4后缀表达式求值 后缀表达式求值的运算要用到一个数栈stack和一个 存放后缀表达式的字符型数组exp。其实现过程就是从头至 尾扫描数组中的后缀表达式： （1）当遇到运算对象时，就把它插入到数栈stack中； （2）当遇到运算符时，就执行两次出栈的操作，对出 栈的数进行该运算符指定的运算，并把计算的结果压入到数 栈stack。把它插入到数栈stack中； （3）重复（1）、（2），直至扫描到表达式的终止符 “#”，在数栈的栈顶得到表达式的值。 以例【例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函数返回地址压入栈中；在子函数a()中调用子函数b() 时，又将b函数返回地址压人栈中；同样，在子函数b()中 调用子函数c()时，又将c函数返回地址压人栈中。其调用 返回地址进栈示意图如图3-5所示。 图35 无参函数嵌套调用返回地址进栈示意图 当执行完子函数c()以后，就从栈顶弹出c()函数返回 地址，回到子函数b()；子函数b()执行完毕返回时，又从栈 顶弹出b函数返回地址，回到子函数a()；子函数a()返回时， 再在栈顶弹出a函数返回地址，回到主函数，继续执行主函 数程序。无参函数嵌调用返回示意图如图3-6所示。 c函数返回地址 b函数返回地址 a函数返回地址 返回地址栈 ： 图36 无参函数嵌套调用返回示意图 3-3-4 递归调用 1递归 一个直接调用自己，或者通过一系列调用语句间接 地调用自己的函数称为递归函数。在程序设计中，有许多 实际问题是递归定义的，使用递归的方法编写程序将使许 多复杂的问题大大简化。所以，递归是程序设计中的一个 强有力的工具。 2典型例子 （1）2阶斐波那契（Fibonacci）数列 0 n=0 1 n=1 Fib( n1 )+Fib( n2 ) 其它情况 Fib(n)= （2）阶乘函数 n!的定义为： Fac(n)= 1 n=0 / 递归终止条件 n*Fac (n1) n0 / 递归步骤 根据定义不难写出相应的递归函数： int fac ( int n ) if (n= =0) return 1 ； else return (n* fac (n1) )； 3-3-5 中断处理和现场保护 1.中断处理（Interrupt Processing） 在C+语言中，系统调用是通过中断来进行，中 断调用示意图如图38所示。 图38 中断调用示意图如 如果把中断处理想象成函数调用，则中断处理程序 可以看成被调用的函数。 2. 现场保护和恢复 执行中断时，微处理机有时必须对状态寄存器，累 加器，以及相关的寄存器对进行现场保护（压栈）；中断处 理完毕，则必须按后进先出的原则恢复现场（出栈）。下面 ，我们以汇编语言来说明现场保护和恢复的原理： ；接受中断处理 PUSH AX ；保护现场 PUSH BX PUSH CX PUSH BP PUSHF ；F状态寄存器进栈 ；中断处理 POPF ；恢复现场，后进栈的先出栈 POP BP POP CX POP BX POP AX （1）栈是一种运算受限制的线性表，它只允许在 栈顶进行插入和删除等操作。 （2）栈的逻辑结构和线性表相同，数据元素之间 存在一对一的关系，其主要特点是“后进先出”。 （3）栈的存储结构有顺序栈和链栈之分，要求掌 握栈的C语言描述方法。 （4）重点掌握在顺序栈和链栈上实现：进栈、出 栈、读栈顶元素、判栈空和判栈满等基本操作。 （5） 熟悉栈在计算机的软件设计中的各种应用， 能灵活应用栈的基本原理解决一些综合性的应用问题。 小 结 实验实验 3 3 栈子系统栈子系统 1实验目的 （1） 掌握栈的特点及其描述方法。 （2） 用链式存储结构实现一个栈。 （3） 掌握建栈的各种等基本操作。 （4）掌握栈的几个典型应用的算法。 2. 实验内容 （1）设计一个字符型的链栈； （2）编写进栈、出栈、显示栈中全部元素的程序； （3）编写一个把十进制整数转换成二进制数的应用程序 ； （4）编写一个把中缀表达式转换成后缀表达式（逆波兰 式）的应用程序； （5）设计一个选择式菜单，以菜单方式选择上述操作。 栈 子 系 统 * * 1-进 栈 * * 2-出 栈 * * 3-显 示 * * 4-数制转换 * * 5-逆波兰式 * * 0-返 回 * * 请选择菜单号： *教材p64第3行void Stack() ，在作为子系统上机时上 机时改为：void main() 习题3 参考习题解答 返回 实用数据结构基础 第4章 队列 第4章 队列 知 识 点 队列的定义和特点 队列的存储实现及运算实现 队列的应用举例 难 点 循环队列的特点及判断溢出的条件 利用队列的特点设计相关的应用问题 要 求 熟练掌握以下内容： 队列的特点和基本运算 循环队列的特征和基本运算 了解以下内容： 队列运算的时间复杂性分析 队列的实际应用 第 4 章 目录 41 队列的定义和基本运算 42 队列的存储及运算的实现 43 队列的应用举例 小 结 实验4 队列子系统 习题4 41 队列的定义和基本运算 411 队列（Queue）的定义 1队列的定义 设有n个元素的队列Q=（a1，a2，a3，an），则 称a1为队首元素，an为队尾元素。队列中的元素按，a1，a2， a3，an1 ，an的次序进队，按a 1，a2，a3，an1 ，an 次序出队，即队列的操作是按照“先进先出” 的原则进行的。 2. 队列的特性 （1）队列的主要特性是“先进先出”。 （2）队列是限制在两端进行插入和删除操作的线性表 。 能够插入元素的一端称为 队尾（Rear），允许删除 元素的一端称为 队首（Front）。 图41 队列示意图 a1 a2 a3 a4 a5 an 入队出队 4. 队列的实例 （1）如车站排队买票或自动取款机排队取款。 （2）在计算机处理文件打印时，为了解决高速的CPU与低 速的打印机之间的矛盾，对于多个请求打印文件，操作系统 把它们当作可以被延迟的任务，提出打印任务的先后顺序， 就是它们实际打印的先后顺序。即按照“先进先出”的原则形 成打印队列。 412 队列的基本运算 （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） 初始条件： 队q存在。 操作结果： 若队满则返回为0，否则返回为1。 （7）求队列长度Qlen（q） 初始条件： 队列q存在。 操作结果： 返回队列的长度。 4242 队列的存储实现及运算实现队列的存储实现及运算实现 421 顺序队列 1顺序队列 顺序队列是用内存中一组连续的存储单元顺序存放队列 中各元素。所以可以用一维数组QMAXLEN作为队列的 顺序存储空间，其中MAXLEN为队列的容量，队列元素从 Q0单元开始存放，直到QMAXLEN1单元。因为队头 和队尾都是活动的，因此，除了队列的数据以外，一般还 设有队首（front）和队尾（rear）两个指针。 顺序队可以用C+语言定义： #define MAXLEN 10 / 队列的最大容量 typedef struct datatype QMAXLEN； / datatype 可根据用户需要定义 int front= 1, rear= 1； / 定义队头、队尾指针，并置队列为空 Queue； Queue *p； / 定义一个指向队的指针变量 p=new Queue； / 申请一个顺序队的存储空间 / 在C中用p = malloc（sizeof（Queue） ） 设： 队头指针：pfront 指向队头元素前面一个位置 队尾指针：prear 指向队尾元素。 （1）判队空 当pfront = prear= 1时表示队空。如图42（a） （2）入队 在无溢出的情况下，队尾指针加1，新元素即可入队： prear+； / 先将队尾指针加1 pQprear=x； / 入队 （3）出队。 在队列非空的情况下允许出队，出队时队头指针加1， 队头元素即可输出： pfront+； x=pQpfront； / 队头元素送x （4）队列的长度： m= (prear)(pfront)； （5）判队满： m= MAXLEN； 判队空： m=0 。 E D C B A H G F J I H G F Rear=-1 front=-1 (a) rear=4 rear=7 rear=9 front=-1 front=4 front=4 (b) (c) (d) 图42 从示意图中可以看到，随着入队、出队操作的进行，整 个队列会整体向后移动，这样就出现了图4-2（d）中的现象 ：队尾指针虽然已经移到了最后，而队列却未真满的“假溢 出”现象，使得队列的空间没有得到有效的利用。 2循环队列 为了解决上述队列的“假溢出”现象，要做移动操作，当 移动数据较多时将会影响队列的操作速度。一个更有效的方 法是将队列的数据区Q0 MAXLEN-1看成是首尾相连的环 ，即将表示队首的元素Q0与表示队尾的元素QMAXLEN1 连接起来，形成一个环形表，这就成了循环队列，如图4-3 所示。 图43 循环队列示意图 MAXLEN-1 图4-4是假设长度为10的循环队列操作示意图。 因为是头尾相接的循环结构，所以将入队时的队尾指针 加1操作修改为： p-rear= (p-rear+1) % MAXLEN； 将出队时的队头指针加1操作修改为： p-front= (p-front+1) % MAXLEN； 在图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）在定义结构体时，附设一个存储循环队列中元素个 数的变量n，当n= =0时表示队空； 当n= =MAXLEN时为队满。 循环队列的结构体类型定义如下： typedef struct datatype dataMAXLEN； / 定义数据的类型及数据的存储区 int front，rear； / 定义队头、队尾指针 int n； / 用以记录循环队列中元素的个数 csequeue； / 循环队列变量名 3. 循环队列的基本运算 （1）置空队 csequeue* IniQueue ( ) q=new csequeue ; / 在c语言中用malloc (sizeof (csequeue) ) qfront=qrear=MAXLEN1 ； qn=0； return q； （2）入队 int 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； / 出队完成，返回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 链队列的入队、出队 (a) a1 a1 a2 a1 a2 front front front front rear rear rear rear (b) (c) (d) 图4-5中头指针front和尾指针rear是两个独立的指针变 量，从结构性上考虑，有时也两个指针封装在一个结构中 。 2链队的描述： typedef struct queuenode datatype data; / datatype为特定的类型，根据具体情况可以是char或int等 struct queuenode *next; queuenode; / 链队结点的类型datatype typedef struct queuenode *front,*rear; linkqueue; / 将头指针、尾指针封装在一起的链队 3头指针和尾指针封装在一个结构中的链队列 如图4-6所示为头指针和尾指针封装在一个结构 中的链队列。 图46 链队列示意图 front rear p A B J 4链队的基本运算： （1）入队（进队） void InQueue (linkqueue *q) / 进队函数 int x; / 定义入队元素类型 queuenode *p=new queuenode; / 申请一个新结点 p-data=x; / 输入元素 p-next=NULL; / 修改指针 if (q-front= =NULL) q-front=p; else q-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; / 回收结点 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“); 队列是一种应用广泛的数据结构，凡具有“先进先出”需要 排队处理的问题，都可以使用队列来解决。 1. 队列在输入、输出管理中的应用 在计算机进行数据输入、输出处理时，由于外部设备的速 度远远低于CPU数据处理的速度，此时可以设定一个“队列缓冲 区”进行缓冲。当计算机要输出数据时，将计算机的数据按块 （例如每块512B）逐个添加到“队列缓冲区”的尾端，而外部设 备则按照其输出速度从队首逐个取出数据块输出。这样，虽然 输出数据速度较慢，但却能保证与计算机输出的数据有完全相 同的次序，而不致发生输出次序的混乱或数据的丢失。 4343 队列应用举例队列应用举例 2.对CPU的分配管理 一般的计算机系统只有一个CPU，如果在系统中有多个 进程都满足运行条件，这就可以用一个就绪队列来进行管 理。当某个进程需要运行时，它的进程名就被插入到就绪 队列的尾端。如果此队列是空的，CPU就立即执行该进程； 如果此队列非空，则该进程就需要排在队列的尾端进行等 待。CPU总是首先执行排在队首的进程，一个进程分配的一 段时间执行完了，又将它插入到队尾等待，CPU转而为下一 个出现在队首的进程服务。如此，按“先进先出”的原则 一直进行下去，直到执行完的进程从队列中逐个删除掉。 3优先队列（Priority Queue） 在实际应用中，有时往往需要根据任务的优先级别来决 定先做那些最重要的事情，此时必须对这种“先进先出”的规 则进行适当的修改。 假设每个元素都有一个相当于权的数据项，那么我们就 可以根据权值的大小来决定元素出队的顺序。也就是说，在 队列中哪一个优先级最高，那一个就优先出队。这种按优先 级高低来决定出队顺序的队列，称为优先队列。 优先队列的一个典型的应用就是批处理操作系统中的作 业处理。每个作业都有一个优先级，系统在处理文件的时候 ，并不是根据一般队列的“先进先出”原则，而是根据文件优 先级的高低来选择处理对象。 在优先队列中的每一个元素都有一个被称为权的数据 项，权的大小决定了元素的优先级。实现优先队列有两种方 法： （1）按权的大小进行插入，使整个队列始终保持按优先级 次序排列的状态，而删除操作则和普通队列一样，只删除队 首元素。 （2）插入操作和普通队列一样，只在队尾进行插入，而删 除操