您阅读这篇文章共耗时:
一、什么是循环队列
1、基本概念
队列就是一个能够实现“先进先出”的存储结构，队列分为链式队列和静态队列。静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。说白了循环队列就是一个数组循环队列出队，我们把这个数组当成首尾相连来使用(写到数组的末尾后从头开始写)。
2、结构体
typedef char Item; //环形队列的数据类型,根据自身情况设置
typedef struct queue
{
Item *data; //使用指针的方式，大小在使用循环队列的文件分配，减少queue.c、queue.h和其他文件的耦合性！
unsigned int front; //指向队列第一个元素
unsigned int rear; //指向队列最后一个元素的下一个元素
unsigned int maxsize; //循环队列的最大存储空间
说明：
a、队列初始化时，front和rear值都为零。
b、当队列为空时，front与rear的值相等，但不一定为零。
c、当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置。
二、队列的基本操作
1、判断队列是否为空。若front与rear的值相等（不一定为零）则队列为空。
2、判断队列是否填满。这个问题比较复杂，如下图所示（此图转载），假设数组的存数空间为7，此时已经存放1，a，5,7,22,90六个元素了循环队列出队，如果在往数组中添加一个元素，则rear=front；此时，队列满与队列空的判断条件front=rear相同，这样的话我们就不能判断队列到底是空还是是满了。解决这个问题有两个办法：一是增加一个参数，用来记录数组中当前元素的个数；第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满。
3、循环队列入队
（1）把值存在rear所在的位置；
（2）rear=（rear+1）% ，其中代表数组的长度；
4、循环队列出队
（1）先保存出队的值；
（2）front=（front+1）% ，其中代表数组的长度；
三、例子。
这个简单的例子只是为了演示循环队列的使用而已，先把数据放入循环队列，然后取出打印出来。
main.c文件
#include
#include "queue.h"
#if 0
#define PrintToBuffer(fmt, args...) do { \
if(!FullQueue(&queue)) { \
sprintf(printk_buffer.high[queue.rear],fmt, ## args); \
Enqueue(&queue,0); \
} \
}while(0)
#define PrintToConsole() do { \
if(!EmptyQueue(&queue)) { \
printk("%s",printk_buffer.high[queue.front]); \
Dequeue(&queue,0); \
} \
}while(0)
#endif
#define QUEUE_SIZE 10
QUEUE queue;
int main(int argc, char **argv)
{
int count = 0;
Item value = 'a';
CreateQueue(&queue, QUEUE_SIZE);
for(count = 0; count < 8; count++) {
Enqueue(&queue, value);
value++;
}
for(count = 0; count < 8; count++) {
Dequeue(&queue, &value);
printf("%c ", value);
}
printf("\n");
return 0;
}
queue.c文件
#include
#include
#include "queue.h"
void CreateQueue(PQUEUE Q,int maxsize)
{
Q->data = (Item *)malloc(sizeof(Item) * maxsize);
Q->front = 0;
Q->rear = 0;
Q->maxsize = maxsize;
return;
}
bool FullQueue(PQUEUE Q)
{
if(Q->front==(Q->rear+1)%Q->maxsize) {
return 1;
} else {
return 0;
}
}
bool EmptyQueue(PQUEUE Q)
{
if(Q->front==Q->rear) {
return 1;
} else {
return 0;
}
}
bool Enqueue(PQUEUE Q, Item val)
{
if(FullQueue(Q)) {
return 0;
} else {
Q->data[Q->rear] = val;
Q->rear = (Q->rear+1)%Q->maxsize;
return 1;
}
}
bool Dequeue(PQUEUE Q, Item *val)
{
if(EmptyQueue(Q)) {
return 0;
} else {
*val = Q->data[Q->front];
Q->front = (Q->front+1)%Q->maxsize;
return 1;
}
queue.h文件
#ifndef QUEUE_H
#define _QUEUE_H_
#include
#include
typedef char Item; //环形队列的数据类型,根据自身情况设置
typedef struct queue
{
Item *data; //使用指针的方式，大小在使用循环队列的文件分配，减少queue.c、queue.h和其他文件的耦合性！
unsigned int front; //指向队列第一个元素
unsigned int rear; //指向队列最后一个元素的下一个元素
unsigned int maxsize; //循环队列的最大存储空间
}QUEUE, *PQUEUE;
//分配数据空间和初始化参数
void CreateQueue(PQUEUE Q,int maxsize);
//判断循环队列是否满，留一个预留空间不用
bool FullQueue(PQUEUE Q);
//判断循环队列是否空
bool EmptyQueue(PQUEUE Q);
//将数据放入队列保存
bool Enqueue(PQUEUE Q, Item val);
//从队列取出数据到val
bool Dequeue(PQUEUE Q, Item *val);
文件
CC = gcc
WORKDIR =
INCLUDES =
LIBS =
LINKS =
TARGET = queuetest
src=$(wildcard *.c ./callback/*.c)
C_OBJS=$(patsubst %.c, %.o,$(src))
#C_OBJS=$(dir:%.c=%.o)
compile:$(TARGET)
$(C_OBJS):%.o:%.c
$(CC) $(CFLAGS) $(INCLUDES) -o $*.o -c $*.c
$(TARGET):$(C_OBJS)
$(CC) -o $(TARGET) $^ $(LIBS) $(LINKS)
@echo
@echo Project has been successfully compiled.
@echo
install: $(TARGET)
cp $(TARGET) $(INSTALL_PATH)
uninstall:
rm -f $(INSTALL_PATH)/$(TARGET)
rebuild: clean compile
clean:
四、为什么要使用循环队列
1、为了缓冲数据。比如，某一时间cpu太忙，收到的数据来不及处理了，这时候就可以把数据先存到循环队列，等cpu不忙了再拿出来处理。
