数据结构第3章栈和队列

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

1、教学目标1、知识目标1）掌握栈的定义及基本运算；2）掌握顺序栈、链栈基本运算的实现算法。3）掌握队列的定义及基本运算；4）掌握循环队列、链队列基本运算的实现算法。2、能力目标1）具有恰当的选择栈作为数据的逻辑结构、顺序栈，链栈作为数据的存储结构的能力；2）具有恰当的选择队列作为数据的逻辑结构、循环队列、链队列作为数据的存储结构的能力；3）具有应用栈和队列解决实际问题的能力。3、素质目标养成分工合作、团结协作的良好协作精神。3.1栈的定义及基本操作栈是一种特殊的线性表，它的逻辑结构与线性表相同，只是其运算规则较线性表有更多的限制，故又称

2、它为运算受限的线性表。1、栈的定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为退（出）栈。通常插入、删除的这一端称为栈顶，由于元素的进栈和退栈，使得栈顶的位置经常是变动的，因此需要用一个整型量Top指示栈顶的位置，通常称Top为栈顶指针；另一端称为栈底。当表中没有元素时称为空栈，即Top=-1。栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每

3、次删除的总是当前栈中“最新”的元素，即最后插入的元素，而最先插入的是被放在栈的底部，要到最后才能删除。在现实生活中，我们见到的手枪的弹夹就是一个栈，装入子弹时，需要从弹夹的顶部一个个的放入，子弹射出时，需要从弹夹的顶部一个个的射出，最后装入的被最先射出，最先装入的只有到最后才能被射出。栈可以用下图来表示：DCBAtop栈入栈出栈2、栈的基本运算（1）置空栈：InitStack(S)构造一个空栈S。（2）判栈空：StackEmpty(S)若S为空栈，则返回1，否则返回0。（3）判栈满：StackFull(S)若S为满栈，则返回1，否则返

4、回0。（4）进栈：Push(S，x)若栈S不满，则将元素x插入S的栈顶。（5）退栈：Pop(S)若栈S非空，则将S的栈顶元素删去，并返回该元素。（6）取栈顶元素：StackTop(S)若栈S非空，则返回栈顶元素，但不改变栈的状态。3.2顺序栈及基本操作的实现由于栈是运算受限线性表，因此线性表的存储结构对栈也适用，而线性表有顺序存储和链式存储两种，所以，栈也有顺序存储和链式存储两种。1、顺序栈：栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。2、顺序栈的描述3、顺序栈的基本操作设S是SeqStack类型的指针变量。若栈底位置在向量的

5、低端，即S->data[0]是栈底元素。（1）进栈操作进栈时，需要将S->top加1。①S->top==StackSize-1表示栈满②上溢：当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避免。2、顺序栈的描述#defineStackSize100//假定栈空间最多为100个元素typedefcharDataType;//假定栈元素的类型为字符类型typedefstruct{DataTypedata[StackSize];//栈元素定义inttop;//栈指针定义}SeqStack;SeqStack*S

6、;//栈定义8（2）退栈操作退栈时，需将S->top减1。①S->top==-1表示空栈②下溢：当栈空时，做退栈运算所产生的溢出现象称为下溢。顺序栈在进栈和退栈操作时的具体变化情况如下图：4、顺序栈上六种基本运算的算法（1）置栈空（2）判栈空如果栈S为空，则S->top==-1，此时应该返回1，而关系表达式S->top==-1的值为1；如果栈S为非空，则S->top!=-1，此时应该返回0，而关系表达式S->top==-1的值为0，因此，无论怎样只需返回S->top==-1的值。43210-1top(a)栈空A43210-1top(b

7、)A进栈DCBA43210-1top(c)BCD进栈BA43210-1top(c)DC退栈（1）置栈空voidInitStack（SeqStack*S）{//将顺序栈置空S->top=-1;}8（2）判栈空intStackEmpty（SeqStack*S）{returnS->top==-1;}（3）判栈满与判栈空的道理相同，只需返回S->top==StackSize-1。（4）进栈进栈操作需要将栈和进栈元素的值作为函数参数,由于使用栈指针作为函数参数,对栈进行操作，所以进栈函数不需要有返回值;进栈操作时,需要判断是否栈满,当栈不满时,

8、先将栈顶指针加1,再进栈。（5）退栈退栈操作需要将栈指针作为函数参数，并返回栈顶元素的值,所以函数返回值的类型为DataType；退栈操作时，需要判断是否栈空，当栈不空时，先退栈，再将栈顶指针减1，可以先将栈顶元素的值记