首页  /  数据结构教程  /  循环队列二  /  

循环队列二

点击打开在线编译器,边学边练

1. 初始化

我们初始化相比链表而言更为简单了,核心就在于申请空间以及将front指针和rear指针内容赋值为0,即指向第0个元素即可(注意第 0个元素内容为空)。

4041.png

其代码可以表示为:

//初始化
cir_queue *init(){
    cir_queue *q = (cir_queue*)malloc(sizeof(cir_queue));
    if(q==NULL){
        exit(0);   //申请内存失败,退出程序
    }
    q->front=0;
    q->rear=0;
    return q;
}


2.  入队操作

入队操作同顺序队列的方法,直接将rear向后移动即可,但是要注意判断,如果rear达到了队列的空间上线,将要从头继续开始移动,这里推荐使用余数法,即无论如何求余都是在这片空间内进行操作,防止一次错误执行就直接整体崩溃,而且也相对而言更为简洁,不推荐使用if语句,这样显得比较累赘。

4042.png

注意进行加一移动位置操作的时候,不能直接q->rear++这样的操作,这样计算机判断优先级会产生让自己意想不到的后果,此外这里还需要进行一次是否队列已满的判断,当我们rear指针的下一个位置就是front的位置的时候,即改循环队列已满。

如图:

4043.png

其代码可以表示为:

//入队操作push
void push(cir_queue *q,int data){
    if((q->rear+1)%maxsize==q->front){
        printf("溢出,无法入队\n");
        return;
    }else{
        q->rear=(q->rear+1)%maxsize;
        q->data[q->rear]=data;
    }
}

3. 出队操作

如果顺序队列的出队操作,直接将front进行后移一位即可,注意这时候有一个需要留意的地方,即队列是否为空,当队列为空的时候是无法进行出队操作的。

4044.png

其代码可以表示为:

//出队操作pop
void pop(cir_queue *q){
    if(q->rear==q->front){
        printf("队列为空,无法出队\n");
        return;
    }else{
        q->data[q->front]=0;
        q->front=(q->front+1)%maxsize;
    }
}

4. 遍历操作

遍历操作需要借助一个临时变量储存位置front的位置信息,利用i逐步向后移动,直到i到达了rear的位置即可宣告遍历的结束。

//遍历队列
void print(cir_queue *q){
    int i=q->front;
    while(i!=q->rear){
        i=(i+1)%maxsize;
        printf("%d\t",q->data[i]);   
    }
    printf("\n");       //记得换行
}

5. 本题代码

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#define maxsize 10      //表示循环队列的最大容量

//循环队列的结构设计
typedef struct cir_queue{
    int data[maxsize];
    int rear;
    int front;
}cir_queue;

//初始化
cir_queue *init(){
    cir_queue *q = (cir_queue*)malloc(sizeof(cir_queue));
    if(q==NULL){
        exit(0);    //申请内存失败,退出程序
    }
    memset(q->data,0,sizeof(q->data));
    q->front=0;
    q->rear=0;
    return q;
}

//入队操作push
void push(cir_queue *q,int data){
    if((q->rear+1)%maxsize==q->front){
        printf("溢出,无法入队\n");
        return;
    }else{
        q->rear=(q->rear+1)%maxsize;
        q->data[q->rear]=data;
    }
}

//出队操作pop
void pop(cir_queue *q){
    if(q->rear==q->front){
        printf("队列为空,无法出队\n");
        return;
    }else{
        q->data[q->front]=0;
        q->front=(q->front+1)%maxsize;
    }
}

//遍历队列
void print(cir_queue *q){
    int i=q->front;
    while(i!=q->rear){
        i=(i+1)%maxsize;
        printf("%d\t",q->data[i]);   
    }
    printf("\n");       //记得换行
}

int main(){
    cir_queue *q = init();
    ////////////入队操作///////////////
    printf("入队操作\n");
    for(int i=1;i<=6;i++){
        push(q,i);
    }
    print(q);
    ////////////出队操作///////////////
    printf("出队操作\n");
    for(int i=1;i<=3;i++){
        pop(q);
        print(q);
    }
    return 0;
}


6.  题目推荐

毕竟循环队列只是队列的基本优化,可以使用普通顺序队列的练习题再度练习:

1895题

上一课:循环队列一
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记