数据结构(第二版)课件 包振宇 第三章 栈和队列.ppt

《数据结构(第二版)课件 包振宇 第三章 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列3.1堆栈3.2队列3.3典型例题3.1堆栈3.1.1堆栈的定义和基本操作栈（stack）是一种特殊的线性表，这种表只能在其一端（称为栈顶top）进行插入和删除操作,如图2-4-1所示。栈的概念来自存货的堆栈，存货时一件一件往上堆，每次取货时都有只能从上面取。栈的存取特征是后进先出（LastInFirstOut,缩写为LIFO）。栈顶将随着栈中元素的增减而浮动，通过栈顶指针指明当前栈顶元素位置。栈的固定端称为栈底（bottom），栈底指针并不移动。栈的基本操作包括：创建一个栈进栈栈顶出栈进栈（push），出栈（pop）读取栈顶元素，判栈空，栈清

2、空（初始化），求当前栈中元素的个数，撤消一个栈等栈底3.1.2顺序存储栈可用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top（习惯称为栈顶指针，注意与指针变量的区别），top指出栈顶表元素在数组中的下标。当栈为空时，top=0;栈满时，top=MAXN(数组元素个数),如图2-4-1所示。顺序存储栈示意图MAXN-1MAXN-1top......11top->00栈空栈满1、顺序存储栈的进栈操作(1)顺序存储栈的进栈操作(2)函数如下：intpush(NODEstack[],intmaxn,inttop,NODEx)/

3、*设栈点的数据类型为NODE，栈空间最多能存maxn个结点*/{if(top>=maxn)return1;/*栈满，进栈失败返回*/stack[top]=x;/*完成进栈运算*/++top;return0;/*进栈成功，返回0*/}2、顺序存储栈出栈操作(1)顺序存储栈出栈操作(2)函数如下：intpop(NODEstack[],inttop,NODEcp){if(top==0)return1;/*栈空，出栈失败返回*/--top;cp=stack[top];/*完成出栈运算*/return0;/*出栈成功，返回*/}3.1.3链式存储栈栈也可以用链表实现，

4、用链表实现的栈称为链式栈。链表的第一个元素是栈顶结点，链表的末尾元素是栈底结点，链表的首表指针是栈顶指针top,top为null的空链表是空栈。设栈结点类型为：typedetstructnode{NODEdata;/*栈元值，某种NODE类型*/structnode*link;}LNODE;(一)链式存储栈的进栈函数示意图toptop=p②①p->link=topp4X52null函数定义函数如下：voidL_push(NODEx,LNODE*top)/*设栈结点的数据类型为NODE*/{LNODE*p=(LNODE*)malloc(sizeof(LNODE

5、));p->data=x;p->link=top;top=p;}（二）链接存储栈的出栈函数示意图Topp452Null函数定义intL_pop(NODE*cp,LNODE*top)/*设栈结点的数据类型为NODE*/{LNODE*p=top;if(top==NULL)return1;/*空栈*/*cp=p->data;top=p->link;free(p);return0;/*出栈成功*/}3.2队列一、队列定义、队列是只允许在一端进行插入，另一端正进行删除的线性表，如图3-7所示。出队q0q1…qiqi+1…qn-1进队队首队尾图3-7队列示意图队列中允许

6、删除运算的一端称队首，允许插入运算的一端称为队尾。习惯称在队列中插入结点操作为进队，队列中删除结点的操作为出队。若有队Q=(q0,q1,…qn-1),则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所以队列具有先进先出（FirstInFirstOut简称FIFO）的特性。队列的基本操作包括：创建一个队列，入列，出队，读取队首元素，判队空，请队列空，求当前队列中的元素个数，撤消一个队列等。3.2.1顺序存储队列可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需一个游标变量front（习惯上称为头指针），为了指明当前执行

7、进队运算的队尾位置，需要一个游标变量rear（习惯上称为尾指针）。开始时，让队列front度rear都指向数组的前端，这是一个空队列。在队列未满情况下，队列可执行进队运算。进队时，首先让rear加1,变为指向队列新结点的存放下标，然后将新结点送到由rear所指的数组元素中。队列非空时，可执行出队运算。出队时，首先把front所指的队列首结点送到接受结点的变量中，然后让front加1，使front指向新的队首结点。出入队列的状态示意图环形队列(1)若用有MAXN个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端

8、空着，而队列空间已用完的情况。一种可行的解决方法是当