第三章 栈和队列
本章介绍的是 栈 和 队列 的逻辑结构定义及在两种存储结构(顺序存储结构和链式存储结构)上如何实现 栈和队列的基本运算 本章的 重点 是掌握栈和队列在两种存储结构上实现的基本运算 难点 是循环队列中对边界条件的处理
栈的逻辑结构存储结构及其相关算法( 综合应用 ):
栈 的逻辑结构和我们先前学过的 线性表 相同如果它是非空的则有且只有一个 开始结点 有且只能有一个 终端结点 其它的结点前后所相邻的也只能是一个结点( 直接前趋 和 直接后继 )但是栈的运算规则与线性表相比有更多的限制 栈(Stack) 是 仅限制在表的一端进行插入和删除运算的线性表 通常称插入删除这一端为 栈顶 另一端称为 栈底 表中无元素时为 空栈 栈的修改是按后进先出的原则进行的我们又称栈为LIFO表(Last In First Out)
栈的基本运算有六种
构造空栈InitStack(S)
判栈空: StackEmpty(S)
判栈满 StackFull(S)
进栈 Push(Sx)可形象地理解为压入这时栈中会多一个元素
退栈 Pop(S) 可形象地理解为弹出弹出后栈中就无此元素了
取栈顶元素StackTop(S)不同与弹出只是使用栈顶元素的值该元素仍在栈顶不会改变
由于栈也是线性表因此线性表的存储结构对栈也适用通常栈有 顺序栈 和 链栈 两种存储结构这两种存储结构的不同则使得实现栈的基本运算的算法也有所不同
我们要了解的是在 顺序栈 中有 上溢 和 下溢 的概念顺序栈好比一个盒子我们在里头放了一叠书当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算哼哼)这时就是上溢 上溢也就是栈顶指针指出栈的外面 显然是出错了反之当栈中已没有书时我们再去拿看看没书把盒子拎起来看看盒底还是没有这就是 下溢 下溢本身可以表示栈为空栈 因此可以用它来作为控制转移的条件
链栈 则没有上溢的限制它就象是一条一头固定的链子可以在活动的一头自由地增加链环(结点)而不会溢出 链栈不需要在头部附加头结点 因为栈都是在头部进行操作的如果加了头结点等于要在头结点之后的结点进行操作反而使算法更复杂所以只要有链表的头指针就可以了
以上两种存储结构的栈的基本操作算法是不同的我们主要 要学会进栈和退栈的基本算法以解决简单的应用问题
队列的逻辑结构存储结构及其相关算法( 综合应用 )
队列(Queue念Q音) 也是一种运算受限的 线性表 它的运算限制与栈不同是两头都有限制 插入只能在表的一端进行(只进不出)而删除只能在表的另一端进行(只出不进) 允许删除的一端称为 队头(rear) 允许插入的一端称为 队尾 (Front) 队列的操作原则是先进先出的所以队列又称作 FIFO 表(First In First Out)
队列的基本运算也有六种
置空队 InitQueue(Q)
判队空 QueueEmpty(Q)
判队满 QueueFull(Q)
入队 EnQueue(Qx)
出队 DeQueue(Q)
取队头元素 QueueFront(Q)不同与出队队头元素仍然保留
队列 也有顺序存储和链式存储两种存储结构前者称 顺序队列 后者为 链队
对于顺序队列我们要理解 假上溢 的现象
我们现实中的队列比如人群排队买票队伍中的人是可以一边进去从另一头出来的除非地方不够总不会有溢出的现象相似地当队列中元素完全充满这个向量空间时再入队自然就会上溢如果队列中已没有元素那么再要出队也会下溢
那么假上溢就是怎么回事呢?
因为在这里我们的队列是存储在一个向量空间里在这一段连续的存储空间中由一个队列头指针和一个尾指针表示这个队列当头指针和尾指针指向同一个位置时队列为空也就是说 队列是由两个指针中间的元素构成的 在队列中入队和出队并不是象现实中元素一个个地向前移动走完了就没有了而是 指针在移动 当出队操作时头指针向前(即向量空间的尾部)增加一个位置入队时尾指针向前增加一个位置在某种情况下比如说进一个出一个两个指针就不停地向前移动直到队列所在向量空间的尾部这时再入队的话尾指针就要跑到向量空间外面去了仅管这时整个向量空间是空的队列也是空的却产生了上溢现象这就是假上溢
为了克服这种现象造成的空间浪费我们引入 循环向量 的概念就好比是把向量空间弯起来形成一个头尾相接的环形这样当存于其中的队列头尾指针移到向量空间的上界(尾部)时再加的操作(入队或出队)就使指针指向向量的下界也就是从头开始这时的队列就称 循环队列
通常我们应用的大都是循环队列由于循环的原因光看头尾指针重叠在一起我们并不能判断队列是空的还是满的这时就需要处理一些 边界条件 以区别队列是空还是满方法至少有三种一种是另设一个布尔变量来判断(就是请别人看着是空还是满由他说了算)第二种是少用一个元素空间当入队时先测试入队后尾指针是不是会等于头指针如果相等就算队已满不许入队第三种就是用一个计数器记录队列中的元素的总数这样就可以随时知道队列的长度了只要队列中的元素个数等于向量空间的长度就是队满
以上是 顺序队列 我们 要掌握相应算法以解决简单应用问题
队列的链式存储结构称为链队列一个链队列就是一个操作受限的单链表为了便于在表尾进行插入(入队)的操作在表尾增加一个尾指针 一个链队列就由一个头指针和一个尾指针唯一地确定 链队列不存在队满和上溢的问题在链队列的出队算法中要 注意 当原队中只有一个结点时出队后要同进修改头尾指针并使队列变空
栈和队列的应用( 领会 )
教材中举了几个例子对于我们初学者来说看上去比较繁我们只要掌握一点那就是对于什么情况下用栈和队列作为解决问题的数据结构
判断的要点就是 如果这个问题满足 后进先出(LIFO) 的原则就可以使用 栈 来处理如果这个问题满足 先进先出(FIFO) 的原则就可以使用 队列 来处理
比如简单的说有一个数组序列我们输入时按顺序输入但是输出时需要逆序输出那么它就可以利用栈来处理把这个数组存入一个栈中就可以容易地按逆序输出结果了
第三章 栈和队列 复习要点
本章要点是
栈的定义其逻辑结构特征栈的六种基本运算栈的上溢下溢的概念
队列的逻辑结构队列的基本运算;循环队列的边界条件处理;
以上各种基本运算算法的实现算法的简单应用
可能出的题型有填空选择简答算法等如:
栈和队列是的线性表;
有一栈元素ABCD只能依次进栈 则出栈序列中以下哪个是不可能得到的()
A DCBA
B CBAD
C ABCD
D DCAB
试写出队列中的出队算法;
等等
