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

数据结构：队列

news 来源：原创 2025/5/17 20:52:59

1.概念：

和栈相反，队列是一种先进先出的线性表它只允许在标的一段进行插入，而在另一端进行删除元素。这和我们日常生活中的排队是一致的，即最早入队的元素最早离开。队列中允许插入的一端叫做队尾，允许删除的一端的叫队头。

2.队列的基本操作：

1.入队

2.出队

3.队列初始化，判空以及获取出队元素

3.代码实现

一.链队列（队列用链表表示和实现）

#include <stdio.h>
#include <stdlib.h>typedef struct qnode {int data;struct qnode* next;
} qnode, *qptr;typedef struct {qptr front;qptr rear;
} linkq;// 初始化队列
void initq(linkq* q) {q->front = q->rear = (qptr)malloc(sizeof(qnode));q->front->next = NULL;  // 初始化时，队列为空，front 和 rear 都指向头节点
}// 入队操作
void enquence(linkq* q, int e) {qptr p = (qptr)malloc(sizeof(qnode));p->data = e;p->next = NULL;q->rear->next = p;q->rear = p;printf("入队元素为：%d\n", e);
}// 出队操作
int dequence(linkq* q, int* e) {if (q->front == q->rear) {printf("队列为空，无法出队\n");return -1;  // 返回-1表示队列为空}qptr p = q->front->next;*e = p->data;q->front->next = p->next;if (q->rear == p) {q->rear = q->front;  // 如果出队的是最后一个元素，rear 需要指向 front}free(p);return 0;  // 返回0表示出队成功
}int main() {linkq q;int e, e1, e2;initq(&q);  // 初始化队列enquence(&q, 0);  // 入队元素0enquence(&q, 1);  // 入队元素1enquence(&q, 2);  // 入队元素2if (dequence(&q, &e) == 0) {  // 出队元素0printf("出队元素为：%d\n", e);}if (dequence(&q, &e1) == 0) {  // 出队元素1printf("出队元素为：%d\n", e1);}if (dequence(&q, &e2) == 0) {  // 出队元素2printf("出队元素为：%d\n", e2);}return 0;
}

运行结果

入队元素为：0
入队元素为：1
入队元素为：2
出队元素为：0
出队元素为：1
出队元素为：2

二.循环队列（队列的顺序表示和实现）

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100typedef struct {int *base;  // 队列的存储空间int front;  // 队头指针int rear;   // 队尾指针
} sq;// 初始化队列
void init(sq *p) {p->base = (int *)malloc(MAXSIZE * sizeof(int));  // 分配足够的空间if (p->base == NULL) {printf("内存分配失败\n");exit(1);  // 如果分配失败，退出程序}p->front = p->rear = 0;  // 初始化队头和队尾
}// 计算队列长度
int sqlength(sq p) {return (p.rear - p.front + MAXSIZE) % MAXSIZE;
}// 入队操作
void ensq(sq *p, int e) {if ((p->rear + 1) % MAXSIZE == p->front) {  // 判断队列是否已满printf("队列已满，无法入队\n");return;}p->base[p->rear] = e;  // 将元素插入队尾p->rear = (p->rear + 1) % MAXSIZE;  // 队尾指针后移printf("入队元素为：%d\n", e);
}// 出队操作
int desq(sq *p) {if (p->front == p->rear) {  // 判断队列是否为空printf("队列为空，无法出队\n");return -1;  // 返回-1表示队列为空}int e = p->base[p->front];  // 获取队头元素p->front = (p->front + 1) % MAXSIZE;  // 队头指针后移return e;  // 返回出队元素
}int main() {sq p;int e1, e2, e3;init(&p);  // 初始化队列ensq(&p, 1);  // 入队元素1ensq(&p, 2);  // 入队元素2ensq(&p, 3);  // 入队元素3e1 = desq(&p);  // 出队元素1if (e1 != -1) {printf("出队元素为：%d\n", e1);}e2 = desq(&p);  // 出队元素2if (e2 != -1) {printf("出队元素为：%d\n", e2);}e3 = desq(&p);  // 出队元素3if (e3 != -1) {printf("出队元素为：%d\n", e3);}free(p.base);  // 释放队列的存储空间return 0;
}

运行结果

入队元素为：1
入队元素为：2
入队元素为：3
出队元素为：1
出队元素为：2
出队元素为：3

4.应用场景：

顺序队列：适合元素数量固定的场景，需要处理“假溢出”问题。
链式队列：适合元素数量不固定的场景，动态分配内存，无需担心队列大小限制。
队列的应用场景包括任务调度、缓冲区管理、广度优先搜索（BFS）等。

5.优缺点：

优点：
1.顺序性保障：严格按顺序处理数据：队列确保元素按到达顺序被处理，适用于需保证公平性的场景（如打印机任务调度）。
应用示例：广度优先搜索（BFS）算法依赖队列
维护待访问节点的顺序。
2.缓冲作用
速率匹配：平衡生产者和消费者的处理速度差异（如视频流缓冲）。
3.实现简单高效

时间复杂度低：入队和出队操作在数组/链表实现中均可达到**O(1)**时间复杂度。内存连续性：数组实现的队列（如循环队列）能利用CPU缓存局部性优势。
缺点：
1.访问限制
无法随机访问：中间元素需逐个出队才能访问，时间复杂度升至O(n)。
2.容量限制
固定大小问题：循环队列需预分配空间，动态扩容可能引发性能抖动。示例：Java的 ArrayBlockingQueue 需预设容量，而 LinkedBlockingQueue支持无界但有内
存风险。
3.并发复杂度
线程安全开销：并发队列（如ConcurrentLinkedQueue）需通过CAS操作保证安全，增加实现难度。

1.概念：

2.队列的基本操作：

3.代码实现

4.应用场景：

5.优缺点：

相关文章：