VC编程教程 第3章 栈和队列

《VC编程教程 第3章 栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列本章主要介绍以下内容：栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例[本章学习要求]掌握：栈的基本概念、存储结构以及入栈、出栈等基本操作。掌握：在处理实际问题中如何运用栈特点解决问题。了解：栈在递归实现过程中作用。掌握：队列的基本概念、存储结构和入队、出队操作等基本操作。了解：队列在迷宫问题求解中的作用，以及如何运用队列解决实际问题。栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈（stack）3.2栈的应用举例3.3队列3.4队列应用举例3.1.1栈的定义定义：限定仅在表尾进行插入

2、或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)3.1栈（stack）栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。栈结构的基本操作：（1）初始化

3、栈InitStack(S)（2）入栈Push(S,data)（3）出栈Pop(S,data)（4）获取栈顶元素内容GetTop(S,data)（5）判断栈是否为空StackEmpty(S)1.顺序栈：用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。top=-1123450栈空栈顶指针top,指向实际栈顶位置，初值为-1进栈栈满设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)top123450ABCDEFtoptoptoptoptoptop出栈1234

4、50ABCDEFtoptoptoptoptoptop栈空3.1.2栈的存储实现和运算实现存储结构的实现#defineMAXSIZE100typedefstruct{datatypedata[MAXSIZE];inttop;}SeqStack,*PSeqStack;运算实现(1)初始化空栈(2)判栈空(3)入栈(4)出栈(5)取栈顶元素S->top=-1123450栈空S->top123450进栈xS->topS->data[s->top]结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但

5、栈容量难以扩充的弱点仍就没有摆脱。若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。2.链栈^图3-3栈的链式存储结构在C语言中可用下列类型定义实现：结点结构为：typedefstructnode{datatypedata;structnode*next;}StackNode,*PS

6、tackNode;typedefstruct{PStackNodetop;}LinkStack,*PLinkStack;PLinkStackS;S=(PLinkStack)malloc(sizeof(LinkStack));下面我们将给出链栈各项基本操作的算法。1.初始化栈SPLinkStackInit_LinkStack（void）{/*初始化链栈，入口参数：空，返回值：链栈指针，NULL表示初始化失败*/PLinkStackS;S=(PLinkStack)malloc(sizeof(LinkStack));if(S)S->top=NULL;ret

7、urn(S);}intLinkStackPush_LinkStack（PLinkStackS,ElementTypex）{/*进栈，入口参数：链栈指针，进栈元素空，返回值：1入栈成功，0失败*/PStackNodep;p=(PStackNode)malloc(sizeof（StackNode）);if(!p){printf(“内存溢出”);return(0);}p->data=x;p->next=S->top;S->top=p;return(1);}^…...栈底toptopxp2.入栈intPop_LinkStack(PLinkStackS,Dat

8、aType*x){/*出栈，返回值：1表示出栈成功，0表示失败,*x保存被删除的元素值*/PStackNod