循环队列

循环队列的C语言实现,把整个队列当作环来处理。一段连续的空间当作队列,front指向队列头,rear指向队列的尾。每次有数据进入队列,则rear向后一个位置移动,如果超过了最大空间,那么取余数;数据出队列,则front向后一个位置移动。队列满的时候rear = front,队列空的时候也是rear = front,于是可以这样处理,如果 rear+1 = front的话就表明是满队列,这样虽然浪费了一个空间,但是可以处理好队列满和空的问题。

下面是代码:

[code]
#include
#include

#define MAXSIZE 100

typedef int ElemType;

typedef struct CirQueue{
int front;
int rear;
ElemType *base;
}CirQueue ,*pCirQueue;

void prinf();
bool InitCirQueue(pCirQueue Q); //Initial Queue
bool InsertCirQueue(pCirQueue Q,ElemType e); //insert Queue
bool deleteCirQueue(pCirQueue Q,ElemType *e); //delete Queue
int LengthOfCirQueue(pCirQueue Q); //Number of Queue's data
void destoryCirQueue(pCirQueue Q); //Clear Queue
void DisplayCirQueue(pCirQueue Q); //print Queue's data

int main()
{
CirQueue Q;
if(!InitCirQueue(&Q)) //initial Queue
return 0;
for(int i = 1; i < 100;++i)//for debug,Insert Queue from 1 to 100;
InsertCirQueue(&Q,i);
DisplayCirQueue(&Q); //print Queue

while(1)
{
prinf();
int iChoice;
scanf("%d",&iChoice); //choose
switch(iChoice)
{
case 1:
{
int data;
printf("Iuput data:\n");
scanf("%d",&data);
if(InsertCirQueue(&Q,data)) //insert node to queue
{
DisplayCirQueue(&Q);
}
break;
}
case 2:
{
ElemType e;
if(deleteCirQueue(&Q,&e)) //delete node from queue
{
DisplayCirQueue(&Q);
}
break;
}
case 3:
printf( "Node of The Stack is %d\n" , LengthOfCirQueue(&Q)); //length of queue
break;
case 4:
destoryCirQueue(&Q); //clear queue
DisplayCirQueue(&Q);
return 0 ;
default :
break;
}
}
return 0;
}

bool InitCirQueue(pCirQueue Q) //Initial Queue
{
Q->base = (ElemType *)calloc(1,sizeof(ElemType)*MAXSIZE); //Q.base Point to base of Circular Queue
if(!Q->base)
{
printf("Error \n");
return false;
}
Q->front = 0;
Q->rear = 0;
return true;
}

bool InsertCirQueue(pCirQueue Q,ElemType e) //insert Queue
{
if((Q->rear + 1) % MAXSIZE == Q->front) //if the Queue is full
{
printf("Queue is Full\n");
return false;
}
Q->base[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE; //For Circularing
return true;
}

bool deleteCirQueue(pCirQueue Q,ElemType *e) //delete Queue
{
if(Q->rear == Q->front) //if the Queue is empty
{
printf("Empty Queue\n");
return false;
}
*e = Q->base[Q->front];
Q->front = (Q->front + 1) % MAXSIZE; //For Circularing
return true;
}

int LengthOfCirQueue(pCirQueue Q) //Number of Queue's data
{
return ((Q->rear - Q->front + MAXSIZE) % MAXSIZE);
}

void destoryCirQueue(pCirQueue Q) //Clear Queue
{
free(Q->base);
Q->base = NULL;
Q->rear = 0;
Q->front = 0;
}

void DisplayCirQueue(pCirQueue Q) //print Queue's data
{
if(Q->front == Q->rear)
{
printf("Empty Queue\n");
return ;
}
int temp = Q->front;
while(temp != Q->rear)
{
printf("%d ",Q->base[temp]);
temp = (temp + 1) % MAXSIZE;
}
}
void prinf()
{
printf ("\n1:Insert Node\n");
printf ("2:delete Node\n");
printf ("3:Length of Queue\n");
printf ("4:Destory Queue\n");
}

[/code]

标签:DataStructure