1、数据结构课程的内容数据结构课程的内容3.1 栈（栈（Stack） 第三章第三章 栈和队列栈和队列3.2 队列队列（Queue）1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 定义定义3.1 栈栈与同线性表相同，仍为一对一关系。与同线性表相同，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶只能在栈顶(表尾表尾)运算，且访问结点时依照后运算，且访问结点时依照后进先出（进先出（LI
2、FO）或先进后出（）或先进后出（FILO）的原则。）的原则。关键是编写入栈和出栈函数，具体实现依顺关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。栈、或判断栈满、栈空等。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构限定只能在表的一端进行插入和删除运算的限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）线性表（只能在栈顶操作）问：堆栈是什么？它与一般线性表有什么不同？问：堆栈是什么？它与一般线性表有什么
3、不同？3.1 栈栈答：答：堆栈是一种特殊的线性表，它只能在表的一端堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。与一般线性表的区别：仅在于运算规则不同。一般线性表一般线性表 堆栈堆栈逻辑结构：一对一逻辑结构：一对一 逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序表、链表 存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：随机存取运算规则：随机存取 运算规则：后进先出运算规则：后进先出(LIFO)“进进” 压入压入=PUSH（x)“出出” 弹出弹出=POP ( y )栈栈 是
4、仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶 top ; 表头表头(即即 a1 端端)称为称为栈底栈底base例如：例如： 栈栈 s= (a1 , a2 , a3 , .,an-1 , an ) a1 称为称为 栈底元素栈底元素 an 称为称为 栈顶元素栈顶元素插入元素到插入元素到栈顶栈顶（即表尾）的操作，称为（即表尾）的操作，称为入栈入栈。从从栈顶栈顶（即表尾）删除最后一个元素的操作，称为（即表尾）删除最后一个元素的操作，称为出栈出栈。教材教材P44P44对对栈栈有更详细定义：有更详细定义：强调：强调：插入和删除都只能
5、在表的一端（栈顶）进行！插入和删除都只能在表的一端（栈顶）进行！顺序栈示意图顺序栈示意图s a1 a2 a3data a4(栈底栈底)(栈顶栈顶)99.3210top a1 a2 an顺序栈顺序栈S ai表和栈的操作区别表和栈的操作区别对线性表对线性表 s= (a1 , a2 , . , an-1 , an )表头表头表尾表尾栈底栈底base栈顶栈顶top低地址低地址高地址高地址写入：写入：vi= ai读出：读出： x= vi压入：压入：PUSH (an+1)弹出：弹出： POP (x)前提：一定要预设栈顶指针前提：一定要预设栈顶指针top！低地址低地址高地址高地址vi a1 a2 ai an
6、 顺序表顺序表Vn an+1入栈操作入栈操作例如用堆栈存放（例如用堆栈存放（A A，B B，C C，D D） （注意要遵循（注意要遵循“后进先出后进先出” 原则）原则）AACBABAtop核心语句：核心语句：top=L; 顺序栈中的顺序栈中的PUSHPUSH函数函数status Push(ElemType x) if(topM)上溢 else vtop+top+=x;Push (B);Push (C);Push (D);toptoptoptop低地址低地址LPush (A);高地址高地址MBCD 出栈操作出栈操作例如从栈中取出例如从栈中取出B B （注意要遵循（注意要遵循“后进先出后进先出”
7、原则）原则）DCBAtoptopDCABDCBAtopDCBAtoptop低地址低地址L高地址高地址MD核心语句：核心语句：Pop ( );Pop ( );Printf( Pop () );顺序栈中的顺序栈中的POPPOP函数函数status Pop( )status Pop( ) if(top=L) if(top=L) 下溢下溢 else y=velse y=v-top-top; ; return(y); return(y); 例例1：一个栈的输入序列是一个栈的输入序列是12345，若在入栈的过，若在入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实现可能实现吗？
8、吗？12345的输出呢？的输出呢？ 43512不可能实现，主要是其中的不可能实现，主要是其中的12顺序不能顺序不能实现；实现； 12345的输出可以实现，只需压入一个立即弹的输出可以实现，只需压入一个立即弹出一个即可。出一个即可。 435612中到了中到了12顺序不能实现；顺序不能实现； 135426可以实现。可以实现。例例2：如果一个栈的输入序列为如果一个栈的输入序列为123456，能否得，能否得到到435612和和135426的出栈序列？的出栈序列？答：答：答：答：例例3（严题集（严题集3.1）一个栈的输入序列为一个栈的输入序列为123，若在，若在入栈的过程中允许出栈，则可能得到的出栈序列
9、是入栈的过程中允许出栈，则可能得到的出栈序列是什么？什么？答：答： 可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入入3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5 5种可能性。种可
10、能性。补充补充1：若入栈动作使地址向高端增长，称为若入栈动作使地址向高端增长，称为“向上生成向上生成”的栈；的栈；若入栈动作使地址向低端增长，称为若入栈动作使地址向低端增长，称为“向下生成向下生成”的栈；的栈； 对于向上生成的栈对于向上生成的栈入栈入栈口诀：堆栈指针口诀：堆栈指针top先压后加（先压后加（vvtop+top+=x=x）；）；出栈出栈口诀：堆栈指针口诀：堆栈指针top先减后弹（先减后弹（y=vy=v-top-top) 。3.1 栈栈补充补充2： 栈不存在的条件：栈不存在的条件： base=NULL; 栈为空栈为空 的条件的条件 ： base=top; 栈满的条件栈满的条件 ： t
11、op-base=stacksize;补充补充3：链栈：链栈 链栈示意图链栈示意图s(栈底栈底)(栈顶栈顶)topa3a2a4a1链栈的入栈函数、出栈函数链栈的入栈函数、出栈函数（以头指针为栈顶，在头指针处插入或删除！）（以头指针为栈顶，在头指针处插入或删除！）公共说明部分：公共说明部分： typedef struct snode SElemType data; struct snode *link;NODE;NODE *st, *p;int m=sizeof(NODE); Push (SElemType x) p=(NODE*)malloc(m); if(!p)上溢上溢else p-data=
12、x; p-link=st; st=p; S Status pop( ) pop( ) if(st=NULL) if(st=NULL)下溢下溢 elsey=st-data;p=st;st=st-link; elsey=st-data;p=st;st=st-link; free(p); return(y);free(p); return(y); 链栈链栈入栈入栈函数函数链栈链栈出栈出栈函数函数插入插入表头表头从表头从表头删除删除说说 明明问：为什么要设计堆栈？它有什么独特用途？问：为什么要设计堆栈？它有什么独特用途？1. 调用函数或子程序非它莫属；调用函数或子程序非它莫属；2. 递归运算的有力工具
13、；递归运算的有力工具；3. 用于保护现场和恢复现场；用于保护现场和恢复现场；4. 简化了程序设计的问题简化了程序设计的问题。答：答： 数制转换（十转数制转换（十转N） P48 设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例2：括号匹配的检验括号匹配的检验P49 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例3 ：表达式求值表达式求值 P52 设计思路：用栈暂存运算符设计思路：用栈暂存运算符例例4：汉诺仪（：汉诺仪（Hanoi）塔）塔P55 设计思路：用栈实现递归调用设计思路：用栈实现递归调用例例1：例例3 表达式求值表达式求值 ( 这是栈应用的典型例子这是栈应用的典型例子 ) 这里
14、，这里，表达式求值的算法是表达式求值的算法是 “算符优先法算符优先法”。例如：例如：3*（7 2 ） （1）要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则： a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 15（2）根据上述三条运算规则，在运算的每一步中，对）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符任意相继出现的算符 1和和 2 ，都要比较优先权关系。，都要比较优先权关系。算符优先法所依据
15、的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53表表3.1 （是提供给计算机用的表！）（是提供给计算机用的表！）由表可看出，右括号由表可看出，右括号 ) 和井号和井号 # 作为作为 2时时级别最低；级别最低； 由由c 规则规则得出：得出： * ，/， + ，-为为 1时的优先权低于时的优先权低于（，高于，高于） 由由a规则规则得出：得出：（=） 表明括号内运算，已算完。表明括号内运算，已算完。 # = # 表明表达式求值完毕。表明表达式求值完毕。栈的应用（表达式求值）栈的应用（表达式求值）（3）算法思想：）算法思想： 设定两栈：设定两栈：操作符栈操作符栈 OPTR ，操作
16、数栈，操作数栈 OPND 栈初始化栈初始化：设操作数栈：设操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈的栈底元素为表达式起始符底元素为表达式起始符 #； 依次读入字符依次读入字符：是操作数则入：是操作数则入OPND栈，是操作符则要判断：栈，是操作符则要判断： if 栈顶元素栈顶元素 操作符操作符 ，则退栈、计算，结果压入，则退栈、计算，结果压入OPND栈；栈； 栈顶元素栈顶元素 =操作符且不为操作符且不为#，脱括号（弹出左括号）；，脱括号（弹出左括号）； 栈顶元素栈顶元素 : Push(OPTR , c); c=getchar();break; case =: Pop(OP
17、TR);c=getchar();break; case next=S; rear=S;出队（头部删除）：出队（头部删除）：front-next=p-next;完整动作设计参完整动作设计参见教材见教材P61-62 队列会满吗？队列会满吗？front=rear一般不会，因为删除时有一般不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！1) 构造一个空队列Status InitQuene( LinkQuene &Q ) Q.front = Q.rear = ( QuenePtr ) malloc ( sizeof (QNode); if ( !Q.front ) exit ( OVE
18、RFLOW); Q.front next = NULL; return OK; 2) 销毁队列Status DestroyQuene ( LinkQuene &Q) while ( Q.front ) Q.rear = Q.frontnext; free ( Q.front); Q.front = Q.rear; return OK;3) 入队Status EnQuene ( LinkQuene &Q, QElemType e) /插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 p = ( QuenePtr) malloc ( sizeof ( Qnode); if ( !p) exit
19、 (OVERFLOW); pdata = e; pnext = NULL; Q.rearnext = p; Q.rear = p; return OK; 4) 出队Status DeQuene ( LinkQuene &Q, QElemType &e) /若队列不空，则删除若队列不空，则删除Q的队头元素，用的队头元素，用e返回其值，并返回返回其值，并返回OK； / 否则返回否则返回ERROR if ( Q.front = = Q.rear ) return ERROR; p = Q.front next; e = p data; Q.front next = p next; if ( Q.re
20、ar = = p) Q.rear = Q.front; free (p); return OK;顺序队示意图顺序队示意图Q(队尾队尾)(队首队首)front a1 a2 a3data a40.99rear 队列会满吗？队列会满吗？很可能会，因为数组前很可能会，因为数组前端空间无法释放。因此端空间无法释放。因此数组应当有长度限制。数组应当有长度限制。 空队列的特征？空队列的特征？ 约定：约定：front=rear队尾后地址队尾后地址入队入队(尾部插入尾部插入)：vrear=e; rear+;出队出队(头部删除头部删除)：x=vfront; front+;讨论：讨论： 有有缺缺陷陷 怎样实现入队和
21、怎样实现入队和出队操作？出队操作？3.2 队列队列问：什么叫问：什么叫“假溢出假溢出” ？如何解决？如何解决？答：答：在顺序队中，当尾指针已经到了数组在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫中还有空位置，这就叫“假溢出假溢出”。3.2 队列队列解决假溢出的途径解决假溢出的途径采用循环队列采用循环队列a3a2a10123N-1rearfronta3a2a1frontrear 0 1 2 3 . .N-1新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满时也会有队满时也会有f
22、ront=rear；判决条件将出现二义性！判决条件将出现二义性！解决方案有三：解决方案有三： 加设标志位，让删除动作使其为加设标志位，让删除动作使其为1,插入动作使其为插入动作使其为0,则可识别当前则可识别当前 front=rear 使用一个计数器记录队列中元素个数（即队列长度）；使用一个计数器记录队列中元素个数（即队列长度）； 人为浪费一个单元，令人为浪费一个单元，令队满特征为队满特征为front=(rear+1)%N；队空条件队空条件 : front = rear (初始化时：初始化时：front = rear )队满条件队满条件： front = (rear+1) % N (N=maxs
23、ize)队列长度：队列长度：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear 选用选用空闲单元法：空闲单元法：即即front和和rear之一指向实元素，另一指向空闲元素。之一指向实元素，另一指向空闲元素。 问问3： 在具有在具有n个单元的循个单元的循环队列中，队满时共有多少环队列中，队满时共有多少个元素？个元素？ n-1个个5 问问2：左图中队列长度左图中队列长度L=？问问1：左图中队列容量左图中队列容量 maxsize N=？6 注意： 循环队列中的循环队列中的“长度长度”到底是指总长度还是数据元到底是指总长度还是数据元素素个数？个数？ 答：一般情况下的长度（
24、答：一般情况下的长度（L）是指元素个数（不含头）是指元素个数（不含头结点或空闲单元），而结点或空闲单元），而maxsize N 才是指所有单元总才是指所有单元总 数，即数，即“容量容量”。J6 J5J7J8 J9例例1： 一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再个元素，接着再插入插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置? J2 J3J1 J4 J5frontrear解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1和和rear=6。frontrear删除删除4个元素
25、后个元素后front=5；再插入；再插入4个元素后，个元素后，rear=4。 frontfrontfrontfrontfront例例2 ：数组数组n用来表示一个循环队列，用来表示一个循环队列，f 为当前队列头元为当前队列头元素的素的前一前一位置，位置，r 为队尾元素的位置。假定队列中元素的个为队尾元素的位置。假定队列中元素的个数小于数小于n，计算队列中元素的公式为，计算队列中元素的公式为:（）（） rf （）（）（nfr）% n （）（）nrf （）（） （nrf）% n4种公式哪种合理？种公式哪种合理？当当 r f 时（时（A）合理；）合理；当当 r f 时（时（C）合理；）合理；分析分析
26、：综合综合2种情况，以（种情况，以（D）的表达最为合理的表达最为合理例例3：在一个循环队列中，若约定队首指针指向队首元素在一个循环队列中，若约定队首指针指向队首元素的的前一个前一个位置。那么，从循环队列中删除一个元素时，其位置。那么，从循环队列中删除一个元素时，其操作是操作是 先先 ，后，后 。 移动队首指针移动队首指针取出元素取出元素问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？1. 离散事件的模拟（模拟事件发生的先后顺序）；离散事件的模拟（模拟事件发生的先后顺序）；2. 操作系统中多道作业的处理（一个操作系统中多道作业的处理（一个CPU执行多个作执行多个作
27、业）；业）；3. 简化程序设计。简化程序设计。答：答：循环队列的操作实现循环队列的操作实现见教材见教材P64P64循环队列的操作实现循环队列的操作实现1）初始化一空队列初始化一空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间算法操作：为队列分配基本容量空间 设置队列为设置队列为空队列空队列，即即 front=rear=0（也可为任意单元，如（也可为任意单元，如 2，或，或 4）;算法：算法：Status InitQueue ( SqQueue &q )/初始化空循环队列初始化空循环队列 q q . base=(QElemType *)malloc(sizeof
28、(QElemType）* QUEUE_MAXSIZE); /分配空间分配空间 if (!q.base) exit(OVERFLOW); /失败，退出程序失败，退出程序 q.front =q.rear=0; /置空队列置空队列 return OK; /InitQueue;新开单元的地址为新开单元的地址为0则表示内存不足则表示内存不足算法说明：向循环队列的队尾插入一个元素算法说明：向循环队列的队尾插入一个元素分分 析析：(1) 插入前应当先判断队列是否满插入前应当先判断队列是否满 if ( q . rear + 1 ) % QUEUE_MAXSIZE )=q.front) return ERROR
29、;(2）插入动作）插入动作 q.base q.rear = e; q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; 2） 入队操作入队操作Status EnQueue(SqQueue &q, QElemType e)/向循环队列向循环队列 q 的队尾加入一个元素的队尾加入一个元素 e if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front ) return ERROR ; q.base q.rear = e; /存储存储 q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;/指针后移指针后移 r
30、eturn OK; / EnQueue;2） 入队操作（完整函数）入队操作（完整函数）3）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值 e 分分 析：析： （1） 在删除前应当判断队列是否空；在删除前应当判断队列是否空； if (q.front = q.rear ) return ERROR; （2）插入动作分析；插入动作分析； 因为队头指针因为队头指针front指向队头元素的位置，所以：指向队头元素的位置，所以： e = q.base q.front ; q.front = ( q . front + 1 ) % QUEUE_MAXSIZE; Statu
31、s DeQueue ( SqQueue &q, QElemType &e) /若队列不空，删除循环队列若队列不空，删除循环队列 q 的队头元素，的队头元素， /由由 e 返回其值，并返回返回其值，并返回OK if ( q.front = = q.rear ) return ERROR;/队列空队列空 e = q.base q.front ; /队头元素出队队头元素出队 q.front=(q.front+1) % QUEUE_MAXSIZE ; /指针后移指针后移 return OK; / DeQueue算法：算法：讨论（代本章小结）讨论（代本章小结）线性表、栈与队的异同点线性表、栈与队的异同点
32、相同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即链表存储；栈和队列是两种特殊的线性表，即受限的线受限的线性表性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点： 运算规则不同，线性表为随机存取，而栈是只允许在一运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表端进行插入和删除运算，因而是后进先出表LIFOLIFO；队列；队列是只允许在一端进行插入、另一端进行删除运算，因而是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表是先进先出表FIFOFIFO。 用途不同，线性表比较通用；堆栈用于函数调用、递归用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。和简化设计等。
