本文共 2675 字,大约阅读时间需要 8 分钟。
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列的特性总结为:先进先出。
这种特性在日常中类似于排队,先来的先进行服务!我们使用链表实现队列,一个头节点和一个节点表示队列的头部和尾部。出队列和入队列的时间复杂度为 O(1)。空间复杂度为 O(n)
队列是只允许在一端进行插入操作,在另外一段进行删除操作的线性表,队列不允许在中间部位进行操作
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
双端队列是一种两端都可以 删除元素和追加元素的线性结构。双端队列比普通的队列更加灵活。双端队列可以用双向链表实现。
单向队列的实现方式:
#include#include typedef struct Node{ // 节点的值 int val; // 节点的在一个节点 struct Node *next;} Node;typedef struct Queue{ /* data */ // 队列的头节点 Node *head; // 队列的尾节点 Node *tail; // 队列的元素数量 int len;} Queue;// 初始化队列Queue *init(){ // 申请空间 Queue *q = malloc(sizeof(Queue)); // 初始化成员属性 q->head = q->tail = NULL; q->len = 0; return q;}
// 元素入队列void push(Queue *q, int val){ // 申请空间 Node *node = malloc(sizeof(Node)); node->val = val; node->next = NULL; // 判断队列是不是为空 if (q->len == 0) { // 直接赋值 q->head = q->tail = node; } else { // 将元素添加至队列末尾 q->tail->next = node; q->tail = node; } // 长度 + 1 q->len++;}
// 元素出队列int pop(Queue *q){ if (q->len > 0) { // 获取头节点的值 Node *h = q->head; int val = h->val; // 没有其他元素重置为NULL if (h->next == NULL) { q->head = q->tail = NULL; } else { q->head = h->next; } // 释放节点空间 free(h); q->len--; return val; } return 0xFFFFFF;}
// 返回队列的长度int size(Queue *q){ if (q == NULL) { return -1; } return q->len;}void printQueue(Queue *q){ if (q != NULL) { Node *h = q->head; while (h != NULL) { printf("%d->", h->val); h = h->next; } printf("\n"); }}// 销毁队列void destory(Queue *q){ if (q != NULL) { // 逐个释放节点的元素 Node *h = q->tail; while (h != NULL) { free(h); h = h->next; } // 释放队列 free(q); }}
int main(){ Queue *queue = init(); push(queue, 10); push(queue, 11); push(queue, 12); push(queue, 13); push(queue, 14); printQueue(queue); printf("%d\n", size(queue)); printf("%d\n", pop(queue)); printf("%d\n", size(queue)); printQueue(queue); destory(queue); return 0;}/*10->11->12->13->14->510411->12->13->14->*/
从队列的特性中我们可以看到,队列主要用在先来先服务的场景中。生活中与之相关的就是 12306 的候补买票了以及一些排队的场景下,这种顺序服务的思想在一些消息队列当中也有体现。
相关的代码我已上传到 gitlab:
此后的数据结构代码我都会上传在这个仓库中,需要的同学可以自己下载
感谢你能看到这里,欢迎关注我的 vx 公众号:元泱界 zz,学习更多的知识!我们下期再见!
转载地址:http://gtden.baihongyu.com/