[理学]第4章 栈和队列

《[理学]第4章 栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章栈和队列4.1栈4.2栈的顺序存储结构和操作实现4.3栈的链接存储结构和操作实现4.4栈的简单应用举例4.5算术表达式的计算4.6栈与递归4.7队列4.8队列应用举例1.定义4.1栈与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。3.存储结构4.运算规则5.实现方式2.逻辑结构限定只能在表的一端进行插入和删除运算的线性表。即栈顶基本操作有：建栈、判断栈满或栈空、入栈、出栈、

2、读栈顶元素值，等等。栈的示意图a1a2······an-1an入栈出栈topbottom栈底栈顶栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶/top;表头(即a1端)称为栈底/base例如：栈S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！Q1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。

3、与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)a1a2……an顺序栈Sai……Q2：顺序表和顺序栈的操作有何区别？表头表尾低地址高地址写入：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)

4、为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize;a1a2……an顺序栈Sai……低地址高地址an+1栈底base栈顶topQ3：为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。下面用4个例子来帮助理解堆栈：voidtest(int&sum){intx;Cin>>x;if(x==0)sum=0;else{test(sum);sum+=x;}cout<

5、

6、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。例3：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可。例4：设依次进入一个栈的元素序列为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…(

7、Pj

8、】检查括号配对。【例4-3】把十进制整