第三章栈和队列栈和队列是一种操作受限的线性表3.1栈(stack)只能在表尾进行插入和删除表尾称栈顶(top)表头称栈底(bottom)栈按后进先出的原则进行（LastIn FirstOut)
1 第三章 栈和队列 栈和队列是一种操作受限的线性表 3.1 栈(stack) 只能在表尾进行插入和删除 表尾称栈顶( top) 表头称栈底(bottom) 栈按后进先出的原则进行（Last In First Out)
栈的抽象数据类型的定义ADT Stack{数据对象：D={a;|a,EElemset,i=l,2,,n，n>=0}数据关系：R1=[l ai-1,a;ED,i=2,3,",n约定a.端为栈顶，a,端为栈底。基本操作：initStack(&s)destroyStack(&s)clearStack(&s)Stackempty(s)Stacklength(s)GetTop(s,&e)Push(&s,e)Pop(&s,&e)ATD Stack2
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 栈的抽象数据类型的定义
栈的表示和实现1）顺序栈：用一组地址连续的存储单元依次存储自栈底到栈顶的各元素typedef struct{ SElemType *base;SElemType *top;intstacksize;} SqStack;指向栈底的位置；若为NULL，则表示栈不存在。base:top:指向栈顶元素的下一位置。初值指向栈底，即top=base3
3 1）顺序栈：用一组地址连续的存储单元依次存储自栈底到 栈顶的各元素 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; base：指向栈底的位置；若为NULL，则表示栈不存在。 top： 指向栈顶元素的下一位置。 初值指向栈底，即top=base 栈的表示和实现
栈的初始化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;1
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; }
读取栈顶元素的值Status GetTop(SqStack S, SElemType &e)IIS为空栈？( if(S.top= =S.base)return ERROR;e=*(S.top-1)return OK;1
5 读取栈顶元素的值 Status GetTop(SqStack s, SElemType &e) { if(S.top= =S.base) //S为空栈？ return ERROR; e=*(S.top-1) return OK; }
入栈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+=STACKINCREMENT1*S.top=e;S.top++;return OK;6
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; }
出栈Status Pop(SqStack &S, SElemType &e)；1空栈( if(S.top= =S.base) return ERROR;e=*.-S.top;return OK;^
7 出栈 Status Pop(SqStack &S, SElemType &e) { if(S.top= =S.base) return ERROR; //空栈 e=*-S.top; return OK; }
3.2栈的应用举例3.2.1数制转换将十进制数N转换为d进制的数N=(N divd)*d + N modd以N=3467，d=8为例转换方法如下：NN/8（整除）N%8（求余）34333467低位5414335466066高位所以: (3467)10o =(6613):余数符合后进先出的规律8
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 余数符合后进先出的规律
十进制数转换成八进制数/任何非负值的十进制数转换成八进制数void conversionoinitstack(S);scanf("%d",N);while (N)//余数入栈 Push (S N %8):N=N / 8;1while (!StackEmpty(S)) Pop(S,e);printf(“ %d ",e) ;C9
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 ) ; } } 十进制数转换成八进制数
行编辑程序Void lineedit()Ⅱ缓冲区（用栈结构）存放一行字符，逐行存入用户数据区( initstack(S); ch=getchar();Ⅱ文件结束吗?while(ch!=EOF){ while(ch!=EOF&& ch!='ln'){ switch(ch)I/退格符{ case ‘#": Pop(S,c);Ⅱ退行符case‘@': ClearStack(S);Ⅱ其它字符则入栈default: Push(S,ch);1ch=getchar();人将栈内字符传送到用户数据区clearstack(s);if(ch!=EOF)ch=getchar()1DestroyStack(S);710
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); }