第三章栈和队列

1、1第三章 栈和队列23.1 栈的类型定义栈的类型定义3.2 栈的应用举例栈的应用举例3.3 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现3通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列ListInsert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1ListDelete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型43.1 栈的类型定义栈的类

2、型定义 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack5InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()6 InitStack(&

3、amp;S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。7 StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。8 StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。9 GetTop(S, &e)初始条件：栈 S 已存在且非空。操作结果：用e返回 S 的栈顶元素。a1a2an 10 ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。11 Push(&

4、;S, e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。a1a2ane 12 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 133.2 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序问题行编辑程序问题例四、例四、 表达式求值表达式求值例五、例五、 实现递归实现递归14 例一、例一、 数制转换数制转换 算法基于原理： N = (N div d)d + N mod d 15例如：例如：（1348)10

5、= (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序16void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion17例二、例二、 括号匹配的检验括号匹配的检验则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。假设在表达式中 （）或（

6、）等为正确的格式。例如：考虑下列括号序列：例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 818分析可能出现的不匹配不匹配的情况:v到来的右括弧非是所“期待”的;v到来的是“不速之客”;v直到结束，也没有到来所“期待”的括弧;（ ）或 ( ) 或 （ ）均为不正确的格式。19算法的设计思想：算法的设计思想：1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” 否则表明不匹配不匹配3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达

7、式中匹配正确匹配正确 否则表明“左括弧左括弧”有余有余20Status matching(string& exp) int state = 1; while (i= S.stacksize) /栈满 return OVERFLOW; *S.top+ = e; return OK;47Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用 e 返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;48栈

8、顶指针链栈链栈a1an注意注意: 链栈中链栈中指针的方向指针的方向an-1栈底元素栈底元素49 习习 题题设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈出栈次序为push(1)，pop( )，push(2)，push(3)，pop( )，pop( )，push(4)，pop( )，则出栈的数字序列为什么？（2）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。50 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1

9、, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为队列尾队列尾基本操作：基本操作：3.4 队列的类型定义队列的类型定义 ADT Queue51队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)52InitQueue(&Q) 操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q

10、) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：队列Q被销毁， 不再存在。53QueueEmpty(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：若Q为空队列，则 返回TRUE，否则 返回FALSE。54 QueueLength(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：返回Q的元素个数，即队列的长度。55 GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：用e返回Q的队头元素。a1a2an 56 DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：删

11、除Q的队头元素，并用e返回其值。a1a2an 57 EnQueue(&Q, e) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane 58 ClearQueue(&Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：将Q清为空队列。593.5 队列类型的实现队列类型的实现链队列链队列链式映象循环队列循环队列顺序映象60 typedef struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;链队列链队列链式映象61type

12、def struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.frontQ.rear空队列空队列Q.rear队头元素队头元素62 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;63 Status EnQueue (

13、LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = new QNode; if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;Q.frontQ.rearepa1an64 Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rea

14、r) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; delete (p); return OK;if (Q.rear = p) Q.rear = Q.front;65Q.frontQ.reara1注意：出队列操作的特殊情况注意：出队列操作的特殊情况if (Q.rear = p) Q.rear = Q.front;66#define MAXQSIZE 100 /最大队列长度typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， /

15、指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 int queuesize; SqQueue;循环队列循环队列顺序映象67注意：顺序队列的几种情况：注意：顺序队列的几种情况：abcQ.frontQ.rear1、一般情况：、一般情况：100Q.frontQ.rear02、初始化：、初始化：68abcQ.frontQ.rearabQ.front注意：顺序队列的几种情况：注意：顺序队列的几种情况：3、特殊情况：、特殊情况：cQ.reardQ.rearQ.frontdQ.rearQ.rear69Q.front=Q.rear 队满还是队空队满还是队空?约定

16、约定: 少用一个元素空间，以“队列头指针在队列尾指针的下一位置上”作为队列呈“满”状态的表示。70Q.front=Q.rear 队满还是队空队满还是队空?Q.frontQ.rearv队列空：队列空：Q.front=Q.rearQ.frontQ.rearabcd efgv队列满：队列满：（Q.rear +1）% maxsize = Q.front71(a) 空队 (b)非空队 (c)满队 循环队列示意图72 Status InitQueue (SqQueue &Q, int maxsize) / 构造一个最大存储空间为 maxsize 的 / 空循环队列 Q Q.base = new E

17、lemTypemaxsize; if (!Q.base) exit (OVERFLOW); Q.queuesize = maxsize; Q.front = Q.rear = 0; return OK; 73Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % Q.queuesize = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % Q.queuesize; return OK;74 Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % Q.queuesize