2025年c语言实现动态增容循环队列

大家好，我是讯享网，很高兴认识大家。

队列在日常开发中有时还是会用到的，比如实现一个消息队列时底层就需要一个队列、又或者实现图的广度遍历也需要用到队列。c语言标准库是没有队列这种结构提供的，这里提供一个种队列的实现方法，在c语言的环境下能够方便的使用。
一、接口设计
1、数据结构
这里直接把结构体定义在头文件，以方便使用者自由选择堆栈内存实例化。一个循环队列通常需要，一个头下标、一个尾下标、一个数组即可。这里为了实现动态增容添加数组容量字段，用以记录当前数组的长度。还添加了元素大小字段，用以适应不同的数据类型。最后增加了一个元素个数，这个字段不是必须的,循环队列的长度和队列空都可以通过头尾下标以及数组长度来计算，这里添加元素个数是为了减少计算量以空间换时间，以及节省一个头下标指向的元素空间。具体代码如下：

#include<stdint.h> #include<stddef.h> /// <summary> /// 队列 /// </summary> typedef struct { 
    /// <summary> /// 头下标 /// </summary> size_t _front; /// <summary> /// 尾下标 /// </summary> size_t _rear; /// <summary> /// 数据数组 /// </summary> uint8_t* _data; /// <summary> /// 数组容量 /// </summary> size_t _capacity; /// <summary> /// 元素大小 /// </summary> size_t _elementSize; /// <summary> /// 元素个数 /// </summary> size_t _count; }acf_queue;

讯享网

2、方法
（1）初始化
队列使用前需要初始化，传入队列对象的指针，以及队列元素的大小即可初始化队列。

讯享网/// <summary> /// 初始化队列 /// </summary> /// <param name="queue">队列对象的指针</param> /// <param name="_elementSize">元素大小</param> void acf_queue_init(acf_queue* queue, size_t elementSize);

（2）反初始化
使用完成后，需要反初始化队列以释放资源。

/// <summary> /// 反初始化队列 /// </summary> /// <param name="queue">队列对象的指针</param> void acf_queue_deinit(acf_queue* queue);

（3）入队
将元素压入对尾，传入的是元素的指针，当元素个数大于队列数组时，会自动增容。

讯享网/// <summary> /// 入队 /// </summary> /// <param name="queue">队列对象的指针</param> /// <param name="pElement">元素的指针</param> void acf_queue_enqueue(acf_queue* queue, void* pElement);

（4）出队
队头元素出队，如果队列不为空出队且返回成功，否则返回失败。

/// <summary> /// 出队 /// </summary> /// <param name="queue">队列对象的指针</param> /// <returns>1出队成功，0失败</returns> int acf_queue_dequeue(acf_queue* queue);

（5）获取队头元素
只获取队头元素而不出队。返回队头元素的指针。

讯享网/// <summary> /// 获取队头元素 /// </summary> /// <param name="queue">队列对象的指针</param> /// <returns>队头元素的指针</returns> void* acf_queue_peek(acf_queue* queue);

（6）获取元素
根据下标获取元素。返回队头元素的指针。

/// <summary> /// 获取元素 /// </summary> /// <param name="queue">队列对象的指针</param> /// <param name="index">元素的下标</param> /// <returns>队头元素的指针</returns> void* acf_queue_get_element(acf_queue* queue, size_t index);

（7）获取队列长度
获取队列中元素的个数。

讯享网/// <summary> /// 获取队列长度 /// </summary> /// <param name="queue">队列对象的指针</param> /// <returns>队列长度</returns> size_t acf_queue_get_count(acf_queue* queue);

（8）获取队列容量
获取当前队列数组长度。

/// <summary> /// 获取队列容量 /// </summary> /// <param name="queue"></param> /// <returns>队列容量</returns> size_t acf_queue_get_capacity(acf_queue* queue);

（9）清空队列
清除队列中的所有元素。

讯享网/// <summary> /// 清空队列 /// </summary> /// <param name="queue">队列对象的指针</param> void acf_queue_clear(acf_queue* queue);

（10）容量收缩
将队列数组长度，收缩至元素个数大小。

讯享网

/// <summary> /// 容量收缩 ///队列只会根据元素增加增容，不会根据元素减少减容，需要减容则调用此方法。 /// </summary> /// <param name="queue">队列对象的指针</param> void acf_queue_trim_excess(acf_queue* queue);

二、关键实现
1、动态增容

（1）malloc版本
malloc版本主要用于减容，即收缩数组的时候需要用到。

讯享网static int acf_queue_set_capacity_malloc(acf_queue* _this, size_t newCapacity) { 
    if (newCapacity < _this->_count) return 0; if (newCapacity == _this->_capacity) return 1; uint8_t* newData = NULL; if (newCapacity) { 
    newData = malloc(newCapacity * _this->_elementSize); if (_this->_count > 0) { 
    if (_this->_front < _this->_rear) { 
    memcpy(newData, _this->_data + (_this->_front) * _this->_elementSize, _this->_count * _this->_elementSize); } else { 
    memcpy(newData, _this->_data + (_this->_front) * _this->_elementSize, (_this->_capacity - _this->_front) * _this->_elementSize); memcpy(newData + (_this->_capacity - _this->_front) * _this->_elementSize, _this->_data, (_this->_rear) * _this->_elementSize); } } } _this->_front = 0; _this->_rear = _this->_count; _this->_capacity = newCapacity; _this->_data = newData; return 1; }

（2）realloc版本
realloc版本在倍速增容中比malloc版本效率高。具体实现如下。

static int acf_queue_set_capacity_realloc(acf_queue* _this, size_t newCapacity) { 
    if (newCapacity < _this->_count) return 0; if (newCapacity == _this->_capacity) return 1; if (newCapacity <_this->_capacity) return 0; uint8_t* newData = realloc(_this->_data, newCapacity * _this->_elementSize); if (!newData) return 0; _this->_data = newData; if (_this->_front >= _this->_rear) { 
    if (newCapacity - _this->_capacity < _this->_rear) { 
    memcpy(_this->_data + _this->_capacity * _this->_elementSize, _this->_data, (newCapacity - _this->_capacity) * _this->_elementSize); memmove(_this->_data, _this->_data + ((newCapacity - _this->_capacity) * _this->_elementSize), (_this->_rear - (newCapacity - _this->_capacity)) * _this->_elementSize); _this->_rear -= (newCapacity - _this->_capacity); } else { 
    memcpy(_this->_data + (_this->_capacity) * _this->_elementSize, _this->_data, _this->_rear * _this->_elementSize); _this->_rear = _this->_capacity + _this->_rear ; } } _this->_capacity = newCapacity; return 1; }

（3）组合
根据不同的情况使用不同的策略。这里只是简单的进行了数组容量判断，如果细化还可以根据元素个数在数组中的占比做出不同的选择策略。

讯享网static int acf_queue_set_capacity(acf_queue* _this, size_t newCapacity) { 
    if (newCapacity < _this->_capacity) { 
    acf_queue_set_capacity_malloc(_this, newCapacity); } else { 
    acf_queue_set_capacity_realloc(_this, newCapacity); } }

2、入队
入队前需要判断元素是否已满，已满则需要增容，增容方式是2倍增容。具体实现如下：

void acf_queue_enqueue(acf_queue* _this, void* pData) { 
    if (_this->_count == _this->_capacity) //队满 { 
    if (_this->_capacity < 4) acf_queue_set_capacity(_this, 4); else acf_queue_set_capacity(_this, _this->_capacity *2); } memcpy(_this->_data + _this->_rear * _this->_elementSize, pData, _this->_elementSize); _this->_rear = (_this->_rear + 1) % _this->_capacity; _this->_count++; }

3、容量收缩
当队列数组容量过大时，可以手动调用容量收缩方法以减少不必要的空间浪费。参照了c#的queue具体实现如下：

讯享网void acf_queue_trim_excess(acf_queue* _this) { 
    size_t threshold = (size_t)(((double)_this->_capacity) * 0.9); if (_this->_count < threshold) { 
    acf_queue_set_capacity(_this, _this->_count); } }

三、使用例子
1、整型元素
main.c

#include "Collection/acf_queue.h" #include<stdio.h> int main() { 
    acf_queue queue1; //初始化 acf_queue_init(&queue1, sizeof(int)); //入队 for (int i = 0; i < 50; i++) { 
    acf_queue_enqueue(&queue1, &i); } //获取元素个数 printf("count:%d\n", acf_queue_get_count(&queue1)); //获取数组容量 printf("capacity:%d\n", acf_queue_get_capacity(&queue1)); //容量收缩 acf_queue_trim_excess(&queue1); //获取数组容量 printf("trim capacity:%d\n", acf_queue_get_capacity(&queue1)); printf("dequeue:"); //出队 do { 
    int* pI = acf_queue_peek(&queue1); if (pI) printf("%d ", *pI); } while (acf_queue_dequeue(&queue1)); printf("\n"); //入队 for (int i = 0; i < 50; i++) { 
    acf_queue_enqueue(&queue1, &i); } //遍历队列 printf("traverse:"); for (int i = 0; i < 50; i++) { 
    int* pI = acf_queue_get_element(&queue1, i); if (pI) printf("%d ", *pI); } printf("\n"); //清除元素 acf_queue_clear(&queue1); printf("clear count:%d\n", acf_queue_get_count(&queue1)); //反初始化 acf_queue_deinit(&queue1); return 0; }

2、结构体元素

讯享网#include "Collection/acf_queue.h" #include<stdio.h> typedef struct { 
    int i; int j; }A; int main() { 
    acf_queue queue2; //初始化 acf_queue_init(&queue2, sizeof(A)); //入队 for (int i = 0; i < 50; i++) { 
    A a; a.i = i; a.j = i; acf_queue_enqueue(&queue2, &a); } //获取元素个数 printf("count:%d\n", acf_queue_get_count(&queue2)); //获取数组容量 printf("capacity:%d\n", acf_queue_get_capacity(&queue2)); //容量收缩 acf_queue_trim_excess(&queue2); //获取数组容量 printf("trim capacity:%d\n", acf_queue_get_capacity(&queue2)); printf("dequeue:"); //出队 do { 
    A* pA = acf_queue_peek(&queue2); if (pA) printf("%d ", pA->i); } while (acf_queue_dequeue(&queue2)); printf("\n"); //入队 for (int i = 0; i < 50; i++) { 
    A a; a.i = i; a.j = i; acf_queue_enqueue(&queue2, &a); } //遍历队列 printf("traverse:"); for (int i = 0; i < 50; i++) { 
    A* pA = acf_queue_get_element(&queue2, i); if (pA) printf("%d ", pA->j); } printf("\n"); //清除元素 acf_queue_clear(&queue2); printf("clear count:%d\n", acf_queue_get_count(&queue2)); //反初始化 acf_queue_deinit(&queue2); return 0; }

3、指针元素

#include "Collection/acf_queue.h" #include<stdio.h> #include<stdlib.h> typedef struct { 
    int i; int j; }A; int main() { 
    acf_queue queue3; //初始化 acf_queue_init(&queue3, sizeof(A*)); //入队 for (int i = 0; i < 50; i++) { 
    A* a = malloc(sizeof(A)); a->i = i; a->j = i; acf_queue_enqueue(&queue3, &a); } //获取元素个数 printf("count:%d\n", acf_queue_get_count(&queue3)); //获取数组容量 printf("capacity:%d\n", acf_queue_get_capacity(&queue3)); //容量收缩 acf_queue_trim_excess(&queue3); //获取数组容量 printf("trim capacity:%d\n", acf_queue_get_capacity(&queue3)); printf("dequeue:"); //出队 do { 
    A** pA = acf_queue_peek(&queue3); if (pA) { 
    printf("%d ", (*pA)->i); //释放资源防止内存泄漏 free(*pA); } } while (acf_queue_dequeue(&queue3)); printf("\n"); //入队 for (int i = 0; i < 50; i++) { 
    A* a = malloc(sizeof(A)); a->i = i; a->j = i; acf_queue_enqueue(&queue3, &a); } //遍历队列 printf("traverse:"); for (int i = 0; i < 50; i++) { 
    A** pA = acf_queue_get_element(&queue3, i); if (pA) { 
    printf("%d ", (*pA)->j); //释放资源防止内存泄漏 free(*pA); } } printf("\n"); //清除元素 acf_queue_clear(&queue3); printf("clear count:%d\n", acf_queue_get_count(&queue3)); //反初始化 acf_queue_deinit(&queue3); return 0; }

四、完整代码
https://download.csdn.net/download/u0/

2025年c语言实现动态增容循环队列

相关推荐