资源描述：
《数据结构第3章 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、数据结构第3章栈和队列什么是栈和队列？？栈和队列的基本运算栈和队列的应用1数据结构栈栈(Stack)：是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端（尾端）进行。a1a2an-1an…栈顶栈底假设栈S=(a1，a2，a3，…an)，栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素，即an。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表。（LIFO）。2数据结构例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。例2：在建筑工地上，使用的砖
2、块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。3数据结构栈的抽象数据类型定义ADTStack{数据对象:D={ai
3、ai(-ElemSet,i=1,2,...,n,n>=0}数据关系:R1={
4、ai-1,ai(-D,i=2,...,n}基本操作：InitStack(&S)构造一个空栈SDestroyStack(&S)栈S存在则栈S被销毁ClearStack(&S)栈S存在则清为空栈StackEmpty(S)栈S存在则返回TRUE,否则FALSEStackLength(S)栈S存在则返回S的元素个数,即栈的长度GetTop(S,&e)栈S存在且非空则返回S的栈顶
5、元素Push(&S,e)栈S存在则插入元素e为新的栈顶元素Pop(&S,&e)栈S存在且非空则删除S的栈顶元素并用e返回其值StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用visit()一旦visit()失败,则操作失败}ADTStack4数据结构栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类似于顺序表，我们可用如下的结构来顺序地定义栈。#defineSTACK_INIT_SIZE100//存储空间的初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruc
6、t{SElemType*base;//存储空间基址inttop;//栈顶指针（栈的长度）intstacksize;//当前分配的存储容量（以一数据元素存储长度为单位）}SqStack;栈的顺序表示和实现5数据结构顺序栈的建立StatusInitStack_Sq(SqStack&S){//构造一个空的栈S。S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=0;//空栈长度为0S.listsize=LIST_INIT_SIZE;//初始存储容量re
7、turnOK;}//InitStack_Sq此算法的时间复杂度为O(1)。顺序栈典型操作的实现6数据结构线性栈的销毁voidDestroyStack(SqStack&S){//释放顺序栈S所占存储空间if(S.base)free(S.base);S.top=0;S.stacksize=0;}//DestroyStack_Sq此算法的时间复杂度为：O(1)线性栈的清空voidClearStack(SqStack&S){//将顺序栈S的长度置0S.top=0;}//ClearStack_Sq此算法的时间复杂度为：O(1)7数据结构判断线性栈是否为空intStackEmpty(SqStackS){i
8、f(S.length==0)returnTRUE;elsereturnFALSE;}此算法的时间复杂度为：O(1)求线性栈S的长度intStackLength(SqStackS){returnS.top;}此算法的时间复杂度为：O(1)8数据结构获取线性栈S中的栈顶元素的内容intGetTop(SqStackS,SElemType*e){if(S.top==0)returnERROR;*e=*(S.base+S.top–1);returnOK;}此算法的时间复杂度为：O(1)9数据结构插入新的栈顶元素StatusPush_Sq(SqStack&S,ElemTypee){//在顺序栈的栈顶插入新
9、的元素eif(S.top>=S.stacksize){//当前存储空间已满，增加容量newbase=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!newbase)returnERROR;//存储分配失败S.base=newbase;//新基址S.stacksize+=STACKINCRE
