数据结构第三章栈

数据结构李鑫辽宁工程技术大学电信学院数据结构课程的内容3.1栈（Stack）3.2队列（Queue）

第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义3.1栈与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。3.存储结构4.运算规则5.实现方式

2.逻辑结构限定只能在表的一端进行插入和删除运算的线性表。即栈顶基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶

/top;表头(即a1端)称为栈底/base例如：栈S=(a1,a2,a3,……….,an-1,an

)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！栈的存储结构顺序栈实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空Q1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表

堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)

a1

a2……

an顺序栈S

ai……Q2：顺序表和顺序栈的操作有何区别？表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):

S[top++]=an+1弹出(POP):e=S[--top]低地址高地址S[i]

a1

a2

ai

an

……顺序表S

……

an+1以线性表

S=(a1,a2,….,an-1,an)为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize;

a1

a2……

an顺序栈S

ai……低地址高地址

an+1栈底base栈顶top若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；

对于向上生成的堆栈:入栈口诀：堆栈指针top“先压后加”:S[top++

]=an+1出栈口诀：堆栈指针top“先减后弹”:e=S[--top

]Q3：什么叫“向上生成”的栈？“向下生成”又是何意？Q4：为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。下面用4个例子来帮助理解堆栈：例1一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。例2：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，b

Ｃ）b，c，d，aＤ）a，c，d，bA）、D）可以，

B）、C）不行。讨论：有无通用的判别原则？有！若输入序列是…,Pj…Pk…Pi…(Pj<Pk<Pi)，一定不存在这样的输出序列

…,Pi…Pj…Pk…答：即对于输入序列1，2，3，不存在输出序列3，1，2考研题栈的抽象数据类型定义:(教材P44-45）ADTStack{数据对象：D={D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R=={<ai–1,ai>|ai–1,ai∈D,i=2,…,n}}约定an端为栈顶，a1端为栈底。基本操作：……}ADTStack入栈、出栈、建栈初始化、判断栈满或栈空、读栈顶元素值等。本节重点：顺序栈和链栈的基本操作基本操作InitStack（&s）操作结果：构造一个空栈DestroyStack(&s)初始条件：栈s已经存在操作结果：栈s被销毁ClearStack（&s）初始条件：栈s已经存在操作结果：将s清为空StackEmpty(s)初始条件：栈s已经存在操作结果：若栈为空栈，则返回TRUE,否则FALSEStackLength（s）初始条件：栈s已经存在操作结果：返回栈的元素个数，即栈的长度GetTop（s,&e）初始条件：栈s已经存在且非空操作结果：用e返回s的栈顶元素Push（&s,e）初始条件：栈s已经存在且非空操作结果：插入元素e为新的栈顶元素Pop（&s,&e）初始条件：栈s已经存在且非空操作结果：删除s的栈顶元素，并用e返回其值顺序栈的存储表示（教材P46)：

#defineSTACK-INIT-SIZE100

//存储空间初始分配量

#defineSTACKINCREMENT10

//存储空间分配增量

typedefstruct{

SElemType*base;

//栈的基址即栈底指针

SElemType*top;

//栈顶指针

intstacksize;

//当前分配的空间

}SqStack;动态数组顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：top=L;

顺序栈入栈函数PUSH（）statusPush(ElemTypee){if(top>M){上溢}else*s.top++

=e;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD等价于*s.top=es.top++顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop();顺序栈出栈函数POP()statusPop(){if(top=L){下溢}else{e=*--s.top;return(e);}}Pop();Printf(Pop());等价于--s.tope=*s.top链栈的入栈操作和出栈操作(1)链栈的构造方式——以头指针为栈顶，在头指针处插入或删除.Node*st,*p;intm=sizeof(Node);栈顶栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈st

a1

a2an-1

annextdata链栈中每个结点由两个域构成：data域和next域，其定义为：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;Push(SElemTypee){p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->next=st;st=p;}}

StatusPop()

{if(st==NULL){下溢}else{e=st->data;p=st;st=st->next;

free(p);return(e);}}链栈入栈函数链栈出栈函数插入表头从表头删除(2)操作由此可以看出：一个链栈由其栈顶指针唯一指定设st指向栈顶元素，当st=NULL时表示栈空链栈不必设头结点，因为栈顶（表头）操作频繁；链栈一般不会出现栈满情况，除非没有空间导致malloc分配失败。链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。几点说明:例1：数制转换（十转N）——见教材P48

设计思路：用栈暂存低位值例2：行编辑程序————见教材P49

设计思路：用栈暂存输入数据例3

：表达式求值

—-————见教材P52

设计思路：用栈暂存运算符例4：汉诺（Hanoi）塔-———见教材P55

设计思路：用栈实现递归调用栈的应用举例例1、多进制输出：Voidconversion（）{//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。InitStack（s）//构造空栈scanf(“%d”,N);while(N){Push(s,N%8);N=N/8;}While（!StackEmpty(s)）{pop(s,e);printf(“%d”,e);}}//conversion例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文字符串：“madamimadam”上海自来水来自海上完成该算法的类c语言描述限于二目运算符的表达式定义：表达式::=(操作数)+（运算符）+（操作数）操作数::=简单变量|表达式例3、表达式求值在计算机中，表达式可有三种不同的标识方法设Exp=S1+OP+S2则称OP+S1+S2为表达式的

前缀表示法称S1+OP+S2为表达式的

中缀表示法称S1+S2+OP

为表达式的

后缀表示法可见，它以运算符所在不同位置命名的例如：Exp=a×b

+(c–d/e)×f前缀式(波兰式)：+×ab

×-c/def中缀式：a×b

+c–d/e×f后缀式（逆波兰式）：ab×

cde/-f×+结论：1）操作数之间的相对次序不变2）运算符的相对次序不同3）中缀式丢失了括号信息，致使运算的次序变得不确定4）前缀式的运算规则为：5）后缀式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序连续出现的两个操作数和在它们之前且仅靠它们的运算符构成一个最小表达式每个运算符和它之前出现且仅靠它的两个操作数构成一个最小表达式后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top43top735top例计算4+3*5=后缀表达式：435*+top415top19如何求后缀表达式呢？写出算法

前缀表达式中缀表达式后缀表达式（RPN)+*abca*b+cab*c++a*bca+b*cabc*++a/+*bcdea+（b*c+d）/eabc*d+e/+中缀表达式：操作数栈和运算符栈例计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符-12如何从原表达式求后缀式？

例如a*b+（c-d/e）*f

后缀式（逆波兰式）：ab×

cde/-f×+

1）设立运算符栈；2）设表达式的结束符为#，予设运算符栈的栈底为#3）若当前字符是操作数，则直接发送给后缀式；4）若当前运算符的优先数高于栈顶运算符，则进栈；5）否则，退出栈顶运算符发送给后缀式；6）“（”对它之前后的运算符起隔离作用,”）”可视为自相应左括弧开始的表达式结束标志从原表达式求得后缀式的规律为：表达式的起止符号例3编写算法，用栈实现表达式3*（7–2）求值。(表达式求值是栈应用的典型例子,见P52)注：本例采用

“算符优先法”。一个算术表达式是由操作数（x，y，z…）和算符（*，/，+，-，（，），#）组成.教材P53中表3.1给出了算符之间的优先级专为计算机处理而设计的表!(1)

表达式求值必须满足算术四则运算规则：

a.从左算到右

b.先乘除，后加减

c.先括号内，后括号外表达式求值过程----机内运算示意图OPTROPNDINPUT#3*（7–2）#top3top#*(←top7-2←top7-255*3153元素退栈：2,-,7;计算:a,thata,b=7-2=5将结果压入OPND栈且运算符‘)’保留，继续与下一个栈顶元素比较！(2)算法思想：1）首先置操作数栈OPND为空栈，表达式的起始符#为运算符栈OPTR的栈底元素；2）依次读入表达式中的每个字符，若运算符是‘#’或栈顶是‘#’，结束计算，返回OPND栈顶值。

if（是操作数）→则PUSH（OPND，操作数）；

if（是运算符）→则与OPTR栈顶元素进行比较，按优先级(规定详见P53表3.1）进行操作；为了实现算符优先算法，可以设定两个工作栈：OPND—存放操作数或运算结果，OPTR—存放运算符号。3）直到整个表达式求值完毕（当前读入的字符和OPTR栈的栈顶元素均为#

）

if栈顶元素<输入算符，则算符压入OPTR栈，并接收下一字符

if栈顶元素=运算符但≠‘#’，则脱括号(弹出左括号)并收下一字；

if栈顶元素>运算符，则退栈、按栈顶计算，将结果压入OPND栈。且该未入栈的运算符要保留，继续与下一个栈顶元素比较！问：教材P53表3.1中，1和2哪个对应栈顶元素，哪个对应键盘输入值？答：根据P53Precede()函数可知，1对应栈顶元素由表3.1可看出，右括号)

和井号

#

作为2时级别最低；由c规则得出：*，/，+，-为1时的优先权低于‘（’，高于‘）’由a规则得出：‘（’=‘）’表明括号内的运算已完成；‘#’=‘

#’表明表达式求值完毕。附：表达式求值过程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3*（7–2）StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);