第三章 栈的相关内容(常州大学)

1、3.1 栈 ( Stack )3.1.1 栈的定义及运算假设栈S=(a1，a2，a3，an)，则栈底元素?栈顶元素?栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素？ 只允许在一端插入和删除的顺序表 允许插入和删除 的一端称为栈顶 (top)， 另一端称为栈底(bottom) 特点 后进先出 (LIFO)栈的示意图出栈进栈栈顶栈底ana2a1例：对于一个栈，给出输入项A、B、C，如果输入项序列由A B C组成，试给出所有可能的输出序列。A进 A出 B进 B出 C进 C出 ABCA进 A出 B进 C进 C出 B出 ACBA进 B进 B出 A出 C进 C出 BACA进 B进 B出 C进

2、 C出 A出 BCAA进 B进 C进 C出 B出 A出 CBA不可能产生输出序列CAB栈的顺序存储结构顺序栈的定义typedef int DataType;#define maxsize 64typedef struct DataType datamaxsize; int top;SeqStack; 设s是SeqStack类型的指针变量。 sdata0是栈底元素 进栈时需将stop加1，退栈时需将stop 减1相关概念:空栈和栈满 因此： stoptop =stacksize-1 表示栈满。 当栈满时再做进栈运算必定产生空间溢出，简称“上溢” 当栈空时再做退栈运算也将产生溢出，简称“下溢”。相

3、关概念:上溢和下溢进出栈示例toptoptopAABCDEAB空栈 A进栈 B C D E 进栈E D C 出栈toptop-1约定栈顶指针指向栈顶元素的位置注意：栈的基本操作1、初始化2、判栈是否非空3、进栈4、退栈5、取栈顶元素（1）InitStack(&s) 初始化：初始化一个新的栈。（2）StackEmpty(s) 栈空判断：若栈s空，则返回TRUE；（3）Push(&s,x) 入栈：在栈s的顶部插入元素x，若栈满，则返回FALSE；（4）Pop(&s) 出栈：若栈s不空，则返回栈顶元素，并从栈顶中删除该元素；否则，返回空元素NULL。（5）GetTop(s,x

4、) 取栈元素：若栈s不空，则返回栈顶元素；栈的基本操作void InitStack(SeqStack *s) s-top-1; 置空栈void ClearStack(SeqStack *s) s-top-1; 栈的基本运算判栈空int StackEmpty(SeqStack *s) if (s-top=0) return 0; else return 1;int Push(SeqStack *s,DataType x) s-top+; s-datas-topx; return 1; if (s-top=maxsize-1) printf(“overflown”); return 0; else

5、进栈DataType Pop(SeqStack *s) DataType x x= s-datas-top; s-top-; return(x); if (StackEmpty(s) printf(“underflown”); return 0; else出栈DataType GetTop(SeqStack *s, DataType x) x= s-datas-top; return(x); if (StackEmpty(s) printf(“underflown”); return 0; else 取栈顶元素3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的

6、工具。以下是几个栈应用的例子。 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多。 原理: N=(N div d)*d+ N mod d ( 其中:div为整除运算,mod为求余运算) n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序(2504)8(1348)10数制转换算法：void conversion( ) InitStack(s); /建空栈 scanf(“%d”,&x); /输入一个非负十进制整数 while(x!=0) / x不等于零 循环 push(s, x% 8

7、); / x/8第一个余数进栈 x=x/8; /整除运算 while(! StackEmpty(s) ) x=pop(s); printf(“%d”,x); /依次输出栈顶元素 3.2.4中缀表达式求值表达式由操作数（operand）、运算符（operator）和界限符组成的。 在处理表达式前，首先设置两个栈：（1）操作数栈（OPND）：存放操作数（2）运算符栈（OPTR）：存放运算符。 在运算符栈中先压入结束符“#”。运算符可以是算术运算符、关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符。算符优先关系表 表达式中任何相邻运算符c1、c2的优先关系有： c1c2：c1的优先级高于

8、c2+ c2 c1 -*/()#+ - * / ( ) # = 算符间的优先关系表注： c1 c2是相邻算符， c1在左， c2在右读出一个符号后，作如下处理：（1）是操作数:将其压入操作数栈，读下一个符号。中缀表达式求值算法 （2）是运算符：1）比栈顶高：压入运算符栈，并读下一个符号。与栈顶运算符的优先级比较2）比栈顶低：则从操作数栈连续退出两个操作数从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈。此时读出的运算符下次重新考虑3）假如读出的是“）”，则：A）若运算符栈栈顶不是“（”，连续退出两操作数，退出一个运算符，作相应的运算，将结果压操作数栈，然后继续执行AB）若

9、运算符栈栈顶为“（”，则消去括号，依次读下一个符号 int express ( ) /运算数栈，OP为运算符集合。 InitStack(OPTR); Push (OPTR, # ); InitStack(OPND); c=getchar( ); 在算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符一个是OPND栈，用以保存操作数或运算结果。 while(c!= # | GetTop(OPTR)!=#) if(! In(c,OP) / In(c, OP)判断c是否 是运算符的函数 Push(OPND,c); /不是运算符则进栈 c=getchar(); else续 switch (Pre

10、cede(GetTop(OPTR), c) case : /栈顶算符优先权高,出栈并将运算结果入栈OPND op=Pop(OPTR); b=Pop(OPND); a= Pop(OPND); Push(OPND,Operate(a, op, b); break; return GetTop(OPND);char Precede (char sym1,char sym2) /*比较两操作符优先级*/int i; char chl2; int ind2;char re77=, , , , ,=; chl0=sym1; chl1=sym2; for(i=0;i2;i+) switch(chli) case +:indi=0;break; case -:indi=1;break; case *:indi=2;break; case /:indi=3;break; case (:indi=4;break; case ):indi=5;break; case #:indi=6;break; defaul:printf(Error!n);return(0); return(reind0ind1);double Operate(double a,char sym,doubl