第3章 栈和队列（2）.pptx

;队列（queue）是一种只能在不同端进行插入或删除操作的线性表。

进行插入的一端称做队尾（rear），进行删除的一端称做队头或队首（front）。

队列的插入操作通常称为进队或入队（push），队列的删除操作通常称为出队或离队（pop）。;3/92;先进先出，即先进队的元素先出队。

每次进队的元素作为新队尾元素，每次出队的元素只能是队头的元素。

队列也称为先进先出表。;队列抽象数据类型=线性结构+队列的基本运算;【例3.10】若元素进队顺序为1234，能否得到3142的出队序列？;队列的实现方式;…a0a1…an-1…;1.非循环队列;;;;非循环队列的基本运算算法;（2）进队push(e);（3）出队pop();（4）取队头元素peek();2.循环队列;循环队列首尾相连，当队尾指针rear=MaxSize-1时，再前进一个位置就应该到达0位置，这可以利用数学上的求余运算（％）实现：

（1）队首指针循环进1：front=(front+1)％MaxSize

（2）队尾指针循环进1：rear=(rear+1)％MaxSize;MaxSize=4，初始front=rear=0;顺序队（含循环队列和非循环队列）通过front和rear标识队列状态，一般是采用它们的相对值即|front-rear|实现的。

若data数组的容量为m，则队列的状态有m+1种，分别是队空、队中有1个元素、队中有2个元素、…、队中有m个元素（队满）。

front和rear的取值范围均为0～m-1，这样|front-rear|只有m个值。

显然m+1种状态不能直接用|front-rear|区分，因为必定有两种状态不能区分。

为此让队列中最多只有m-1个元素，这样队列恰好只有m种状态了，就可以通过front和rear的相对值区分所有状态了。;;;循环队列的基本运算算法;（2）进队push(e);（3）出队pop();（4）取队头元素peek();3.2.3顺序队的应用算法设计示例;cnt=(rear-front)=3;publicintsize() //返回队中元素个数

{

return(rear-front+MaxSize)%MaxSize;

};进队第k（k≥1）个元素e;publicstaticbooleanpushk(CSqQueueClassIntegerqu,intk,Integere)

//进队第k个元素e

{Integerx;

inti=1,n=qu.size();

if(k1||kn+1)returnfalse; //参数k错误返回false

if(k=n)

{for(i=1;i=n;i++) //循环处理队中所有元素

{if(i==k)qu.push(e); //将e元素进队到第k个位置

x=qu.pop(); //出队元素x

qu.push(x); //进队元素x

}

}

elsequ.push(e); //k=n+1时直接进队e

returntrue;

};publicstaticIntegerpopk(CSqQueueClassIntegerqu,intk)

//出队第k个元素

{Integerx,e=0;

inti=1,n=qu.size();

if(k1||kn) //参数k错误

thrownewIllegalArgumentException(参数错误);

for(i=1;i=n;i++) //循环处理队中所有元素

{x=qu.pop(); //出队元素x

if(i!=k)qu.push(x); //将非第k个元素进队

elsee=x; //取第k个出队的元素

}

returne;

};【例3.12】对于循环队列来说，如果知道队头指针和队列中元素个数，则可以计算出队尾指针。也就是说，可以用队列中元素个数代替队尾指针。设计出这种循环队列的判队空、进队、出队和取队头元素的算法。;classCSqQueueClass1E //本例循环队列泛型类

{finalintMaxSize=100; //假设容量为100

privateE[]data; //存放队列中的元素

privateintfront; //队头指针

privateintcount; //元素个数

public