资源描述：
《栈的定义、表示、实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程的内容：13.1栈（Stack）3.2队列（Queue)第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式2通常称，栈和队列是限定插入和删除操作只能在表的“端点”进行的线性表。线性表(L)栈(S)队列(Q)Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型31.定义3.1栈限定只能
2、在表尾进行插入和删除运算的线性表。表的尾端称为栈顶，表头端称为栈底。例如：栈S=(a1,a2,a3,……….,an-1,an)an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。一、概念：4想一想：要从栈中取出a1，应当如何操作？5与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实
3、现依顺序栈或链栈的存储结构有别而不同。3.存储结构：4.运算规则：5.实现方式：2.逻辑结构：6讨论1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：任意位置存取运算规则：后进先出(LIFO)“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)7二、栈的抽象数据类型定义ADTStack{数据对象：D
4、＝{ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack8（1）初始化栈InitStack(&S)（2）入栈Push(&S,e)（3）出栈Pop(&S,&e)（4）获取栈顶元素内容GetTop(S,&e)（5）判断栈是否为空StackEmpty(S)基本操作:建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。9#defineSTACK_INIT_SIZE100;//存储空
7、间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间}SqStack;三、栈的表示和实现1.顺序栈//-----栈的顺序存储表示-----10栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize;a1a2……an顺序栈Sai……低地址高地址栈底base栈顶top如图：to
8、p的初值指向栈底，在非空栈中top总是指向栈顶元素的下一个位置上。为浮动端。base始终指向栈底的位置。为固定端。11a1a2……an顺序栈Sai……表头表尾低地址高地址写入：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讨论2：顺序表和顺序栈的操作有何区别？12StatusInitStack(SqStack&S
9、){//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;//空栈S.stacksize=STACK_INIT_SIZE;returnOK;}//-----基本操作的算法描述-----顺序栈的建栈操作——构造空栈S13顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：Push(B);Push(C);Push(D)
10、;topbasetoptoptop低地址LPush(A);高地址MBCD顺序栈入栈函数Push（&S,e）入栈口诀：栈顶指针top“先压后加”S[top++]=e14StatusPush(SqStack&S,SElemTypee){//若栈不满，则将元素e插入栈顶，并返回OK;否则返回OVERFLOWif(S.top-S.base
