第03章_栈和队列A.ppt

《第03章_栈和队列A.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、。3.存储结构4.运算规则5.实现方式2.逻辑结构即栈顶基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶/top;表头(即a1端)称为栈底/base例如：栈S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！4a1a2an入栈出栈栈顶top栈底bottom栈的示意图．．．例1（严题集3.1）一个栈的

3、输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？5可以通过穷举所有可能性来求解：①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，b6[解答]A）、D）可以，B）、C）不行。讨论：有无

4、通用的判别原则？即对于输入序列1，2，3，不存在输出序列3，1，2有！若输入序列是…,Pj…Pk…Pi…(Pj

5、n)a1a2……an顺序栈Sai……Q2：顺序表和顺序栈的操作有何区别？8表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):S[top++]=an+1弹出(POP):e=S[--top]低地址高地址S[i]a1a2aian……顺序表S……an+1以线性表S=(a1,a2,….,an-1,an)为例栈底base栈顶top前提：一定要预设栈顶指针top栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize;a1a2……an顺序栈Sai……低地

6、址高地址an+1栈底base栈顶top9若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的堆栈:入栈口诀：堆栈指针top“先压后加”:S[top++]=an+1出栈口诀：堆栈指针top“先减后弹”:e=S[--top]Q3：什么叫“向上生成”的栈？“向下生成”又是何意？10栈的基本操作(教材p.44--45)：11InitStack(&S):DestroyStack(&S):ClearStack(&S):StackEmpty(S):StackLength(S):

7、GetTop(S,&e)：Push(&S,e)：Pop(&S,&e)：……构造一个空栈销毁栈S将S清为空栈若栈S为空栈，返回True;否则返回False返回栈S的元素个数，即栈的长度用e返回栈S的栈顶元素插入元素e为新的栈顶元素删除S的栈顶元素，并用e返回其值……#defineSTACK-INIT-SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//栈底指针:构造之前和销毁之后，//base的值为NULLSEl

8、emType*top;//栈顶指针intstacksize;//当前分配的空间}SqStack;12顺序栈的存储表示(教材p.46)：顺序栈的入栈操作3.1栈13低地址L高地址MtopbaseS.top=S.baseAtopbase*S.top=A;S.top++;Push(&S,