数据结构C语言版(栈和队列).ppt

《数据结构C语言版(栈和队列).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作：（1）初始化栈InitStack(S)（2）入栈Push(S,item)（3）出栈Pop(S,item)（4）获取栈顶元素内容GetTop(S,item)（5）判断栈是否为空StackEmpty(S)3.1.2栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#defineMAX_STACK10//栈的最大数据元素数目typedefstr

3、uctstack{StackEntryitem[MAX_STACK];//存放栈中数据元素的存储单元inttop;//栈顶指针}STACK;基本操作算法：1.初始化栈SvoidInItStack(STACK*S){s->top=-1;}2.入栈voidPush(STACK*S,StackEntryitem){if(S->top==MAX_STACK-1)exit(“Stackisfull”);elseS->item[++S->top]=item;}图3-23.出栈voidPop(STACK*S,StackEntry*item){if(StackEmpty(*S))exit(“Stackis

4、empty”);else*item=S->item[S->top--];}4.获取栈顶元素内容voidGetTop(STACKS,StackEntry*item){if(StackEmpty(S))exit(“Stackisempty”);else*item=S.item[S.top];}5.判断栈S是否为空intStackEmpty(STACKS){if(S.top==-1)returnTRUE;elseFALSE;}结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。3.1.3栈的链式存储若

5、是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3-3所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。^top图3-3栈的链式存储结构在C语言中可用下列类型定义实现：typestructnode{//链栈的结点结构StackEntryitem;//栈的数据元素类型structnode*next;//指向后继结点的指针}NODE;typedefstructsta

6、ck{NODE*top;}STACK;下面我们将给出链栈各项基本操作的算法。1.初始化栈SvoidInitStack(STACK*S){S->top=NULL;}2.入栈voidPush(STACK*S,StackEntryitem){p=(NODE*)malloc(sizeof(NODE));if(!p)exit(OVERFLOW);else{p->item=item;p->next=S->top;S->top=p;}}3.出栈voidPop(STACK*S,StackEntry*item){if(StackEmpty(*S))exit(“Stackisempty”);else{*ite

7、m=S->top->item;p=S->top;S->top=p->next;free(p);}}4.获取栈顶元素内容voidGetTop(STACKS,StackEntry*item){if(StackEmpty(S))exit(“Stackisempty”);else*item=S.top->item;}5.判断栈S是否空intStackEmpty(STACKS){if(S.top==NULL)returnTRUE;