当前位置：首页 > news >正文

队列算法【基于顺序表的环形队列】

news 来源：原创 2024/9/18 17:35:58

代码如下所示：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*【环形缓冲区（顺序表版本）】*/
typedef struct
{int* data;int size;
}g_tVector;
/* 顺序表的初始化 */
void VectorInit(g_tVector* vector, int len)
{if (NULL == vector)  return;vector->data = (int*)malloc(sizeof(int) * len);vector->size = len;return;
}
/* 顺序表的清理 */
void VectorClear(g_tVector* vector)
{if (NULL == vector)  return;free(vector->data);return;
}
/* 顺序表的写入数据 */
bool VectorWrite(g_tVector* vector, int index , int data)
{if (NULL == vector)  return false;vector->data[index] = data;return true;
}
/* 顺序表的读出数据 */
bool VectorRead(g_tVector* vector, int index, int** data)
{if (NULL == vector)  return false;**data = vector->data[index];return true;
}/************************************************/
typedef struct
{g_tVector* vector;int count, head, tail, len;void (*vectorInit)(g_tVector*, int);void (*vectorClear)(g_tVector*);bool (*vectorWrite)(g_tVector*, int, int);bool (*vectorRead)(g_tVector*, int, int**);
}g_tQueue;/* 环形缓冲区的初始化 */
void QueueInit(g_tQueue* queue, int len)
{if (NULL == queue) return;queue->vector = (g_tVector*)malloc(sizeof(g_tVector));queue->vectorInit = VectorInit;queue->vectorClear = VectorClear;queue->vectorRead = VectorRead;queue->vectorWrite = VectorWrite;queue->vectorInit(queue->vector, len);queue->len = len;queue->head = queue->tail = queue->count = 0;printf("init:%d, %d, %d, %d\r\n", queue->len, queue->count, queue->head, queue->tail);return;
}/* 环形缓冲区申请内存的释放 */
void QueueClear(g_tQueue* queue)
{if (NULL == queue) return;VectorClear(queue->vector);free(queue->vector);free(queue);return;
}bool QueueIsEmpty(g_tQueue* queue)
{if (NULL == queue) return false;return (queue->count == 0);
}bool QueueIsFull(g_tQueue* queue)
{if (NULL == queue) return false;//printf("data:%d, %d\r\n", queue->count, queue->len);return (queue->count == queue->len);
}/* 从环形缓冲区取出数据 */
bool PopQueue(g_tQueue* queue, int* data)
{if ((NULL == queue)|| (NULL == data) || QueueIsEmpty(queue)) return false;queue->vectorRead(queue->vector, queue->head, &data);if (queue->head < queue->len-1)queue->head++;      //头部索引向后移动elsequeue->head = 0;    //头部指向尾部queue->count--;   //环形缓冲区存储的数据量return true;
}
/* 向环形缓冲区压入数据 */
bool PushQueue(g_tQueue* queue, int data)
{if ((NULL == queue) || QueueIsFull(queue)) return false;queue->vectorWrite(queue->vector, queue->tail, data);if (queue->tail < queue->len-1)queue->tail++;elsequeue->tail = 0;queue->count++;return true;
}int main()
{g_tQueue queue;bool ret;int data;QueueInit(&queue, 5);for (int i = 0; i < 6; i++){data = rand() % 100;ret = PushQueue(&queue, data);if (!ret)printf("%d push is error\r\n", i);elseprintf("push %d\r\n", data);}ret = PopQueue(&queue, &data);if (ret)printf("pop data is %d\r\n", data);return 0;
}

运行结果如下所示：