1、2023年11月28日1第第3章章 栈和队列栈和队列 本章学习内容本章学习内容3.1 栈 3.2 队列 2023年11月28日23.1 栈栈 3.1.1 栈的定义 栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定的一端，称为栈底（Bottom）。根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。在如图3-1所示的栈中，元素以 a1，a2，a3，an的顺序进入栈中，而出来则以an，an-1，a2，a1的顺序
2、。也就是说，栈是一种后进先出（Last In First Out）的线性表，简称为LIFO表。栈在日常生活中随处可见，如仓库货物的存放，先从底层往上面堆，再从上往下拿，是一典型的栈。而乘客乘车（假设只有一个车门在前面），上车的人按从后往前的顺序坐，下车时则按从前往后的顺序下来，也是一种典型的栈。2023年11月28日33.1.2 栈的运算1初始化栈：inistack(&s)将栈s置为一个空栈（不含任何元素）。2进栈：push(&s,x)将元素x插入到栈s中，也称为“入栈”、“插入”、“压入”。3出栈：pop(&s)删除栈s中的栈顶元素，也称为“退栈”、“删除”、“弹出”。4取栈顶元素：gett
3、op(s)取栈s中的栈顶元素。5判栈空：empty(s)判断栈s是否为空，若为空，返回值为true或1，否则返回值为false或0。2023年11月28日43.1.3 栈的抽象数据类型描述栈的抽象数据类型可描述为：栈的抽象数据类型可描述为：ADT Stack isData：含有n个元素a1,a2,a3,an，按LIFO规则存放，每个元素的类型都为elemtype。operation：void inistack(&s)/将栈s置为一个空栈（不含任何元素）void push(&s,x)/将元素x插入到栈s中，也称为“入栈”、“插入”、“压入”void pop(&s)/删除栈s中的栈顶元素，也称为“
4、退栈”、“删除”、“弹出”elemtype gettop(s)/取栈s中的栈顶元素int empty(s)/判断栈s是否为空，若为空，返回值为true或1，否则返回值为false或0End stack2023年11月28日53.1.4 顺序栈 1顺序栈的数据类型栈的顺序存储结构，也称为顺序栈，与顺序表的数据类型描述类似，描述如下：CONST int maxsize=maxlen;/定义栈的最大容量为maxlen class seqstack public:elemtype stackmaxsize;/将栈中元素定义为elemtype类型 int top;/指向栈顶位置的指针void inist
5、ack(&s);/将栈s置为一个空栈（不含任何元素）void push(&s,elemtype x);/将元素x插入到栈s中，也称为“入栈”、“插入”、“压入”void pop(&s);/删除栈s中的栈顶元素，也称为“退栈”、“删除”、“弹出”elemtype gettop(s);/取栈s中栈的顶元素bool empty(s);/判栈s是否为空;2023年11月28日62栈的五种运算栈的五种运算实现过程如下：（规定栈中空间为1maxsize-1，浪费存储位置，是为了与线性表数组存储对应）。（1）初始化栈void seqstack:inistack(seqstack&s)s.top=0;（2）进
6、栈void seqstack:push(seqstack&s,elemtype x)if(s.top=maxsize-1)coutoverflow;else s.top+;s.stacks.top=x;2023年11月28日7（3）退栈void seqstack:pop(seqstack&s)if (s.top=0)coutunderflow;else s.top-;（4）取栈顶元素 elemtype seqstack:gettop(seqstack s)if (s.top=0)coutunderflow;return 0;else return s.stacks.top;（5）判栈空否 bo
7、ol seqstack:empty(seqstack s)if(s.top=0)return true;else return false;2023年11月28日83栈的共享存储单元有时，一个程序设计中，需要使用多个同一类型的栈，这时，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。下面以两个栈为例来说明栈共享存储空间(见下图)栈 1 顶栈 2 顶栈 1 底栈 2 底设两个栈共享一段内存单元（一维数组），两个栈的栈底分别设在一维数组
8、的两端，这时，若第一个栈发生溢出，而且第二个栈中还有多余空间，则可将第一个栈进栈元素放入第二个栈；反之，若第二个栈发生溢出，而第一个栈中还有多余空间，则可将第二个栈进栈元素放入第一个栈中。这样就可以实现两个栈的优势互补，只有当两个栈的栈顶相遇时，这时进栈才会发生溢出，比两个栈单独使用进栈发生溢出的可能性小得多。2023年11月28日9两个栈共享存储单元可用如下C+语句描述：CONST int maxsize=maxlen;/maxlen为共享单元的最大长度class dbseqstack public:elemtype stackmaxsize;int top2;/两个栈的栈顶指针void d
9、binistack(dbseqstack&s,int k);/将第k个栈置为一个空栈（不含任何元素）void dbpush(dbseqstack&s,elemtype x,int k);/将元素x插入到第k个栈中void dbpop(dbseqstack&s,int k);/删除第k个栈中的栈顶元素elemtype dbgettop(dbseqstack s,int k);/取第k个栈中的栈顶元素bool dbempty(dbseqstack s,int k);/判第k个栈是否为空 ;2023年11月28日10对于上述形式的栈共享存储单元，栈的五种运算可类似描述，现仅描述进栈、退栈算法。（1）
10、两个栈共享存储单元的进栈算法void dbseqstack:dbpush(dbseqstack&s,elemtype x,int k)/将元素x压入到第k个栈中if(s.top0+1=s.top1)coutoverflow;else if(k=0)s.top0+;s.stacks.top0=x;else s.top1-;s.stacks.top1=x;（2）两个栈共享存储单元的退栈算法void dbseqstack:dbpop(dbseqstack&s,int k)/应以s为栈空间的栈中，对第k个栈进行退栈if (k=0)&(s.top0=0)coutunderflow;else if(k=1
11、)&(s.top1=maxsize)coutnext=NULL;（2）进栈运算void link:push(link*top,int x)link*s;s=new link;s-data=x;s-next=top-next;top-next=s;2023年11月28日13（3）退栈运算 void link:pop(link*top)link*s;s=top-next;if(s!=NULL)top-next=s-next;delete(s);（4）取栈顶元素elemtype link:gettop(link*top)if(top-next!=NULL)return top-next-data;e
12、lse return NULL;2023年11月28日14（5）判栈空bool link:empty(link*top)if(top-next=NULL)return(true);else return(false);从上述算法可知，它们的时间复杂度都为O(1)。3.1.6 栈的应用栈在日常生活中和计算机的程序设计中，有着许多重要的应用。下面仅介绍栈在计算机中的一些应用。2023年11月28日151算术表达式的求值算术表达式中包含了算术运算符和算术量（常量、变量、函数），而运算符之间又存在着优先级的问题，不能简单地进行从左到右（C+中，有的运算是从右到左的）的运算，而必须先计算优先级高的。编译
13、程序在求值时，不能简单从左到右运算（或从右到左运算），必须先算运算级别高的，再算运算级别低的，同一级运算才按从左到右的顺序（或从右到左运算）。因此，要实现表达式求值，必须设置两个栈，一个栈存放运算符，另一个栈存放操作数（算术量），在进行表达式求值时，编译程序从左到右扫描，每遇到一个操作数，一律进入操作数栈，每遇到一个运算符，则应与运算符栈的栈顶进行比较，若运算符优先级高于栈顶的优先级，则进栈，否则在运算符栈中退栈，退栈后，在操作数栈中退出两个元素（先退出的数放在退出运算符右边，后退出的数放在退出运算符左边），然后用运算符栈中退出的栈顶元素进行运算，运算的结果存入操作数栈中，直到扫描完毕。这时运
14、算符栈为空，操作数栈中只有一个元素，即为运算的结果。2023年11月28日16【例1】用栈求1+2*3-4/2的值，栈的变化见表3-1。从表3-1可知，最后求出的表达式的值为5。当然，算术表达式除了简单求值外，还会涉及算术表达式的两种表示方法，即中缀表示法和后缀表示法。刚才的例1中的表达式就是中缀表达式，中缀表达式求值比较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号，需要用到两个栈），而后缀表达式求值比较方便（无须考虑运算符的优先级及圆括号，仅按从左到右的顺序进行即可，仅用到一个栈）。2023年11月28日17步骤操作数栈运算符栈说明开始 开始时，两个栈为空 1 1扫描到“1”，进入操作数栈
15、 2 1+扫描到“+”，进入运算符栈 3 1 2 +扫描到“2”，进入操作数栈 4 1 2+*扫描到“*”，进入运算符栈 5 1 2 3+*扫描到“3”，进入操作数栈 6 1+扫描到“-”，退栈 7 1 6+2*3=6 进栈 8 扫描到“-”，退栈 9 7 1+6=7进栈10 7-扫描到“-”，进入运算符栈11 7 4 -扫描到“4”，进入操作数栈12 7 4 -扫描到“/”，进入运算符栈13 7 4 2 -扫描到“2”，进入操作数栈14 7 -扫描完，“/”“4”“2”退栈15 7 2 -4/2=2 进栈16“-”“7”“2”退栈17 57-2=5 进栈表3-1 表达式求值栈演示图2023年
16、11月28日18从前面的例题可以看出，中缀表达式求值比较麻烦，需用两个栈来实现，并且如果出现圆括号时，运算还要复杂些。那么，能否把中缀表达式转换成另一种形式的算术表达式，使计算简单化呢？回答是肯定的。波兰科学家卢卡谢维奇（Lukasiewicz）很早就提出了算术表达式的另一种表示，即后缀表达式，也称为逆波兰式，其定义规则是把运算符放在两个操作数后面。在后缀表达式中，不存在括号，也不存在运算符优先级问题，计算过程完全按照运算符出现的先后次序进行，比中缀表达式的求值要简单得多。2023年11月28日19例如，对于下列各中缀表达式：（1）3/5+8（2）18-9*(4+3)（3）(25+x)*(a*
17、(a+b)+b)上面三个中缀表达式对应的后缀表达式为：（1）3 5 /8 +（2）18 9 4 3 +*-（3）25 x +a a b +*b +*2023年11月28日202中缀表达式变成等价的后缀表达式中缀表达式变成等价的后缀表达式将中缀表达式变成等价的后缀表达式，表达式中操作数的相对次序不发生变化，运算符相对次序将会发生变化，同时去掉了表达式中的圆括号。转换规则是：设立一个堆栈，用来存放表达式中的运算符。首先设栈为空，编译程序从左到右扫描中缀表达式，每次遇到操作数，直接将其输出，并接着输出一个空格作为两个操作数的分隔符；若遇到一个运算符，则必须与栈顶的运算符优先级比较，若运算符级别比栈顶
18、运算符级别高，则进栈，否则退出栈顶元素，并直接输出，然后输出一个空格作为分隔符；若扫描时遇到左括号，进栈；若扫描时遇到右括号，则一直退栈输出，直到退到左括号止。当栈已经变成空时，输出的结果即为所求的后缀表达式。【例2】将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果见表3-2。2023年11月28日21步骤栈中元素输出结果说明1(（进栈2(1输出13(+1+进栈4(+1 2输出251 2 +退栈并输出，退栈到（止6*1 2 +*进栈7*(1 2 +（进栈8*(1 2 +（进栈9*(1 2 +8输出810*(-1 2 +8 -进栈11*
19、(-1 2 +8 2输出212*(1 2 +8 2 -退栈并输出，退栈到（止13*(/1 2 +8 2 -/进栈14*(/(1 2 +8 2 -（进栈15*(/(1 2 +8 2 -7输出716*(/(-1 2 +8 2 -7-进栈17*(/(-1 2 +8 2 -7 4输出418*(/1 2 +8 2 -7 4 -退栈并输出，退栈到（止19*1 2 +8 2 -7 4 -/退栈并输出，退栈到（止201 2 +8 2 -7 4 -/*退栈并输出表3-2 中缀表达式转换成后缀表达式示意图2023年11月28日22从表3-2可知，中缀表达式(1+2)*(8-2)/(7-4)变成的后缀表达式为：1
20、2 +8 2 -7 4 -/*3后缀表达式的求值后缀表达式的求值将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符的左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。【例3】求上例中转换得到的后缀表达式1 2 +8 2 -7 4 -/*之值。该求值过程可用一个栈来描述，栈中最后的结果即为后缀表达式的值（应该与用中缀表达式求出的结
21、果相同），具体见表3-3。从表3-3可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀表达式求值要简单得多。2023年11月28日23表3-3 后缀表达式求值示意图步骤栈中元素说明111进栈21 22进栈3遇+号退栈2和1431+2=3的结果3进栈53 88进栈63 8 22进栈73遇-号退栈2和883 68-2=6的结果6进栈93 6 77进栈103 6 7 44进栈113 6遇-号退栈4和7123 6 37-4=3的结果3进栈133遇/号退栈3和6143 26/3=2的结果2进栈15遇*号退栈2和31663*2=6进栈176扫描完毕，运算结束2023年11月28日24
22、4函数的嵌套调用在函数嵌套调用中，一个函数的执行没有结束，又开始另一个函数的执行，因此必须用栈来保存函数中断的地址，以便调用返回时能从断点继续往下执行。【例4】设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见下图），其中r，s，t分别表示中断地址。主函数 a 函数 b 函数 c 函数r s t2023年11月28日25在上图中，主程序调用函数a，留下一个断点地址r进栈，然后主函数处于挂起状态，进入函数a中执行，函数a中再调用函数b，留下一个断点地址s进栈，然后函数a处于挂起状态，进入函数b中执行，函数b中调用函数c，留下一个断点地址t进栈，然后函数b处于挂起状态，进入
23、函数c中执行，函数c执行完后，要返回断点处继续执行，但返回到哪一个断点呢?根据栈顶元素来决定。返回时，执行退栈操作，先退出t，故返回t断点继续执行，接着退栈退出s，故返回s断点继续执行，接着退栈退出r，返回r断点继续执行，最后栈为空，算法结束。我们可以用一个栈来描述调用情况（见下图的(a)(f)）。2023年11月28日26 s r t s r r （a）调用a函数，r进栈 （b）调用b函数，s进栈 （c）调用c函数，t进栈 r s r（d）返回b函数，t退栈 （e）返回a函数，s退栈 （f）返回主程序，r退栈2023年11月28日275函数的递归调用函数的递归调用函数的递归调用也是一种嵌套，
24、故也必须用栈来保存断点信息，但递归调用相当于同一个函数的嵌套调用，故除了保存断点信息外，还必须保存每一层的参数、局部变量等。【例5】求n!可用递归函数描述如下：1n=0 n!n*(n-1)!n0可以用一个栈来描述求解过程（设n=4，栈变化情形见下图）。开始时，栈为空，见下图（a），接着栈中保存4和3！，见下图（b），再接着调用3！，栈中保存3和2！，见下图（c），接着调用2！，栈中保存2和1！，见下图（d），接着调用1！，栈中保存1和0!，见下图（e），接着调用0！，而0！值已知为1，故返回，1和0！退栈，见下图（f），同时得到1！（1*0!=1）值为1，然后，2和1！退栈，见下图（g），同时
25、得到2！（2*1!=2）值为2，然后，3和2！退栈，见下图（h），同时得到3！（3*2!=6）值为6，然后4和3！退栈，见下图（i），同时得到4！（4*3!=24）值为24，这时，栈已经为空，算法结束，故最后得到的结果为24，即4！=24。2023年11月28日28 4*3!3*2!4*3!2*1!3*2!4*3!1*0!2*1!3*2!4*3!（a）（b）（c）（d）（e）1*12*1!3*2!4*3!2*13*2!4*3!3*24*3!4*6（f）（g）（h）（i）2023年11月28日293.2 队列队列3.2.1 队列的定义仅允许在一端进行插入，另一端进行删除的线性表，称为队列（que
26、ue）。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列的含义与我们日常生活中的多种排队现象相类似，后来的人只能排在队尾（插入），先来排队的人，可以先办完事先离开（删除）。因此，队列是一种先进先出（First In First Out）的特殊线性表，或称FIFO表。若队列中没有任何元素，则称为空队列，否则称为非空队列。队列的描述如下图所示。a1 a2 .an 入 队 队 头 队 尾 出 队 2023年11月28日303.2.2 队列的基本运算队列可定义如下五种基本运算：1初始化队列INIQUEUE(&Q)将队列Q设置成一个空队列。2入队列ENQUEUE(&Q,X)
27、将元素X插入到队尾中，也称“进队”，“插入”。3出队列DLQUEUE(&Q)将队列Q的队头元素删除，也称“退队”、“删除”。4取队头元素GETHEAD(Q)得到队列Q的队头元素之值。2023年11月28日315判队空EMPTY(Q)判断队列Q是否为空，若为空返回1，否则返回0。3.2.3 队列的抽象数据类型描述队列的抽象数据类型描述队列的抽象数据类型可描述为：ADT QUEUE ISData：含有n个元素a1,a2,a3,an，按FIFO规则存放，每个元素的类型为elemtype。Operation：void INIQUEUE(&Q)/将队列Q设置成一个空队列void ENQUEUE(&Q,X
28、)/将元素X插入到队尾中，也称“进队”，“插入”void DLQUEUE(&Q)/将队列Q的队头元素删除，也称“退队”、“删除”elemtype GETHEAD(Q)/得到队列Q的队头元素之值int EMPTY(Q)/判断队列Q是否为空，若为空返回1，否则返回0End queue2023年11月28日323.2.4 循环队列循环队列1队列的顺序存储数据类型描述CONST int maxsize=maxlen;/定义队列的最大容量为maxlenclass seqqueuepublic:elemtype queuemaxsize;/将队列中元素定为数组型，元素类型为elemtypeint fron
29、t;/队头指针int rear;/队尾指针void INIQUEUE(&Q)/将队列Q设置成一个空队列void ENQUEUE(&Q,X)/将元素X插入到队尾中，也称“进队”，“插入”void DLQUEUE(&Q)/将队列Q的队头元素删除，也称“退队”、“删除”Elemtype GETHEAD(Q)/得到队列Q的队头元素之值bool EMPTY(Q)/判断队列Q是否为空，若为空返回真，否则返回假;2023年11月28日332顺序队列顺序队列将队列中元素全部存入一个一维数组中，数组的低下标一端为队头，高下标一端为队尾，将这样的队列看成是顺序队列。在顺序队列中，队列的存储空间为从queue0到q
30、ueuemaxsize-1，则判断队列为空的条件为front=rear=-1，若有一个元素进队，则rear的值增1，若有一个元素出队，则front的值增1。为了与我们的日常规定相符，建议顺序队列的存储空间为从queue1到queuemaxsize，此时队列为空的条件变成front=rear=0。虽然浪费一个存储单元queue0，但可以给我们的操作带来方便。设一个顺序队列为(a1,a2,a3,a4,a5)，对应的存储结构见下图（a），此时front=0,rear=5，若有一个元素a6进队，见下图（b），此时front=0,rear=6，若有连续三个元素a1,a2,a3出队，见下图（c），此时fr
31、ont=3,rear=6，若所有元素都出队，见下图（d），此时front=6,rear=6，队列也变为空，即有front=rear时，队列为空。因此，队列为空的条件是front=rear。2023年11月28日34 a1 a2 a3 a4 a5 front rear （a）a1,a2,a3,a4,a5进队后的顺序队列 a1 a2 a3 a4 a5 a6front rear（b）a1,a2,a3,a4,a5,a6进队后的顺序队列 a4 a5 a6 front rear（c）a1,a2,a3出队后的顺序队列 front rear（d）元素全部出队后的顺序队列2023年11月28日35若一维数组中所
32、有位置都被元素装满，称为队满，即尾指针rear指向一维数组最后，而头指针指向一维数组开头，称为队满。但有可能出现这样的情况，尾指针指向一维数组最后，但前面有很多元素已经出队，即空出很多位置，这时要插入元素，仍然会发生溢出。例如，在上图（d）中，若队列的最大容量maxsize=9，此时，front=rear=6，若再有元素a7，a8，a9进队，front=6，rear=9，这时，若有元素a10进队，将发生溢出。我们将这种溢出称为“假溢出”，因为front的前面有6个空位置，还能装6个元素。要克服“假溢出”，可以将整个队列中的元素向前移动，直到头指针front为零，或者每次出队时，都将队列中的元素
33、前移一个位置。因此，顺序队列的队满判定条件为rear=maxsize。但是，在顺序队列中，这些克服“假溢出”的方法都会引起大量元素的移动，花费大量的时间，所以在实际应用中很少采用，一般采用下面的循环队列形式。2023年11月28日363循环队列循环队列 队头队尾an-1a3a2a1anai为了克服顺序队列中假溢出，通常将一维数组queue0到qmaxsize-1看成是一个首尾相接的圆环，即queue0与queuemaxsize-1相接在一起。将这种形式的顺序队列称为循环队列，见下图。2023年11月28日37这时，可以不必浪费存储单元queue0，但是，必须规定头指针front指向的是队头前一
34、位置，尾指针rear指向当前队尾。在循环队列中，若front=rear,则称为队空，若(rear+1)%maxsize=front，则称为队满，这时，循环队列中能装入的元素个数为maxsize-1，即浪费一个存储单元，但是这样可以给操作带来较大方便。4循环队列上五种运算的实现循环队列上五种运算的实现（1）队列初始化 void seqqueue:INIQUEUE(seqqueue&Q)Q.front=Q.rear=maxsize-1;2023年11月28日38（2）进队列void seqqueue:ENQUEUE(seqqueue&Q,elemtype x)if(Q.rear+1)%maxsiz
35、e=Q.front)coutoverflow;else Q.rear=(Q.rear+1)%maxsize;Q.queueQ.rear=x;（3）出队列void seqqueue:DLQUEUE(seqqueue&Q)if(Q.rear=Q.front)coutunderflow;else Q.front=(Q.front+1)%maxsize;2023年11月28日39（4）取队头元素（注意得到的应为头指针后面一个位置值）elemtype seqqueue:GETHEAD(seqqueue Q)if (Q.rear=Q.front)coutnext=NULL;s.front=p;s.rear
36、=p;（2）入队列void linkqueue:enqueue(linkqueue&s,elemtype x)link *p;p=new link;p-data=x;p-next=s.rear-next;s.rear-next=p;s.rear=p;2023年11月28日43（3）判队空bool linkqueue:empty(linkqueue s)if(s.front=s.rear)return true;else return false;（4）取队头元素elemtype linkqueue:gethead(linkqueue s)if(s.front=s.rear)return NUL
37、L;else return s.front-next-data;2023年11月28日44（5）出队列void linkqueue:dlqueue(linkqueue&s)link*p;p=s.front-next;if(p-next=NULL)s.front-next=NULL;s.front=s.rear;else s.front-next=p-next;delete p;从上述出队列算法可知，若链队列中只有一个元素，需作特殊处理（用if语句判断），修改队尾指针。为了避免修改队尾指针，我们可以采用一种改进的出队列算法。其基本思想是：出队列时，修改头指针，删除头结点而非队头结点，这时，队头结
38、点成为新的头结点，队列中第二个结点成为队头结点。这时，不管队列中有多少个元素，都不需要作特殊处理（不需用if语句来判断），这种改进的算法如下：2023年11月28日45void linkqueue:dlqueue(linkqueue&s)link*p;p=s.front;s.front=p-next;delete p;上述算法的时间复杂度都为O(1)。3.2.6 队列的应用队列的应用队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面的例子来说明它，其他应用在后面章节中将会遇到。第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各
39、自运行自己的程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。2023年11月28日46第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写入到这个缓冲区中，写满后就暂停输出，继而去做其他的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。
