[计算机软件及应用]栈和队列

《[计算机软件及应用]栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列本章主要介绍以下内容：栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例退出3.1栈3.2队列3.1栈3.1.1栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图3-1的形式描述：a1,a2,a3,...,an插入和删除端图3-1结论：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若

2、一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。　　　操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。　　　操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。　　　操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。　　　

3、操作结果：返回栈S中元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。　　　操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。　　　操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。　　　操作结果：删除S的栈顶元素，并用e返回其值。3.1.2栈的顺序存储和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。　　和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，base为这个存储空间的基地址，也即一维数组的地址。　　从名称来讲，“栈顶指针”意为指示栈顶元素在栈中的位置，

4、但它的值实际是栈中元素的个数，和顺序表中的length值的意义相同。　　为了应用方便，这个“最大空间的容量”应由使用这个顺序栈的程序员决定，它的默认值和顺序表的默认值相同。一、顺序栈类型的定义#defineSTACKSIZE10structstack{inttop;//栈顶指针intitems[STACKSIZE];};基本操作算法：在此只给出其中5个函数的定义。1.初始化栈SvoidInItStack(STACK*S){s->top=0;}2.入栈voidPush(STACK*S,StackEntryitem){if(S->top==MAX_STACK)exit(“Stackisfu

5、ll”);else{S->items[S->top]=item;S->top++;}}3.出栈voidPop(STACK*S,StackEntry&item){if(StackEmpty(S))exit(“Stackisempty”);elseitem=S->items[S->top--];}4.获取栈顶元素内容voidGetTop(STACK*S,StackEntry&item){if(StackEmpty(S))exit(“Stackisempty”);elseitem=S->items[S->top];}5.判断栈S是否为空intStackEmpty(STACK*S){if(S->

6、top==0)returnTRUE;elseFALSE;}6.判断栈S是否为满intisfull(STACK*S){if(S->top>=STACKSIZE)returnTRUE;elseFALSE;}结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。3.1.3栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3-3所示。由于栈的插入删除操作只能在一端进行，而对于单链表

7、来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。^top图3-3栈的链式存储结构在C语言中可用下列类型定义实现：typestructnode{//链栈的结点结构StackTypedata;//栈的数据元素类型structnode*next;//指向后继结点的指针}NODE;typedefstructstack{NODE*top;}STACK;下面我们将给出链栈各项基