第3章栈和队列 3.栈 1 1. 栈的基本概念 栈(stack)是限定只在表头进行插入(入栈)与删除(出栈)操作的线性表,表头端称为栈 顶,表尾端称为栈底。 a则一般称a1为栈底元素,为栈顶元素, a2,…,设有栈S=(a1,a2,…, n ), an 按a1,an 的 顺序依次进栈,出栈的第一个元素为栈顶元素,也就是说栈是按后进先 出的原则进行进栈和出栈操作,如图1.1所示,所以栈可称为后进先 3. 出(atiisuLIFO)的线性表(简称为LIFO 结构)。 lsnfrtot, 在实际应用中,栈包含了如下基本操作 : 1)intLength()const 初始条件:栈已存在 。 操作结果:返回栈元素个数 。 2)boolEmpty()const 图1.1 栈示意图 3.初始条件:栈已存在。 操作结果:如栈为空,则返回true,否则返回false。 3)voidClear() 初始条件:栈已存在。 操作结果:清空栈。 4)voidTraverse(void(*visit)(constElemType&))const 初始条件:栈已存在。 操作结果:从栈底到栈顶依次对栈的每个元素调用函数(*visit)。 5)boolPush(constElemType&e) 初始条件:栈已存在。 操作结果:插入元素 e 为新的栈顶元素。 6)boolTop(ElemType&e)const 初始条件:栈已存在且非空。 操作结果:用 e 返回栈顶元素。 7)boolPop(ElemType&e) 初始条件:栈已存在且非空。 操作结果:删除栈顶元素,并用 e 返回栈顶元素。 8)boolPop() 初始条件:栈已存在且非空。 操作结果:删除栈顶元素。 ·9· 2. 顺序栈 在顺序实现中,利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素,将数 据类型为ElemType的数据元素存储在数组中,并用count存储数组中存储的栈的实际元 素个数。当count=0时表示栈为空,每当插入新的栈顶元素时,如栈未满,操作成功, count的值将加1。而当删除栈顶元素时,如栈不空,操作成功,并且count的值将减1。 3. 链式栈 链式栈的结构如图1.2所示,入栈和出栈操作都非常简单,一般都不使用头节点直接 3. 实现。 图1.2 链式栈示意图 3. 3.2 队列 1. 队列的基本概念 队列(quu是一种先进先出(isnfrtot,的线性表, ee) frtiisuFIFO) 只允许在一端进行插 入(入队)操作,在另一端进行删除(出队)操作。 在队列中,允许入队操作的一端称为队尾,允许出队 操作的一端称为队头,如图1.3所示。 3. 设有队列q=(a2,…, n 则一般a1称为队头元 a1,), 图1.3.3 队列示意图素。an 称为队尾元素。队列中元(a) 素按a1,a的顺 a2,…, 序入队,同时也按相同的顺序出队。队列的典型应(n) 用是 下的基本操作: 操作系统中的作业排队。在实际应用中,队列包含了如 1)intLength()const 初始条件:队列已存在 。 操作结果:返回队列长度 。 2)boolEmpty()const 初始条件:队列已存在 。 操作结果:如队列为空,则返回true,否则返回false 。 3)voidClear( ) 初始条件:队列已存在 。 操作结果:清空队列 。 4)voidTraverse(void(*visit)(constElemType&))const 初始条件:队列已存在 。 操作结果:依次对队列的每个元素调用函数(*visit) 。 5)boolOutQueue(ElemType&e) 初始条件:队列非空 。 ·10 · 操作结果:删除队头元素,并用 e 返回其值。 6)boolOutQueue( ) 初始条件:队列非空 。 操作结果:删除队头元素 。 7)boolGetHead(ElemType&e)const 初始条件:队列非空 。 操作结果:用 e 返回队头元素 。 8)boolInQueue(constElemType&e) 初始条件:队列已存在 。 操作结果:插入元素 e 为新的队尾 。 2. 链队列 用链表表示的队列称为链队列,一个链队列应有两个分别指示队头与队尾的指针(分别 称为头指针与尾指针), 如图1.4所示。 3. 图1.4 链队列示意图 3. 如要从队列中退出一个元素,必须从单链表的首元素节点中取出队头元素,并删除此节 点,而入队的新元素是存放在队尾处的,也就是单链表的最后一个元素的后面,并且此节点 将成为新的队尾。 3. 循环队列———队列的顺序存储结构 用C++描述队列的顺序存储结构,就是利用一个容量是maxSize的一维数组elems 作 为队列元素的存储结构,其中front和rear分别表示队头和队尾,maxSize是队列的最大元 素个数。当队列的实际可用空间还没有使用完,这种情况下再插入一个新元素产生的溢出 称为假溢出,解决假溢出的一个技巧是将顺序队列从逻辑上看成一个环,成为循环队列,循 环队列的首尾相接,当队头front和队尾rear进入maxSize-1时,再进一个位置就自动移 动到0。此操作可用取余运算(%)简单地实现。 队头进1:frn=(rnxie otfot+1)%maSz 队尾进1:= ( rearrear+1)%maxSize 只从front=rear无法判断是队空还是队满,有3种处理方法 : (1)另设一个标志符区别队列是空还是满。 (2)少用一个元素空间,约定队头在队尾指针的下一位置(指环状的下一位置)时作为 队满的标志。 (3)增加一个表示元素个数count的成员,队空条件就变成count==0,队满条件为 count==maxSize。 本书配套软件包采用方法(3)处理循环队列。 ·11· *3.优先队列 3 在许多情况下,前面介绍的队列是不够的,先进先出的机制有时需要某些优先规则来完 善。比如在医院中,危重病人应具有更高的优先权,也就是当医生有空时,应立刻医治危重 病人,而不是排在最前面的病人。 优先队列(priorityqueue)是一种数据结构,其中元素的固有顺序决定了对基本操作的 执行结果,优先队列有两种类型:最小优先队列和最大优先队列。最小优先队列的出队操 作OutQueue() 将删除最小的数据元素值。最大优先队列的出队操作OutQueue() 将删除 最大的数据元素值。 优先队列有多种实现方法,一种比较简单的实现方法是在做入队操作InQueue() 时,元 素不是排在队列的队尾,而是将其插入在队列的适当位置,使队列的元素有序,优先队列类 模板可作为队列类的派生来实现。只需要重载入队操作InQueue() 即可。 ·12·