队列的基本概念
队列是一种**先进先出(FIFO, First In First Out)**的线性数据结构。它只允许在队尾进行插入操作,在队头进行删除操作。这种特性使得队列非常适合处理需要按顺序排队等待的任务。
生活中的队列场景很常见,比如银行窗口排队、打印机任务列表,或者消息中间件里的消息传递,本质上都是队列的应用。
队列的核心操作
实现一个队列,通常包含以下几个基础操作:
- 初始化(InitQueue):创建一个空队列,分配必要的内存资源。
- 入队(EnQueue):将新元素添加到队尾。
- 出队(DeQueue):从队头移除并返回元素。
- 获取队头元素(GetFront):查看队头数据但不移除。
- 判空(IsEmpty):检查队列是否没有元素。
- 销毁(DestroyQueue):释放队列占用的所有内存,防止泄漏。
C 语言实现队列
顺序队列(数组实现)
顺序队列利用数组存储元素,通过 front 和 rear 指针标记边界。为了节省空间并解决'假溢出'问题,我们通常采用循环队列的设计思路。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 顺序队列结构体
typedef struct {
int data[MAX_SIZE];
int front; // 队头指针(指向队头元素)
int rear; // 队尾指针(指向队尾元素的下一个位置)
} SeqQueue;
// 初始化队列
void InitQueue(SeqQueue *q) {
q->front = 0;
q->rear = 0;
}
// 判空
int IsEmpty(SeqQueue *q) {
return q->front == q->rear;
}
// 判满
int IsFull(SeqQueue *q) {
// 预留一个空间区分空满状态
(q->rear + ) % MAX_SIZE == q->front;
}
{
(IsFull(q)) {
();
;
}
q->data[q->rear] = value;
q->rear = (q->rear + ) % MAX_SIZE;
;
}
{
(IsEmpty(q)) {
();
;
}
*value = q->data[q->front];
q->front = (q->front + ) % MAX_SIZE;
;
}
{
(IsEmpty(q)) {
();
;
}
*value = q->data[q->front];
;
}
{
SeqQueue q;
InitQueue(&q);
EnQueue(&q, );
EnQueue(&q, );
EnQueue(&q, );
frontVal;
GetFront(&q, &frontVal);
(, frontVal);
deVal;
DeQueue(&q, &deVal);
(, deVal);
GetFront(&q, &frontVal);
(, frontVal);
;
}


