目录

数据结构中的循环队列

在数据结构中，队列（Queue）是一种常见的线性数据结构，遵循先进先出（First In First Out，FIFO）的原则。循环队列是队列的一种变体，它可以更高效地利用存储空间，并解决了普通队列可能出现的假溢出问题。本篇博客将详细介绍循环队列的定义、实现和基本操作。

一、 循环队列的定义

循环队列是通过数组或链表实现的一种队列，它将队列的首尾相连，形成一个循环。在循环队列中，队尾指针（rear）可能在队列的前面，队头指针（front）可能在队列的后面。当队列为空时，front和rear指向同一个位置。当队列满时，front和rear之间有一个空位。

二、循环队列的实现

我们可以通过数组来实现循环队列。为了更好地利用存储空间，通常会预留一个位置来区分队列是空还是满。具体来说，我们需要定义一个固定大小的数组和两个指针front和rear来表示队头和队尾。

typedef int TypeData;
typedef struct Node{
          
   
    TypeData *data;
    int front;
    int rear;
    int len;
}Queue,*Pqueue;

三、循环队列的基本操作

①初始化队列

Pqueue init_queue(Pqueue *queue, int m){
          
   
    *queue = (Pqueue)malloc(sizeof(Queue));
    if(*queue == NULL){
          
   
        return NULL;
    }
    (*queue)->data = (TypeData *)malloc(sizeof(Queue) * m);
    (*queue)->front = (*queue)->rear= 0;
    (*queue)->len = m;
    return *queue;
}

②判空

int isEmpty(Pqueue queue){
          
   
    return queue->front == queue->rear;
}

③判满

int full(Pqueue queue){
          
   
    return (queue->rear+1) % (queue->len) == (queue->front);
}

④入队

int queue_en(Pqueue queue, TypeData value){
          
   
    if(full(queue)){
          
   
        return -1;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear+ 1) % (queue->len);
    return 0;
}

⑤出队

TypeData queue_de(Pqueue queue){
          
   
    if(isEmpty(queue)){
          
   
        return -1;
    }
    TypeData temp = queue->data[queue->front];
    queue->front = (queue->front + 1) % (queue->len);
    return temp;
}

⑥获取队列长度

int get_length(Pqueue queue){
          
   
#if 0
    int a = queue->rear - queue->front;
    if(a >= 0){
          
   
        return a;
    }else{
          
   
        return (a + queue->len) % (queue->len);
    }
#else 
    return (queue->rear - queue->front + queue->len) % queue->len;
#endif
}

⑦打印

void show(Pqueue queue){
          
   
    for(int i = queue->front; i != queue->rear; i = (i + 1) % queue->len){
          
   
        printf("%d ",queue->data[i]);
    }
    printf("
");
}

四、循环队列的应用

循环队列常用于解决生产者-消费者问题，以及在需要定期缓存数据时。它还在计算机操作系统的进程调度中得到广泛应用，用于管理就绪队列。循环队列的高效性和简单性使其成为许多问题的理想解决方案。

五、全部代码