C# · 12月 20, 2021

【数据结构】队列-循环队列的基本定义

循环队列的基本定义 :

顺序存储结构定义:

typedef struct{

QElemType *base;

int Front,Rear;

}CQueue;

循环队列的基本操作:

1、初始化一个队列

2、清空一个队列

3、判断一个队列是否为空

4、求队列的长度

5、入队列操作

6、出队列操作

7、取队头元素

8、历遍操作

1、初始化一个队列

void InitCQueue(CQueue &Q){

Q.base=new QElemType [QueueSize];

Q.Front=Q.Rear=0;

}

2、清空一个队列

void ClearCQueue(CQueue &Q){

delete [] Q.base;

InitCQueue(Q);

}

3、判断一个队列是否为空

bool QueueEmpty(CQueue Q){

return Q.Front==Q.Rear?true:false;

}

4、求队列的长度

int QueueLength(CQueue Q){

return (Q.Rear-Q.Front+QueueSize)%QueueSize;

}

5、入队列操作

void EnQueue(CQueue &Q,QElemType e){

if((Q.Rear+1)%QueueSize == Q.Front){

printf(“error !!! Queue is full !!!”);return ;

}

Q.base[Q.Rear]=e;

Q.Rear=(Q.Rear+1)%QueueSize;

}

6、出队列操作

void DeQueue(CQueue &Q,QElemType &e){

if(Q.Front==Q.Rear){

printf(“error !!! Queue is empty !!!”);return ;

}

e=Q.base[(Q.Front)%QueueSize];

Q.Front=(Q.Front+1)%QueueSize;

}

7、取队头元素

void GetHead(CQueue Q,QElemType &e){

if(Q.Front==Q.Rear){

printf(“error !!! Queue is empty !!!”);return ;

}

e=Q.base[Q.Front];

}

8、历遍操作

void QueueTraverse(CQueue Q){

for(int i=Q.Front;i!=Q.Rear;i=(i+1)%QueueSize){

printf(“%d%c”,Q.base[i],(i+1)%QueueSize==Q.Rear?’n’:’ ‘);

}

}

完整的调试代码:

#include

#include

#include

#define QElemType int

#define QueueSize 11

using namespace std;

typedef struct{

QElemType *base;

int Front,Rear;

}CQueue;

void InitCQueue(CQueue &Q){

Q.base=new QElemType [QueueSize];

Q.Front=Q.Rear=0;

}

void ClearCQueue(CQueue &Q){

delete [] Q.base;

InitCQueue(Q);

}

bool QueueEmpty(CQueue Q){

return Q.Front==Q.Rear?true:false;

}

int QueueLength(CQueue Q){

return (Q.Rear-Q.Front+QueueSize)%QueueSize;

}

void EnQueue(CQueue &Q,QElemType e){

if((Q.Rear+1)%QueueSize == Q.Front){

printf(“error !!! Queue is full !!!”);return ;

}

Q.base[Q.Rear]=e;

Q.Rear=(Q.Rear+1)%QueueSize;

}

void DeQueue(CQueue &Q,QElemType &e){

if(Q.Front==Q.Rear){

printf(“error !!! Queue is empty !!!”);return ;

}

e=Q.base[(Q.Front)%QueueSize];

Q.Front=(Q.Front+1)%QueueSize;

}

void GetHead(CQueue Q,QElemType &e){

if(Q.Front==Q.Rear){

printf(“error !!! Queue is empty !!!”);return ;

}

e=Q.base[Q.Front];

}

void QueueTraverse(CQueue Q){

for(int i=Q.Front;i!=Q.Rear;i=(i+1)%QueueSize){

printf(“%d%c”,(i+1)%QueueSize==Q.Rear?’n’:’ ‘);

}

}

int main()

{

CQueue Q;

InitCQueue(Q);

int e;

if(QueueEmpty(Q)){

for(int i=0;i<10;i++){

//printf(“%dn”,i);

EnQueue(Q,i);

}

}

printf(“Front : %d Rear : %dn”,Q.Front,Q.Rear);

//printf(“%dn”,Q.base[0]);

QueueTraverse(Q);

for(int i=0;i<9;i++){

DeQueue(Q,e);

printf(“%d %d %d F: %d R: %dn”,i,e,QueueLength(Q),Q.Rear);

}

GetHead(Q,e);printf(“%dn”,e);

for(int i=0;i<4;i++){

//printf(“%dn”,i);

}

printf(“Front : %d Rear : %dn”,Q.Rear);

for(int i=0;i<3;i++){

DeQueue(Q,Q.Rear);

}

ClearCQueue(Q);

if(QueueEmpty(Q)){

printf(“Front : %d Rear : %dn”,Q.Rear);

}

return 0;

}