数据结构：栈的原理与应用

《数据结构：栈的原理与应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构栈的原理与应用第页主要内容栈的定义顺序栈链栈栈的应用举例课堂作业第页栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除1.什么是栈一、栈的定义第页第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，不含元素的栈称为空栈。出栈Pop进栈Push栈顶栈底2、栈的逻辑结构topbottom空栈topbottoman...a2a1第页bottomtopbottomtopAABCDEAB栈操作图示A进栈BCDE进栈EDC出栈CDEtoptoptop栈的特点后进先出LIFO3、入栈与出栈

2、topbottomtopbottomtoptoptop第页4、栈的基本操作初始化IniStack(S):构造一个空栈S，准备存放数据；进栈操作Push(S,x)：将数据元素x插入栈S，使x成为S的栈顶元素；出栈操作Pop(S)：当栈不空时返回栈顶元素为该函数的值，然后删除栈顶元素；取栈顶元素GetTop(S)：当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变；判栈空EmptyStack(S)：若S为空栈则该函数值为1，否则为0。第页栈属于加了限制条件的线性结构；栈是后进先出的线性表；进栈和出栈只能从栈的一个端点进行；栈中的元素个数可以是0，此时

3、是空栈；栈的元素的个数是可以变化的，可以是多个，但不能是无穷多个；每个栈中的元素的类型相同.5、栈的特性第页思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA第页如果是4个元素，那么它不可能的出栈序列有哪些？可能的出栈序列：12431324134221342143231424313241321434214321不可能出现的出栈序列：2413312434124123423142134312第页用一个一维数组和一个整型变量来实现。structstack{datatypearray[ma

4、xlen];inttop;}栈数组array[maxlen]用来存放栈中所有元素；整型变量top的整数值表示栈顶元素在数组array中的位置，也称为栈顶指针。二、栈的顺序存储结构第页约定栈顶指针指向向栈顶元素的位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？顺序栈的图示topMAX-1nn-1n-210anan-1a2a1栈空：栈满：Top=-1Top=maxlen-1二、栈的顺序存储结构（续）第页1)初始化栈viodinitstack(structstacks){s.top=-1;}MAX-1nn-1n-210建立空栈

5、top二、栈的顺序存储结构（续）第页2)进栈操作viodPush(structstacks,datatypex){s.top=s.top+1;s.array[top]=x；}MAX-1nn-1n-210anan-1a2a1x进栈前topx进栈后MAX-1nn-1n-210topxanan-1a2a1第页3）出栈操作intpop(structstacks){return(array[s.top]);s.top--;}出栈操作前MAX-1nn-1n-210anan-1a2a1top出栈操作后MAX-1nn-1n-210anan-1a2a1top第页

6、栈在运算过程中可能发生“溢出”现象：上溢下溢topMAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210top二、栈的顺序存储结构（续）第页顺序栈的不足：存在栈满以后就不能再进栈的问题（这是因为用了定长的数组存储栈的元素）解决方法：使用链式存储结构。二、栈的顺序存储结构（续）第页三、栈的链式存储和实现栈的链式存储结构，也称链栈。其各结点的结构与单链表中的结点结构完全相同。如图所示：在前面学习了线性链表的插入删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法结点结构定义：Typedefstructnode{elemty

7、pedata;structnode*next;}node,*pointer;Datanexts栈顶（单链表的表头）栈底an-1a1an第页(1)初始化栈Voidinitstack（pointers）{s=null;}^s三、栈的链式存储和实现（续）第页Datanexts栈顶栈底an-1a1anDatanext栈顶栈底an-1a1anxps进栈前进栈后(2)进栈第页进栈算法Voidpush(pointers,datatypex){p=(pointer*)malloc(sizeof(node));p->data=x;p->next=s->next;s

8、->next=p;}第页出栈前出栈后Datanext栈顶栈底an-1a1ansDatanextp栈顶栈底an-1a1anxs(3)出栈