数据结构导论 第3章 栈、队列和数组ppt课件.ppt

《数据结构导论 第3章 栈、队列和数组ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈、队列和数组栈和队列是重要的线性结构，实质上是操作受限的线性表。通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列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栈和队列是两种常用的数据类型3.1.1　栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端(表尾)进行。进行插入和删除的一端是浮动端，通常被称为栈顶(top)，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底

2、(bottom)。当表中没有元素时称为空栈。我们经常将栈用下图的形式描述S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。举例1：家里吃饭的碗。举例2：在建筑工地上使用的砖块栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）-----栈的结构特征进栈出栈下面我们先给出栈结构的基本操作：（1）初始化栈InitStack(&S)（2）入栈Push(＆S,x)（3）出栈Pop(&S,&x)（4）获取栈顶元素内容GetTop(S,＆e)（5）判断栈是否为空EmptyStack(S)（6）清空栈　ClearStack(&S)（7）返回栈的长度　S

3、tackLength(S)栈类型的存储实现顺序实现------顺序栈链接实现------链栈3.1.2栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。可以用一维数组表示一个栈。用起始端作为栈底，它是固定的。栈顶位置是随着进栈和退栈操作而变化的，故需用一个指针top来标记当前栈顶元素下标值。顺序栈类型定义如下所示：#definesqstack_maxsize6typedefstructsqstack{datatypedata[sqstack_maxsize];inttop;}SqStackTp;//存放栈中数据元素的存储单元/

4、/栈的最大数据元素数目//栈顶指针,指示栈顶元素下标值top初值为-1，每插入一个元素增1，始终指向栈顶元素。栈空：top==-1；栈満：top==sqstack_maxsize–1；top43210Atop43210EDCBAtop43210基本操作在顺序栈上析实现(1)初始化：使栈为空-----栈顶元素下标初始化为0intInItStack(SqStackTp*sq){sq->top=-1;return(1);}(4)判栈空:若栈为空则让函数返回1，否则返回0intEmptyStack(SqStackTpsq){if(sq.top==-1)return1;elseret

5、urn0;}栈空标志：top==-1(5)取栈顶元素intGetTop(SqStacksq,datatype*x){if(EmptyStack(sq)){printf(“Stackisempty”);return0;}else*x=sq.data[sq.top];return1;}栈顶元素下标：sq.top栈顶元素的表示：sq.data[sq.top](2)进栈:在栈顶插入一个值为X的元素intPush(SqStackTp*sq,DataTypex){if(sq->top==sqstack_maxsize-1){printf(“栈已满，无法操作!”)；return0;}el

6、sesq->data[++sq->top]=x;return1;}验满栈顶下标加1(top++)在栈顶插入新的元素算法步骤：sq->top++;sq->data[sq->top]=x;Atop543210(3)退栈:删除栈顶元素intPop(SqStackTp*sq,datatpye*x){if(EmptyStack(*sq)){printf(“Stackisempty”);return0;}else*x=sq->data[sq->top--];return1}取出栈顶元素用参数返回栈顶下标减1(top--)*x=sq->data[sq->top];sq->top--;At

7、op543210BC顺序栈操作总结由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。3.1.3栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端将单链表的头指针作为栈顶