C语言-数据结构-队列

目录

1.队列的特点

2.队列的实现

2.1.初始化队列

2.2.入队列

2.2.1.入空队列

2.2.2.入非空队列

2.3.出队列

2.4.销毁队列

2.5.完整代码

3.实际应用

---

1.队列的特点

        队列是一种常见的数据结构，它遵循先进先出（FIFO, First In First Out）原则，即先加入队列的元素先被处理（出队），后加入的元素后处理，这一点和栈的特性完全相反。队列广泛应用于计算机科学中，尤其是在任务调度、消息传递、数据缓存等场景中。

        那么关于队列的核心就是先进先出，后进后出。

2.队列的实现

        首先需要确定队列的数据结构如何设计？

        核心思路:使用单链表挂载数据节点，队列的队头指针和队尾指针指向链表头和链表尾

        由于队列不同于栈的特性，队列可以两端操作，因此需要两个指针来维护队头和队尾，那么最基本的队列的结构就可以设计出来了，如下：

/* 数据节点 */
typedef struct _DataNode {u32 data;struct _DataNode *next;
}DataNode;/* 队列 */
typedef struct _Queue {struct _DataNode *head;struct _DataNode *tail;u32 size;
}Queue;

        队列中还加入了队列大小size属性，这里如果做的更通用一些还可以考虑多线程场景，加入锁等，可根据实际需要自行调整。

2.1.初始化队列

        初始化队列就是初始化对象的过程，申请内存然后初始化队列的成员，最后返回队列即可，刚开始初始化队列，队列为空，将队头队尾指针置空即可。

/* 初始化队列 */
Queue *init_queue() {Queue *q = NULL;q = (Queue *)malloc(sizeof(Queue));if (!q) {return NULL;}q->size = 0;q->head = NULL;q->tail = NULL;return q;
}

2.2.入队列

        入队列需要考虑的问题稍微复杂一些，首先要考虑的是空队列怎么办？非空队列怎么办？

        空队列和非空队列的头尾指针的指向是不一样的~~~

2.2.1.入空队列

        入空队列操作简单，创建数据节点，将队头队尾指针都指向该数据节点即可，因为此时只有一个数据节点。

2.2.2.入非空队列

        入非空队列的过程即队头指针的指向不变，队尾指针指向新的节点，也就是说原来队尾指针的next指向新节点，新队尾指针指向新的节点。

入队列完整代码如下：

/* 入队列 */
u8 enqueue(Queue *q, u32 data) {DataNode *new = NULL;new = (DataNode *)malloc(sizeof(DataNode));if (!new) {return FALSE; }new->data = data;new->next = NULL;printf("info, enqueue addr:%p\n", new);/* 空队列 */if (q->size == 0) {    q->head = new;q->tail = new;}else {q->tail->next = new;q->tail = new;}q->size++;return TRUE;
}

2.3.出队列

        出队列的过程和入队列相反，只需要修改队头指针即可，然后返回原有的队头节点即可。

出队完整代码如下：

/* 出队列 */
DataNode *dequeue(Queue *q) {DataNode *node = NULL;if (q->size) {node = q->head;q->head = q->head->next;q->size--;}printf("info, dequeue addr:%p\n", node);return node;
}

2.4.销毁队列

        销毁队列的过程和出队列的过程类似，只需要从队头开始遍历，直到队列中没有元素为止。

/* 销毁队列 */
void destory_queue(Queue *que) {if (!que) {return;}while(que->size) {DataNode *node = que->head;printf("info, destory_queue addr:%p\n", node);que->head = que->head->next;free(node);node = NULL;que->size--;}free(que);que = NULL;
}

2.5.完整代码

#include <stdio.h>
#include <stdlib.h>typedef unsigned char u8;
typedef unsigned int u32;#define FALSE 0
#define TRUE 1/* 数据节点 */
typedef struct _DataNode {u32 data;struct _DataNode *next;
}DataNode;/* 队列 */
typedef struct _Queue {struct _DataNode *head;struct _DataNode *tail;u32 size;
}Queue;/* 初始化队列 */
Queue *init_queue() {Queue *q = NULL;q = (Queue *)malloc(sizeof(Queue));if (!q) {return NULL;}q->size = 0;q->head = NULL;q->tail = NULL;return q;
}/* 销毁队列 */
void destory_queue(Queue *que) {if (!que) {return;}while(que->size) {DataNode *node = que->head;printf("info, destory_queue addr:%p\n", node);que->head = que->head->next;free(node);node = NULL;que->size--;}free(que);que = NULL;
}/* 入队列 */
u8 enqueue(Queue *q, u32 data) {DataNode *new = NULL;new = (DataNode *)malloc(sizeof(DataNode));if (!new) {return FALSE; }new->data = data;new->next = NULL;printf("info, enqueue addr:%p\n", new);/* 空队列 */if (q->size == 0) {    q->head = new;q->tail = new;}else {q->tail->next = new;q->tail = new;}q->size++;return TRUE;
}/* 出队列 */
DataNode *dequeue(Queue *q) {DataNode *node = NULL;if (q->size) {node = q->head;q->head = q->head->next;q->size--;}printf("info, dequeue addr:%p\n", node);return node;
}int main() {Queue *que = NULL;que = init_queue();if (!que) {printf("init queue failed !\n");return -1;}if (!enqueue(que, 10)) {printf("enqueue failed !\n");return -1;}if (!enqueue(que, 100)) {printf("enqueue failed !\n");return -1;}DataNode *node = dequeue(que);printf("info, dequeue node value:%u\n", node->data);free(node);node = NULL;destory_queue(que);return 0;
}

运行结果：

3.实际应用

dpdk中关于ring的描述：

        dpdk中关于环形队列的设计非常巧妙，感兴趣的可以自行研究。