Ch3.栈和队列-栈.ppt

《Ch3.栈和队列-栈.ppt》由会员分享，可在线阅读，更多相关《Ch3.栈和队列-栈.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第第第三三三三章章章章 栈和队列栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 顺序栈 3.1.3 链栈 本章节的基本内容是：本章节的基本内容是：1 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出（LIFO）或下推表。3.1.1 栈的定义及基本运算2栈的

2、逻辑结构栈的逻辑结构空栈：不含任何数据元素的栈。（a1,a2,an）栈：限定仅在表尾进行插入和删除操作的线性表。栈顶栈顶栈底栈底允许插入和删除的一端称为栈顶，另一端称为栈底。3a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的示意图栈的示意图4栈的操作特性：栈的操作特性：后进先出后进先出a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈的示意图栈的示意图5例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依

3、次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶 情况情况1：栈的逻辑结构栈的逻辑结构6栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序列：出栈序列：c、b、a例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 情况情况1：7栈底栈底栈顶栈顶ab栈顶栈顶出栈序列：出栈序列：b 情况情况2：例：有三个元素按例

4、：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构8栈底栈底a出栈序列：出栈序列：b出栈序列：出栈序列：b、c出栈序列：出栈序列：b、c、ac栈顶栈顶栈顶栈顶注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允

5、许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 情况情况2：9栈的抽象数据类型定义栈的抽象数据类型定义 ADT StackData 栈中元素具有相同类型及后进先出特性，栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitStack(S)构造一个空栈 Push(S,x)在栈顶插入一个元素x,如果插入不成功，抛出异常;否则栈顶增加了一个元素。10Pop（S,e）删除栈顶元素,如果删除成功，返回被删元素值e，否则，抛出异常;否则栈减少了一个元素.Stacktop(S,e)读取当前的栈顶元素,若栈不空，返回当前的栈顶元素值

6、e,栈不变.Stackempty(S)判断栈S是否非空，空返回1，非空返回0。ADT Stack栈的抽象数据类型定义栈的抽象数据类型定义 11 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。3.1.2 顺序栈12栈的顺序存储结构及实现栈的顺序存储结构及实现 顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺

7、序存储？如何改造数组实现栈的顺序存储？0 1 2 3 4 5 6 7 8a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。top3.1.2 顺序栈13出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top=-1 0 1 2 3 4 5 6 7 8a1topa2topa3top栈满：栈满：top=MAX_SIZE-1栈的顺序存储结构及实现栈的顺序存储结构及实现 3.1.2 顺序栈14因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#define Sta

8、ckSize 100 typedef char datatype;typedef struct datatype datastacksize;int top;seqstack;顺序栈的类型定义15 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将stop加1，退栈时需将stop 减1。因此，stoptop=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。为了避免溢出，在对栈进行进栈和出展运算前，应分别判断栈是否已满或者是否已空

9、。161、置空栈 void initstack(seqstack*s)stop=-1;/initstack172、判断栈空 int stackempty(seqstack*s)return(stop=-1);/stackempty183、判断栈满 int stackfull(seqstack *s)return(stop=stacksize-1);19 4、进栈 void push(seqstack *s，datatype x)if(stackfull(s)error(“stack overflow”);sdata+stop=x;/push205、退栈 datatype pop(seqstac

10、k*s)if(stackempty(s)error(“stack underflow”);x=sdatatop;stop-;return(x)/pop 216、取栈顶元素 Datatype stacktop(seqstack *s)if(stackempty(s)error(“stack is enpty”);return sdatastop;/stacktop 22栈的链接存储结构及实现栈的链接存储结构及实现 链栈：链栈：栈的链接存储结构栈的链接存储结构firsta1a2anai链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈

11、顶？将哪一端作为栈顶？将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。3.1.3 链栈23栈的链接存储结构及实现栈的链接存储结构及实现 栈顶栈顶栈底栈底链栈：链栈：栈的链接存储结构栈的链接存储结构topanan-1a1firsta1a2anai两种示意图在内存中两种示意图在内存中对应同一种状态对应同一种状态topa1an-1an栈顶栈顶栈底栈底3.1.3 链栈24栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的

12、类型说明如下：typedef struct stacknode datatype data struct stacknode*next stacknode,*linkstack;3.1.3 链栈25 Void initstack(linkstack p)/初始化栈 ptop=null;int stackempty(linkstack p)/判断栈是否空 return(ptop=null);/stackempty 26Void push(linkstack p,datatype x)stacknode*q q=(stacknode*)malloc(sizeof(stacknode);qdata=

13、x;qnext=ptop;ptop=q;/push27Datatype pop(linkstack p)datatype x;stacknode *q=ptop;if(stackempty(p)error(“stack underflow.”);x=qdata;ptop=qnext;free(q);return x;/pop28 datatype stacktop(linkstack p)if(stackempty(p)error(“stack is empty.”);return ptopdata;/stacktop29栈通常采用的两种存储结构是:顺序存储结构和链接存储结构（或顺序栈和链栈）

14、.顺序表判定栈空的条件是栈顶指针top=-1;链栈判定栈空的条件是top=NULL.顺序表判定栈满的条件是栈顶指针top是数组的长度;链栈判定栈满的条件是内存无可用空间.顺序栈和链栈的比较顺序栈和链栈的比较30顺序栈和链栈的比较顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针间时才会出现栈满，但是每个元素都需要一个指针域，从而产生

15、了结构性开销。域，从而产生了结构性开销。总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用较大时，用链栈是适宜的，反之，应该采用顺序栈。链栈是适宜的，反之，应该采用顺序栈。31 作业1.设有一个空栈，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是()。2.若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（）。3.在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。4.从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行()。32