《数据结构》课程教学课件（PPT讲稿）第三章 栈和队列

1 第三章 栈和队列 栈和队列是一种操作受限的线性表 3.1 栈(stack) 只能在表尾进行插入和删除 表尾称栈顶( top) 表头称栈底(bottom) 栈按后进先出的原则进行（Last In First Out)

2 ADT Stack { 数据对象：D={ ai | ai∈Elemset,i=1,2,.,n, n>=0 } 数据关系：R1={| ai-1 ,ai ∈D,i=2,3,.,n } 约定an端为栈顶，a1端为栈底 。 基本操作： initStack(&s) destroyStack(&s) clearStack(&s) Stackempty(s) Stacklength(s) GetTop(s,&e) Push(&s,e) Pop(&s,&e) } ATD Stack 栈的抽象数据类型的定义

3 1）顺序栈：用一组地址连续的存储单元依次存储自栈底到 栈顶的各元素 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; base：指向栈底的位置；若为NULL，则表示栈不存在。 top： 指向栈顶元素的下一位置。 初值指向栈底，即top=base 栈的表示和实现

4 栈的初始化 Status InitStack(SqStack &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; }

5 读取栈顶元素的值 Status GetTop(SqStack s, SElemType &e) { if(S.top= =S.base) //S为空栈？ return ERROR; e=*(S.top-1) return OK; }

6 入栈 Status Push(SqStack &S, SElemType e) { if (S.top-S.base>=S.stacksize) //栈已满，需重新申请空 间 { S.base=(ElemType *) 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; S.top++; return OK; }

7 出栈 Status Pop(SqStack &S, SElemType &e) { if(S.top= =S.base) return ERROR; //空栈 e=*-S.top; return OK; }

8 3.2 栈的应用举例 3.2.1 数制转换 将十进制数N转换为d进制的数 N=(N div d)*d+ N mod d 以N=3467，d=8为例转换方法如下： N N / 8（整除） N % 8（求余） 3467 433 3 低位 433 54 1 54 6 6 6 0 6 高位 所以：(3467) 10 =(6613) 8 余数符合后进先出的规律

9 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 ) ; } } 十进制数转换成八进制数

10 行编辑程序 Void lineedit() //缓冲区（用栈结构）存放一行字符，逐行存入用户数据 区 { initstack(S); ch=getchar(); while(ch!=EOF) //文件结束吗？ { while(ch!=EOF && ch!=‘\n’) { switch(ch) { case ‘#’: Pop(S,c); //退格符 case ‘@’: ClearStack(S); //退行符 default: Push(S,ch); //其它字符则入栈 } ch=getchar(); } 将栈内字符传送到用户数据区； clearstack(s); if (ch!=EOF) ch=getchar(); } DestroyStack(S); }