C++实现循环队列和链式队列的示例

2023-09-19 05:55:05 192

循环队列：

1.循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%maxSize。（我曾经想过为什么不用一个length表示队长，当length==maxSize时队满）原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。

2.用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。

template
classSeqQueue{
protected:
T*element;
intfront,rear;
intmaxSize;
public:
SeqQueue(intsz=10){
front=rear=0;
maxSize=sz;
element=newT[maxSize];
}
~SeqQueue(){
delete[]element;
}
boolEnQueue(constT&x){//入队
if(isFull())returnfalse;
element[rear]=x;
rear=(rear+1)%maxSize;
returntrue;
}
boolDeQueue(T&x){//出队
if(isEmpty())returnfalse;
x=element[front];
front=(front+1)%maxSize;
returntrue;
}
boolgetFront(T&x){//获取队首元素
if(isEmpty())returnfalse;
x=element[front];
returntrue;
}
voidmakeEmpty(){//队列置空
front=rear=0;
}
boolisEmpty()const{//判断队列是否为空
return(rear==front)?true:false;
}
boolisFull()const{//队列是否为满
return((rear+1)%maxSize==front)?true:false;
}
intgetSize()const{
return(rear-front+maxSize)%maxSize;
}
};

测试代码如下：

voidmenu(){
cout<<"1.入队"<*sq){
switch(num){
intx;
case1:
cin>>x;
sq->EnQueue(x);
break;
case2:
sq->getFront(x);
cout<DeQueue(x);
break;
case4:
sq->makeEmpty();
break;
case5:
x=sq->getSize();
cout<*sq=newSeqQueue;
intnum;
while(true){
menu();
cin>>num;
function(num,sq);
}
deletesq;
return0;
}

之后是链式队列，实现类代码和测试代码如下：

#include
usingnamespacestd;
template
structLinkNode{
Tdata;
LinkNode*link;
LinkNode(T&x,LinkNode*l=NULL){
data=x;
link=l;
}
};
template
classLinkedQueue{
protected:
LinkNode*front,*rear;
public:
LinkedQueue(){
front=rear=NULL;
}
~LinkedQueue(){
makeEmpty();
}
boolenQueue(T&x){
if(front==NULL)
front=rear=newLinkNode(x);
else{
rear=rear->link=newLinkNode(x);
}
returntrue;
}
booldeQueue(T&x){
if(isEmpty())returnfalse;
LinkNode*p=front;
x=front->data;
front=front->link;
deletep;
returntrue;
}
boolgetFront(T&x)const{
if(isEmpty())returnfalse;
x=front->data;
returntrue;
}
voidmakeEmpty(){
LinkNode*p;
while(front!=NULL){
p=front;
front=front->link;
deletep;
}
}
boolisEmpty()const{
return(front==NULL)?true:false;
}
intgetSize()const{
LinkNode*p;
intcount=0;
p=front;
while(p!=NULL){
count++;
p=p->link;
}
returncount;
}
};
voidmenu(){
cout<<"1.入队"<*lq){
switch(num){
intx;
case1:
cin>>x;
lq->enQueue(x);
break;
case2:
lq->getFront(x);
cout<deQueue(x);
break;
case4:
lq->makeEmpty();
break;
case5:
x=lq->getSize();
cout<*lq=newLinkedQueue;
intnum;
while(true){
menu();
cin>>num;
function(num,lq);
}
deletelq;
return0;
}

以上这篇C++实现循环队列和链式队列的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++实现循环队列和链式队列的示例

热门推荐

随机推荐