队列的基本用法

以下是关于 C 语言中队列的详细知识，包括队列的生成、相关函数使用以及其他重要概念：

一、队列的概念

队列是一种线性数据结构，它遵循先进先出（First In First Out，FIFO）的原则，就像日常生活中的排队一样，先进入队列的元素先被取出。队列有两个端点，一端是队头（front），用于删除元素；另一端是队尾（rear），用于插入元素。

二、队列的顺序存储结构实现（数组实现）

1. 结构体定义

#define MAX_SIZE 100  // 定义队列的最大容量，可根据实际需求调整typedef struct {int data[MAX_SIZE];  // 存放队列元素的数组int front;  // 队头指针int rear;   // 队尾指针
} Queue;

1. 队列的初始化

// 初始化队列
void initQueue(Queue *q) {q->front = 0;q->rear = 0;
}

1. 判断队列是否为空

// 判断队列是否为空
int isEmpty(Queue *q) {return q->front == q->rear;
}

1. 判断队列是否已满（针对顺序存储的循环队列情况）

// 判断队列是否已满（循环队列）
int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}

1. 入队操作（向队尾插入元素）

// 入队操作
void enqueue(Queue *q, int element) {if (isFull(q)) {printf("队列已满，无法入队\n");return;}q->data[q->rear] = element;q->rear = (q->rear + 1) % MAX_SIZE;
}

1. 出队操作（从队头删除元素）

// 出队操作
int dequeue(Queue *q) {if (isEmpty(q)) {printf("队列为空，无法出队\n");return -1;  // 可以根据实际情况返回合适的错误标识}int element = q->data[q->front];q->front = (q->front + 1) % MAX_SIZE;return element;
}

三、队列的链式存储结构实现（链表实现）

1. 节点结构体定义

typedef struct QNode {int data;struct QNode *next;
} QNode;

1. 队列结构体定义（包含队头和队尾指针）

typedef struct {QNode *front;QNode *rear;
} LinkQueue;

1. 队列的初始化

// 初始化链式队列
void initLinkQueue(LinkQueue *q) {q->front = q->rear = (QNode *)malloc(sizeof(QNode));if (!q->front) {printf("内存分配失败\n");exit(1);}q->front->next = NULL;
}

1. 判断链式队列是否为空

// 判断链式队列是否为空
int isEmptyLinkQueue(LinkQueue *q) {return q->front == q->rear;
}

1. 入队操作（向链式队列的队尾插入节点）

// 链式队列入队操作
void enqueueLinkQueue(LinkQueue *q, int element) {QNode *newNode = (QNode *)malloc(sizeof(QNode));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->data = element;newNode->next = NULL;q->rear->next = newNode;q->rear = newNode;
}

1. 出队操作（从链式队列的队头删除节点）

// 链式队列出队操作
int dequeueLinkQueue(LinkQueue *q) {if (isEmptyLinkQueue(q)) {printf("队列为空，无法出队\n");return -1;  // 同样可按需返回错误标识}QNode *temp = q->front->next;int element = temp->data;q->front->next = temp->next;if (q->rear == temp) {  // 如果删除的是最后一个节点，要更新队尾指针q->rear = q->front;}free(temp);return element;
}

四、队列的应用场景

• 广度优先搜索（BFS）：在图的遍历算法中，比如在迷宫求解、寻找最短路径等场景下，利用队列来存储待访问的节点，按照层次依次访问节点。
• 操作系统中的任务调度：可以将等待执行的进程等任务放入队列中，按照先来先服务等调度策略依次执行。
• 消息队列：在多线程、多进程通信或者分布式系统中，用于暂存消息，实现异步通信，保证消息按照发送顺序依次被处理。

五、队列操作的时间复杂度分析

• 入队操作：
  • 对于顺序存储的队列（循环队列情况），入队操作平均时间复杂度是0(1)，只是对队尾指针进行简单的更新和赋值操作（在不考虑已满的判断情况下，已满判断通常也是常数时间复杂度的操作）。
  • 对于链式存储的队列，入队操作也是0(1)，主要涉及到创建新节点、调整指针等常数时间内可完成的操作。
• 出队操作：
  • 顺序存储的队列出队操作同样平均时间复杂度为0(1)，对队头指针进行更新和获取元素操作（不考虑队列为空的判断情况）。
  • 链式存储的队列出队操作也是0(1)，主要是调整指针和释放节点内存等操作，时间消耗不随队列元素个数线性增长。