目錄
一、循環(huán)隊(duì)列的定義
二、循環(huán)隊(duì)列的實(shí)現(xiàn)
三、循環(huán)隊(duì)列的基本操作
-
①初始化
②判空
③判滿
④入隊(duì)
⑤出隊(duì)
⑥獲取長度
⑦打印
四、循環(huán)隊(duì)列的應(yīng)用
五、全部代碼
數(shù)據(jù)結(jié)構(gòu)中的循環(huán)隊(duì)列
在數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列（Queue）是一種常見的線性數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出（First In First Out，F(xiàn)IFO）的原則。循環(huán)隊(duì)列是隊(duì)列的一種變體，它可以更高效地利用存儲空間，并解決了普通隊(duì)列可能出現(xiàn)的假溢出問題。本篇博客將詳細(xì)介紹循環(huán)隊(duì)列的定義、實(shí)現(xiàn)和基本操作。
一、 循環(huán)隊(duì)列的定義
循環(huán)隊(duì)列是通過數(shù)組或鏈表實(shí)現(xiàn)的一種隊(duì)列，它將隊(duì)列的首尾相連，形成一個(gè)循環(huán)。在循環(huán)隊(duì)列中，隊(duì)尾指針（rear）可能在隊(duì)列的前面，隊(duì)頭指針（front）可能在隊(duì)列的后面。當(dāng)隊(duì)列為空時(shí)，front和rear指向同一個(gè)位置。當(dāng)隊(duì)列滿時(shí)，front和rear之間有一個(gè)空位。
二、循環(huán)隊(duì)列的實(shí)現(xiàn)
我們可以通過數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列。為了更好地利用存儲空間，通常會預(yù)留一個(gè)位置來區(qū)分隊(duì)列是空還是滿。具體來說，我們需要定義一個(gè)固定大小的數(shù)組和兩個(gè)指針front和rear來表示隊(duì)頭和隊(duì)尾。
typedef int TypeData;
typedef struct Node{
TypeData *data;
int front;
int rear;
int len;
}Queue,*Pqueue;
三、循環(huán)隊(duì)列的基本操作
①初始化隊(duì)列
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);
}
④入隊(duì)
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;
}
⑤出隊(duì)
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;
}
⑥獲取隊(duì)列長度
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");
}
四、循環(huán)隊(duì)列的應(yīng)用
循環(huán)隊(duì)列常用于解決生產(chǎn)者-消費(fèi)者問題，以及在需要定期緩存數(shù)據(jù)時(shí)。它還在計(jì)算機(jī)操作系統(tǒng)的進(jìn)程調(diào)度中得到廣泛應(yīng)用，用于管理就緒隊(duì)列。循環(huán)隊(duì)列的高效性和簡單性使其成為許多問題的理想解決方案。
五、全部代碼
①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文章來源：http://www.zghlxwxcb.cn/news/detail-606660.html
#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文章來源地址http://www.zghlxwxcb.cn/news/detail-606660.html
#include "seqqueue.h"
#include "seqqueue.c"
#include <unistd.h>
int main(int argc, char *argv[])
{
Pqueue queue;
init_queue(&queue, 10);
printf("入隊(duì)：");
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("出隊(duì)：");
queue_de(queue);
show(queue);
printf("隊(duì)內(nèi)還有%d個(gè)元素",get_length(queue));
printf("\n");
return 0;
}
到了這里，關(guān)于九、數(shù)據(jù)結(jié)構(gòu)——順序隊(duì)列中的循環(huán)隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
