数据结构——循环队列的简单实现
程序员文章站
2022-07-14 12:29:56
...
采用顺序存储方式,存储容量要比逻辑上的容量多一个,以此方便判断队空还是队满。采用尾进头出的模式,来达到先进先出的目的。操作简单描述如下:
队尾指针是rear,队头是front,其中QueueSize为循环队列的最大长度。1.队空条件:rear==front。
2.队满条件:(rear+1) %QueueSIze==front。
3.计算队列长度:(rear-front+QueueSize)%QueueSize。
4.入队:(rear+1)%QueueSize。
5.出队:(front+1)%QueueSize。
C语言实现:
typedef struct Queue{
int *front;
int *rear;
int *head;
int queueSize;
}Queue,*PQueue;
void initQueue(PQueue x,int size){
x->queueSize=size;
x->front=x->rear=x->head=(int*)malloc(sizeof(int)*(size+1));
}
int* getRemainder(int *x,int *head,int size){
while(x-head>=size)
x=x-size;
return x;
}//指针的取余操作
int judgeEmpty(PQueue x){
if(x->front==x->rear)
return 1;
return 0;
}
int judgeFilled(PQueue x){
if((x->rear+1-x->front)%(x->queueSize+1)==0)
return 1;
return 0;
}
int inQueue(PQueue x,int in){
if(judgeFilled(x)){
printf("Filled!\n");
return 1;
}
*x->rear=in;
x->rear=getRemainder(x->rear+1,x->head,x->queueSize);
return 0;
}
int outQueue(PQueue x){
if(judgeEmpty(x)){
printf("Empty!\n");
return 1;
}
x->front=getRemainder(x->front+1,x->head,x->queueSize);
return 0;
}
int getElem(PQueue x,int i){
if(i<0||i>=x->rear-x->front){
printf("Ilegal i!\n");
return -1;
}
return *getRemainder(x->front+i,x->head,x->queueSize);
}
下一篇: C++中vector和set简单用法