目录
一、循环队列的定义
二、循环队列的实现
三、循环队列的基本操作
- ①初始化
②判空
③判满
④入队
⑤出队
⑥获取长度
⑦打印
四、循环队列的应用
五、全部代码
数据结构中的循环队列
在数据结构中，队列（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("\n");
}
四、循环队列的应用
循环队列常用于解决生产者-消费者问题，以及在需要定期缓存数据时。它还在计算机操作系统的进程调度中得到广泛应用，用于管理就绪队列。循环队列的高效性和简单性使其成为许多问题的理想解决方案。
五、全部代码
①seqqueue.h
#ifndef _SEQQUEUE_H_
#define _SEQQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
typedef int TypeData;
typedef struct Node{
TypeData *data;
int front;
int tail;
int len;
}Queue,*Pqueue;
Pqueue init_queue(Pqueue *queue, int m);
int isEmpty(Pqueue queue);
int full(Pqueue queue);
int get_length(Pqueue queue);
int queue_en(Pqueue queue, TypeData value);
TypeData queue_de(Pqueue queue);
void show(Pqueue queue);
#endif
②seqqueue.c
#include "seqqueue.h"
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)->tail = 0;
(*queue)->len = m;
return *queue;
}
int isEmpty(Pqueue queue){
return queue->front == queue->tail;
}
int full(Pqueue queue){
return (queue->tail+1) % (queue->len) == (queue->front);
}
int get_length(Pqueue queue){
#if 0
int a = queue->tail - queue->front;
if(a >= 0){
return a;
}else{
return (a + queue->len) % (queue->len);
}
#else
return (queue->tail - queue->front + queue->len) % queue->len;
#endif
}
int queue_en(Pqueue queue, TypeData value){
if(full(queue)){
return -1;
}
queue->data[queue->tail] = value;
queue->tail = (queue->tail + 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;
}
void show(Pqueue queue){
for(int i = queue->front; i != queue->tail; i = (i + 1) % queue->len){
printf("%d ",queue->data[i]);
}
printf("\n");
}
③seqqueue_main.c
#include "seqqueue.h"
#include "seqqueue.c"
#include <unistd.h>
int main(int argc, char *argv[])
{
Pqueue queue;
init_queue(&queue, 10);
printf("入队：");
queue_en(queue, 20);
queue_en(queue, 55);
queue_en(queue, 60);
queue_en(queue, 99);
queue_en(queue, 22);
queue_en(queue, 66);
queue_en(queue, 100);
show(queue);
printf("出队：");
queue_de(queue);
show(queue);
printf("队内还有%d个元素",get_length(queue));
printf("\n");
return 0;
}
