代码如下：
SeqQueue.c文件：
/************************************************************************************
文件名：SeqQueue.c
头文件：SeqQueue.h
时间： 2014/03/31
作者： Hao
功能：可以复用的顺序循环队列 即入队列和出队列的时间复杂度都为O(1)
************************************************************************************/
#include <stdio.h>
#include <malloc.h>
#include "SeqQueue.h"
typedef void* TSeqQueueNode;
typedef struct str_SeqQueue
{
int capacity;
int length;
int front;
int rear;
TSeqQueueNode* node;
}TSeqQueue;
/************************************************************************************
函数名： SeqQueue_Create
函数功能： 创建一个容量为capacity的循环队列
参数： int capacity 创建循环队列中成员的个数 即循环队列容量
返回值： void* ret 如果返回NULL 说明创建循环队列失败
如果返回ret 说明创建循环队列成功 且ret为描述循环队列的结构体
************************************************************************************/
SeqQueue* SeqQueue_Create(int capacity)
{
TSeqQueue* ret = NULL;
if( capacity >= 0 )
{
ret = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode) * capacity);
if( ret != NULL )
{
ret->capacity = capacity;
ret->length = 0;
ret->front = 0;
ret->rear = 0;
ret->node = (TSeqQueueNode*)(ret + 1);
}
}
else
{
ret = NULL;
}
return (SeqQueue*)ret;
}
/************************************************************************************
函数名： SeqQueue_Destroy
函数功能： 销毁循环队列 free开辟的内存
参数： void* list 描述循环队列结构体指针
返回值： void
************************************************************************************/
void SeqQueue_Destroy(SeqQueue* queue)
{
free(queue);
}
/************************************************************************************
函数名： SeqQueue_Clear
函数功能：清空循环队列 其实就是给length=0； front = 0 rear = 0;
函数参数：SeqQueue* queue 描述循环队列结构体指针
函数返回值：int ret 成功返回0
失败返回-1
************************************************************************************/
int SeqQueue_Clear(SeqQueue* queue)
{
int ret;
TSeqQueue *Tqueue = (TSeqQueue* )queue;
/*函数参数合法性检测*/
if(NULL != Tqueue)
{
Tqueue->length = 0;
Tqueue->front = 0;
Tqueue->rear = 0;
ret=0;
}
else
ret=-1;
return ret;
}
/************************************************************************************
函数名： SeqQueue_Length
函数功能：获得循环队列 现在的大小
函数参数：void* list 描述循环队列结构体指针
函数返回值：int ret 成功返回length
失败返回-1
************************************************************************************/
int SeqQueue_Length(SeqQueue* queue)
{
int ret;
TSeqQueue *Tqueue = (SeqQueue* )queue;
/*函数参数合法性检测*/
if(NULL != Tqueue)
{
ret = Tqueue->length;
}
else
ret = -1;
return ret;
}
/************************************************************************************
函数名： SeqQueue_Capacity
函数功能：获得循环队列 的容量
函数参数：void* list 描述循环队列结构体指针
函数返回值：int ret 成功返回capacity
失败返回-1
************************************************************************************/
int SeqQueue_Capacity(SeqQueue* queue)
{
int ret;
TSeqQueue *Tqueue = (SeqQueue* )queue;
/*函数参数合法性检测*/
if(NULL != Tqueue)
{
ret = Tqueue->capacity;
}
else
ret = -1;
return ret;
}
/************************************************************************************
函数名： SeqQueue_Push
函数功能：入队操作
函数参数：SeqQueue* queue入队队列, void* data入队数据元素
这个队列是从尾部入队rear 从头部出队front
函数返回值：int ret 成功返回 1
失败返回 0
************************************************************************************/
int SeqQueue_Push(SeqQueue* queue, void* data)
{
TSeqQueue* Tqueue = (TSeqQueue*)queue;
int ret = (Tqueue != NULL) && (data != NULL); //安全性检测
ret = ret && (Tqueue->length + 1 <= Tqueue->capacity); //容量检测
if(ret)
{
Tqueue->node[Tqueue->rear] = data;
Tqueue->rear = (Tqueue->rear + 1) % Tqueue->capacity;
Tqueue->length++;
}
return ret;
}
/************************************************************************************
函数名： SeqQueue_Pop
函数功能：出队操作
函数参数：SeqQueue* queue出队队列
这个队列是从尾部入队rear 从头部出队front
函数返回值：void* ret 成功返回 数据元素地址
失败返回 NULL
************************************************************************************/
void* SeqQueue_Pop(SeqQueue* queue)
{
TSeqQueue* Tqueue = (TSeqQueue*)queue;
void* ret = NULL;
if((Tqueue != NULL) && (Tqueue->length > 0))
{
ret = (void*)(Tqueue->node[Tqueue->front]);
Tqueue->front = (Tqueue->front + 1) % Tqueue->capacity;
Tqueue->length--;
}
return ret;
}
/************************************************************************************
函数名： SeqQueue_Top
函数功能：获得队尾元素地址
函数参数：SeqQueue* queue出队队列
这个队列是从尾部入队rear 从头部出队front
函数返回值：void* ret 成功返回 队尾数据元素地址
失败返回 NULL
************************************************************************************/
void* SeqQueue_Top(SeqQueue* queue)
{
TSeqQueue* Tqueue = (TSeqQueue*)queue;
void* ret = NULL;
if((Tqueue != NULL) && (Tqueue->length > 0))
{
ret = (void*)(Tqueue->node[Tqueue->front]);
}
return ret;
}
#ifndef _SeqQueue_H_ #define _SeqQueue_H_ typedef void SeqQueue; SeqQueue* SeqQueue_Create(int capacity); void SeqQueue_Destroy(SeqQueue* queue); int SeqQueue_Clear(SeqQueue* queue); int SeqQueue_Push(SeqQueue* queue, void* data); void* SeqQueue_Pop(SeqQueue* queue); void* SeqQueue_Top(SeqQueue* queue); int SeqQueue_Length(SeqQueue* queue); int SeqQueue_Capacity(SeqQueue* queue); #endif
#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"
int main(int argc, char *argv[])
{
SeqQueue* queue = SeqQueue_Create(6);
int a[10] = {0};
int i = 0;
for(i=0; i<10; i++)
{
a[i] = i + 1;
SeqQueue_Push(queue, a + i);
}
printf("Top: %d\n", *(int*)SeqQueue_Top(queue));
printf("Length: %d\n", SeqQueue_Length(queue));
printf("Capacity: %d\n", SeqQueue_Capacity(queue));
while( SeqQueue_Length(queue) > 0 )
{
printf("Pop: %d\n", *(int*)SeqQueue_Pop(queue));
}
printf("\n");
for(i=0; i<10; i++)
{
a[i] = i + 1;
SeqQueue_Push(queue, a + i);
printf("Pop: %d\n", *(int*)SeqQueue_Pop(queue));
}
SeqQueue_Destroy(queue);
return 0;
}
注意：其实循环队列就是在一段内存空间中，使用front和rear变量夹住一端空间，使其成为顺序队列，并且入队列和出队列的时间复杂度都是O(1)数据结构学习笔记(8.循环队列与链队列),布布扣,bubuko.com
原文：http://blog.csdn.net/mbh_1991/article/details/22653511