中国计量学院数据结构第3章 栈和队列

1、3 栈和队列栈和队列3.1 栈栈 (Stack)3.2 栈的应用举例栈的应用举例3.3 队列队列 (Queue) 栈和队列是特殊的线性表，其“插入插入”和和“删除删除”操作只能操作只能在表的“端点端点”进行。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型3.1 栈栈 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.

2、,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() InitStack(&S) 操作结果操作结果：构造一个空栈：构造一个空栈 S。 DestroyStack(&S) 初始条件初始条件：栈：栈 S 已存在。已存在。 操作结果操作结果：栈

3、：栈 S 被销毁。被销毁。StackEmpty(S)初始条件初始条件：栈：栈 S 已存在。已存在。 操作结果操作结果：若栈：若栈 S 为空栈，则返回为空栈，则返回 TRUE，否则，否则 FALE。StackLength(S)初始条件初始条件：栈：栈 S 已存在。已存在。 操作结果操作结果：返回：返回 S 的元素个数，即的元素个数，即栈的长度。栈的长度。 GetTop(S, &e) 初始条件初始条件：栈：栈 S 已存在且非空。已存在且非空。操作结果操作结果：用：用 e 返回返回 S 的栈顶元素。的栈顶元素。a1a2an ClearStack(&S)初始条件初始条件：栈：栈 S 已存在。已存在。

4、操作结果操作结果：将：将 S 清为空栈。清为空栈。Push(&S, e) 初始条件初始条件：栈：栈 S 已存在。已存在。 操作结果操作结果：插入元素：插入元素 e 为新的栈顶为新的栈顶a1a2ane Pop(&S, &e) 初始条件初始条件：栈：栈 S 已存在且非空。已存在且非空。 操作结果操作结果：删除：删除 S 的栈顶元素，并用的栈顶元素，并用 e 返回其值。返回其值。a1a2anan-1 栈的表示和实现栈的表示和实现顺序栈顺序栈链栈链栈/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10;

5、 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack (SqStack &S)/ 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (SqStack &S, SElem

6、Type e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;Status Pop (SqStack &S, SElemTy

7、pe &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;栈顶指针链栈链栈a1an注意注意: 指针的方向指针的方向an-13.2 3.2 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序行编辑程序例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值如如:（1348)10 = (2504)8 ，其运算过程如下：，其运算过程如下： N N div 8 N

8、mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序例一、 数制转换void conversion () InitStack(S); scanf (%d, &N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S, e); printf ( %d, e ); 例二、例二、 括号匹配的检验括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）)均为不正确的格式。则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的分析

9、可能出现的不匹配不匹配的情况的情况:到来的右括弧到来的右括弧并非是所并非是所“期待期待”的；的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧。1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余， 否则和和栈顶元素栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” ， 否则表明不匹配不匹配。3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达式中匹配正确匹配正确， 否则表明“左括弧左括弧”有余有余。Status matching(

10、string & exp) int state = 1; while (i 4 2 + 4 - 2 + = 2 +2 + 2 2 + 2 * 2 + 2 * (2 + 2 * ( 3 2 + 2 * ( 3 + 2 + 2 * ( 3 + 8 2 + 2 * ( 3 + 8 ) = 2 + 2 * 11 = 2 + 22 = 26不论是操作数或运算符，最先输入，最后参与运算；因此，可以考虑使用栈实现。算法设置两个栈，分别存放操作数和运算符；输入操作数时，一定不会运算；运算过程实际就是运算符号比较的过程。设两个运算符：1，2，a 1 b 2 c1 2, 1 优先权高于 2，可以运算/表达式求值O

11、pendType EvaluateExpression( )InitStack( OPTR );Push( OPTR, # );InitStack( OPND );c = getchar( );while( !(c = # & GetTop( OPTR ) = #) )if( ! In( c, OP )Push( OPND, c);c = getchar( );elseswitch( Precede ( GetTop( OPTR), c )case :Pop( OPTR, t );Pop( OPND, b );Pop( OPND, a );Push( OPND, Operate( a, t,

12、b );break;/ switch/ if/ whilea = GetTop( OPND );DestroyStack( OPTR );DestroyStack( OPND );/ EvaluateExpression3 * ( 7 2 ) OPTR栈栈 OPND栈栈 输入输入 操作操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 * ( 7 2 ) # PUSH( OPTR, * )3 # * 3 ( 7 2 ) # PUSH( OPTR, ( )4 # * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 - 2 ) # PU

13、SH( OPTR, - )6 # * ( - 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( - 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND ) ADT Queue 数据对象：数据对象： Dai | aiQElemSet, i=1,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为队列尾队列尾基本操作：基本操作：3

14、.3 队列队列 ADT Queue队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作结果：操作结果：构造一个空队列构造一个空队列Q。DestroyQueue(&Q)初始条件：初始条件：队列队列Q已存在。已存在。 操作结果：操作结果：队列队列Q被销毁，被销毁， 不再存在。不再存在。 QueueEmpty(Q)初始

15、条件初始条件：队列：队列Q已存在。已存在。 操作结果操作结果：若：若Q为空队列，则返回为空队列，则返回TRUE，否则返回，否则返回FALSE。 QueueLength(Q) 初始条件初始条件：队列：队列Q已存在。已存在。 操作结果操作结果：返回：返回Q的元素个数，即队列的元素个数，即队列的长度。的长度。 GetHead(Q, &e) 初始条件初始条件：Q为非空队列。为非空队列。 操作结果操作结果：用：用e返回返回Q的队头元素。的队头元素。a1a2an ClearQueue(&Q)初始条件初始条件：队列：队列Q已存在。已存在。 操作结果操作结果：将：将Q清为空队列。清为空队列。 EnQueue(

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

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

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

19、p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK; #define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;循环队列循环队列顺序映象frontrearJ1J2J3J4frontrearJ1J2J3J4frontrearfrontrearJ1J2J3J4J6J5J1frontrear队列空间实际还有，但表现为缺少空间10Q.rearQ.front.543210J3J4J5Q.rearQ.front543210J3J4J5Q.rearQ.frontJ6J7J8543210Q.rearQ.frontacb空和满时头和尾指针相同，如何解决？空队列条件：空队列条件：Q.rear = Q.front;满队列条件满队列条件(Q.rear + 1) % maxsiz