循环队列的代码演示

由于队列的出队操作是head++，直接向后移动，当队尾达到队列设定的长度时，会出现假溢出的现象（即可能head前面还可以插入），因此可以改为循环队列，而循环队列可能出现真溢出的现象，因此需要扩容操作。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct Queue{
    int *data;
    //队首，和队尾，队列的长度
    int head,tail,length;
    //循环队列记录节点个数的变量
    int cnt;
}Queue;
//队列的初始化
Queue *init(int n){
    Queue *q=(Queue *)malloc(sizeof(Queue));
    q->data=(int *)malloc(sizeof(int)*n);
    q->length=n;
    q->head=0;
    q->cnt=0;
    q->tail=0;
    return q;
}
//释放内存
void clear(Queue* q){
    if(q==NULL) return ;
    free(q->data);
    free(q);
    return ;
}
//队首元素
int front(Queue *q){
    return q->data[q->head];
}
//判断队列是否为空
int empty(Queue *q){
    return q->cnt==0;
}
//循环队列的扩容操作
int expand(Queue *q){
    int extr_size=q->length;
    //新开辟数组空间p，记录新队列的元素
    int *p;
    //判断是否有空间可以扩容，每次除以2，
    while(extr_size){
        p=(int *)malloc(sizeof(q->length+extr_size));
        //如果p不为空，说明开辟地址成功，直接break;
        if(p) break;
        extr_size>>=1;
    }
    if(p==NULL) return 0; //开辟不了多余的空间，直接返回
    //把数据拷贝到新的地址空间中
    for(int i=q->head,j=0;j<q->cnt;j++){
        p[j]=q->data[(i+j)%q->length];
    }
    //释放原来的地址空间
    free(q->data);
    //更新数据域
    q->data=p;
    //更新长度
    q->length+=extr_size;
    //更新队首和队尾的下标
    q->head=0;
    q->tail=q->cnt;
    return 1;
}

//入队操作
int push(Queue *q,int val){
    if(q==NULL) return 0;
    if(q->cnt==q->length){
        if(!expand(q)) return 0;
        printf("expand success!Queue->size = %d\n",q->length);
    }
    q->data[q->tail++]=val;
    //如果队尾到达上限，更新下标值
    if(q->tail==q->length) q->tail=0;
    q->cnt+=1;
    return 1;
}
//出队操作
int pop(Queue *q){
    if(q==NULL) return 0;
    if(empty(q)) return 0;
    q->head++;
    //如果队首达到上限，更新下标值。
    if(q->head==q->length) q->head=0;
    q->cnt-=1;
    return 1;
}

void output(Queue *q){
    printf("Queue: [");
    for(int i=q->head,j=0;j<q->cnt;i++,j++){
        j && printf(", ");
        printf("%d",q->data[i%q->length]);
    }
    printf("]\n");
    return;
}

int main(){
    srand(time(0));
    #define max_op 20
    Queue *q =init(max_op);
    //模拟扩容操作
    for(int i=0;i<max_op*2;i++){
        int val=rand()%100;
        int op=rand()%4;
        switch(op){
            case 0:
            case 1:
            case 2:{
                printf("push %d to the Queue! status = %d\n",val, push(q,val));
            }break;
            case 3:{
                printf("pop %d ",front(q));
                printf(" from the Queue! status = %d\n",pop(q));
            }break;
        }
        output(q);
        printf("\n");
    }
    #undef max_op
    clear(q);
    return 0;
}

pop 0  from the Queue! status = 0
Queue: []

push 87 to the Queue! status = 1
Queue: [87]

push 41 to the Queue! status = 1
Queue: [87, 41]

push 69 to the Queue! status = 1
Queue: [87, 41, 69]

push 42 to the Queue! status = 1
Queue: [87, 41, 69, 42]

push 69 to the Queue! status = 1
Queue: [87, 41, 69, 42, 69]

push 81 to the Queue! status = 1
Queue: [87, 41, 69, 42, 69, 81]

push 77 to the Queue! status = 1
Queue: [87, 41, 69, 42, 69, 81, 77]

pop 87  from the Queue! status = 1
Queue: [41, 69, 42, 69, 81, 77]

push 6 to the Queue! status = 1
Queue: [41, 69, 42, 69, 81, 77, 6]

push 45 to the Queue! status = 1
Queue: [41, 69, 42, 69, 81, 77, 6, 45]

pop 41  from the Queue! status = 1
Queue: [69, 42, 69, 81, 77, 6, 45]

push 75 to the Queue! status = 1
Queue: [69, 42, 69, 81, 77, 6, 45, 75]

pop 69  from the Queue! status = 1
Queue: [42, 69, 81, 77, 6, 45, 75]

push 5 to the Queue! status = 1
Queue: [42, 69, 81, 77, 6, 45, 75, 5]

pop 42  from the Queue! status = 1
Queue: [69, 81, 77, 6, 45, 75, 5]

push 68 to the Queue! status = 1
Queue: [69, 81, 77, 6, 45, 75, 5, 68]

push 0 to the Queue! status = 1
Queue: [69, 81, 77, 6, 45, 75, 5, 68, 0]

push 19 to the Queue! status = 1
Queue: [69, 81, 77, 6, 45, 75, 5, 68, 0, 19]

push 58 to the Queue! status = 1
Queue: [69, 81, 77, 6, 45, 75, 5, 68, 0, 19, 58]

pop 69  from the Queue! status = 1
Queue: [81, 77, 6, 45, 75, 5, 68, 0, 19, 58]

pop 81  from the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58]

push 32 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32]

push 72 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32, 72]

push 39 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39]

push 42 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42]

push 62 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62]

push 24 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24]

push 1 to the Queue! status = 1
Queue: [77, 6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1]

pop 77  from the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1]

push 62 to the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62]

push 70 to the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70]

push 26 to the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26]

push 43 to the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43]

push 91 to the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43, 91]

expand success!Queue->size = 40
push 12 to the Queue! status = 1
Queue: [6, 45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43, 91, 12]

pop 6  from the Queue! status = 1
Queue: [45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43, 91, 12]

push 85 to the Queue! status = 1
Queue: [45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43, 91, 12, 85]

push 83 to the Queue! status = 1
Queue: [45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43, 91, 12, 85, 83]

push 27 to the Queue! status = 1
Queue: [45, 75, 5, 68, 0, 19, 58, 32, 72, 39, 42, 62, 24, 1, 62, 70, 26, 43, 91, 12, 85, 83, 27]