1队列的定义和操作
1.1队列的定义和特性
一 队列的定义
队列是一种特殊的线性表，它只允许在表的一端进行插入操作，而在另一端进行删除操作。进行插入操作的一端称为队尾（rear），进行删除操作的一端称为队头（front）。
二 队列的特性
- 先进先出（FIFO，First In First Out）
- 就像在生活中的排队一样，最先进入队列的元素将最先被取出。例如，在银行排队办理业务，先来的客户先得到服务。
- 操作受限
- 插入操作只能在队尾进行，删除操作只能在队头进行。这保证了队列的有序性和特定的操作方式。
- 动态性
- 队列的长度可以根据实际需求动态变化。可以不断地向队列中插入元素，也可以从队列中删除元素。
三、队列的应用场景
队列广泛应用于各种场景，如：
- 任务调度：操作系统中的任务队列。
- 广度优先搜索（BFS）：图搜索算法。
- 消息传递：多线程编程中的消息队列。
- 打印任务：打印机中的打印任务队列
12队列的基本操作
1. 入队（Enqueue）
定义：将一个元素添加到队列的尾部。
操作步骤：
- 检查队列是否已满（对于固定容量的队列）。
- 如果队列不满，则将新元素插入到队列的尾部，并更新尾指针。
示例代码（C语言）:
void enqueue(Queue *q, int value) {if (isFull(q)) {printf("队列已满，无法入队！\n");return;}if (isEmpty(q)) {q->front = 0; // 如果队列为空，初始化 front}q->rear = (q->rear + 1) % MAX_SIZE; // 循环队列的尾指针更新q->data[q->rear] = value; // 将新元素加入队列
}
2. 出队（Dequeue）
定义：从队列的头部移除一个元素，并返回该元素。
操作步骤：
- 检查队列是否为空。
- 如果队列不为空，则移除并返回队首元素，更新头指针。
- 如果出队后队列为空，将头和尾指针重置。
示例代码（C语言）:
int dequeue(Queue *q) {if (isEmpty(q)) {printf("队列为空，无法出队！\n");return -1; // 或者返回其他标志}int value = q->data[q->front]; // 获取队首元素if (q->front == q->rear) {// 如果出队后队列为空q->front = -1;q->rear = -1;} else {q->front = (q->front + 1) % MAX_SIZE; // 循环队列的头指针更新}return value; // 返回出队的元素
}
3. 查看队首元素（Front）
定义：获取队列头部的元素，但不移除它。
操作步骤：
- 检查队列是否为空，为空则无法获取队首元素。
- 如果不为空，返回队首元素的值。
示例代码（C语言）:
int front(Queue *q) {if (isEmpty(q)) {printf("队列为空，无法获取队首元素！\n");return -1; // 或者返回其他标志}return q->data[q->front]; // 返回队首元素
}
4. 查看队尾元素（Rear）
定义：获取队列尾部的元素，但不移除它。
操作步骤：
- 检查队列是否为空。
- 如果不为空，返回队尾元素的值。
示例代码（C语言）:
int rear(Queue *q) {if (isEmpty(q)) {printf("队列为空，无法获取队尾元素！\n");return -1; // 或者返回其他标志}return q->data[q->rear]; // 返回队尾元素
}
5. 判断队列是否为空（IsEmpty）
定义：检查队列是否为空。
操作步骤：
- 比较队首指针和尾指针，如果相等且队首指针不为 -1，则队列为空。
示例代码（C语言）:
int isEmpty(Queue *q) {return q->front == -1; // 返回队列是否为空的布尔值
}
6. 判断队列是否已满（IsFull）
定义：检查队列是否已满（适用于固定容量的队列）。
操作步骤：
- 判断尾指针是否在队首指针的前一个位置。
示例代码（C语言）:
int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front; // 返回队列是否满的布尔值
}
7. 获取队列大小（Size）
定义：获取队列中当前元素的数量。
操作步骤：
- 根据队首和队尾的指针计算元素数量。
示例代码（C语言）:
int size(Queue *q) {if (isEmpty(q)) {return 0; // 如果队列为空，返回0}return (q->rear - q->front + MAX_SIZE) % MAX_SIZE + 1; // 计算队列的当前大小
}2队列的存储与实现
2.1顺序队列
一顺序队列的定义和运算
定义
顺序队列是队列的顺序存储结构，用一个向量空间（即数组）来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因此需要设置两个指针front和rear，分别指示队头元素和队尾元素在向量空间中的位置。
- 队头指针（front）：指向队头元素的位置。
- 队尾指针（rear）：指向队尾元素的下一个位置，即新元素应该插入的位置。
初始化时，front和rear的初值通常都设置为0。
顺序队列结构体定义
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 队列最大容量typedef struct {int data[MAX_SIZE]; // 队列存储数组int front; // 队列头指针int rear; // 队列尾指针
} SequentialQueue;
1. 初始化队列
void initQueue(SequentialQueue *q) {q->front = 0; // 指向队列的第一个元素q->rear = 0; // 队尾指向队列已存放的元素位置
}
2. 判断队列是否为空
int isEmpty(SequentialQueue *q) {return q->front == q->rear; // 如果 front 和 rear 指针相等，则队列为空
}
3. 判断队列是否已满
int isFull(SequentialQueue *q) {return (q->rear + 1) % MAX_SIZE == q->front; // 判断是否满
}
4. 入队操作（Enqueue）
void enqueue(SequentialQueue *q, int value) {if (isFull(q)) {printf("队列已满，无法入队！\n");return;}if (isEmpty(q)) {q->front = 0; // 当队列为空时，初始化 front}q->rear++; // 更新队尾指针q->data[q->rear] = value; // 在尾部插入新元素
}5. 出队操作（Dequeue）
int dequeue(SequentialQueue *q) {if (isEmpty(q)) {printf("队列为空，无法出队！\n");return -1; // 返回特殊值表示队列为空}int value = q->data[q->front]; // 获取队头元素// 检查出队后是否需要重置队列if (q->front == q->rear) {// 如果出队后队列为空，需要重置队列q->front = -1;q->rear = -1;} else {// 更新队首指针q->front++;}return value; // 返回出队的元素
}6. 查看队首元素（Front）
int front(SequentialQueue *q) {if (isEmpty(q)) {printf("队列为空，无法获取队首元素！\n");return -1;}return q->data[q->front]; // 返回队首元素
}
7. 查看队尾元素（Rear）
int rear(SequentialQueue *q) {if (isEmpty(q)) {printf("队列为空，无法获取队尾元素！\n");return -1; // 返回特殊值表示队列为空}return q->data[q->rear]; // 返回队尾元素
}8. 获取队列大小（Size）
int size(SequentialQueue *q) {if (isEmpty(q)) {return 0; // 当队列为空则返回大小为0}return q->rear - q->front + 1; // 计算当前大小
}2.2循环顺序队列
循环顺序队列，简称循环队列，是一种特殊的顺序队列，其特点在于将队列的存储空间视为一个逻辑上的环状空间，从而实现了队列的循环利用。以下是关于循环顺序队列的详细介绍：
定义与结构
循环队列是将顺序队列的首尾相连，形成一个逻辑上的环状空间。在循环队列中，当存储空间的最后一个位置已被使用而再要进行入队操作时，如果存储空间的第一个位置空闲，那么就可以将新元素插入到第一个位置，此时将存储空间的第一个位置视为队尾。
循环队列通常使用一个数组来存储队列元素，并设置两个指针front和rear来分别指示队头和队尾的位置。front指向队头元素的位置，而rear指向队尾元素的下一个位置（即新元素应该插入的位置）。
1. 循环顺序队列的结构体定义
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 队列最大容量typedef struct {int data[MAX_SIZE]; // 队列存储数组int front; // 队列头指针int rear; // 队列尾指针
} CircularQueue;
2. 初始化队列
void initQueue(CircularQueue *q) {q->front = 0; // 队列头指针q->rear = 0; // 队列尾指针
}
3. 判断队列是否为空
int isEmpty(CircularQueue *q) {return q->front == q->rear; // 如果 front 和 rear 指针相等，则队列为空
}
4. 判断队列是否已满
在判断队列是否已满时，使用 (q->rear + 1) % MAX_SIZE == q->front 条件来判断队列是否已满。
int isFull(CircularQueue *q) {return (q->rear + 1) % MAX_SIZE == q->front; // 判断是否满
}
(q->rear + 1) % MAX_SIZE：计算rear的下一个位置。如果rear现在在数组的末尾（MAX_SIZE - 1），则(q->rear + 1) % MAX_SIZE会回绕到数组的开始（即0）。== q->front：如果计算出的下一个rear位置与front位置相同，则表示队列已满，没有空余位置可以插入新元素。
5. 入队操作（Enqueue）
在入队操作中，rear 指针需要移动到下一个位置以存储新的元素。由于队列是循环的，当 rear 达到数组的末尾时，它需要回绕到数组的开头。
void enqueue(CircularQueue *q, int value) {if (isFull(q)) {printf("队列已满，无法入队！\n");return;}q->data[q->rear] = value; // 在尾部插入新元素q->rear = (q->rear + 1) % MAX_SIZE; // 更新尾指针，循环使用
}
q->data[q->rear] = value;：将新元素插入到当前rear指针所指向的位置。q->rear = (q->rear + 1) % MAX_SIZE;：计算rear的下一个位置。如果rear已经到达数组的末尾（MAX_SIZE - 1），则下一次rear会回绕到数组的开始（即rear = 0）。
6. 出队操作（Dequeue）
在出队操作中，front 指针也需要移动到下一个位置以移除当前元素。由于队列是循环的，当 front 达到数组的末尾时，它需要回绕到数组的开头。
int dequeue(CircularQueue *q) {if (isEmpty(q)) {printf("队列为空，无法出队！\n");return -1; // 返回特殊值表示队列为空}int value = q->data[q->front]; // 获取队头元素q->front = (q->front + 1) % MAX_SIZE; // 循环更新队头指针return value; // 返回出队的元素
}
q->data[q->front];：获取当前front指针所指向的元素，即队头元素。q->front = (q->front + 1) % MAX_SIZE;：计算front的下一个位置。如果front已经到达数组的末尾（MAX_SIZE - 1），则下一次front会回绕到数组的开始（即front = 0）。
例子
假设 MAX_SIZE 为 5，当前队列的状态如下：
front：指向0。rear：指向4（即数组的最后一个位置）。
现在我们尝试进行一次入队操作：
- 插入元素前的
rear：4 - 插入元素后的
rear：(4 + 1) % 5 = 0（回绕到数组的开始）
此时，rear 指向下一个要插入的位置 0，如果再次判断队列是否已满：
(0 + 1) % 5 == 0 // 结果为 1 == 0 (假)
结果为假，表示队列未满。
如果 front 也移动到 1，并且 rear 仍然是 0，那么再次尝试判断满的条件：
(0 + 1) % 5 == 1 // 结果为 1 == 1 (真)
这时结果为真，表示队列已满。
2.3链式队列
链式队列的基本结构包括：
-
节点（Node）：链表中的每个元素称为节点，包含两个部分：
- 数据域（data）：存储节点中的数据。
- 指针域（next）：指向下一个节点的指针。
-
队列（Queue）：队列包含两个指针：
front：指向队列头部的指针。rear：指向队列尾部的指针。
链式队列的操作
链式队列的基本操作包括：
- 初始化队列：初始化队列时，
front和rear都指向NULL，表示队列为空。 - 入队（Enqueue）：在队列尾部插入一个新节点。
- 出队（Dequeue）：从队列头部移除一个节点。
- 判断队列是否为空：检查
front是否指向NULL。 - 获取队列头部元素：获取队列头部的值，但不移除节点。
下面是链式队列的实现代码示例：
#include <stdio.h>
#include <stdlib.h>// 定义节点结构体
typedef struct Node {int data; // 数据struct Node* next; // 指向下一个节点的指针
} Node;// 定义队列结构体
typedef struct Queue {Node* front; // 队列头部指针Node* rear; // 队列尾部指针
} Queue;// 初始化队列
void initQueue(Queue* q) {q->front = NULL;q->rear = NULL;
}// 判断队列是否为空
int isEmpty(Queue* q) {return q->front == NULL;
}// 入队操作
void enqueue(Queue* q, int value) {// 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败！\n");return;}newNode->data = value;newNode->next = NULL;// 如果是空队列，front 和 rear 都指向新节点if (isEmpty(q)) {q->front = newNode;q->rear = newNode;} else {// 否则，将新节点添加到 rear 后面，并更新 rearq->rear->next = newNode;q->rear = newNode;}
}// 出队操作
int dequeue(Queue* q) {if (isEmpty(q)) {printf("队列为空，无法出队！\n");return -1; // 返回特殊值表示队列为空}// 获取队头元素int value = q->front->data;Node* temp = q->front; // 临时指针指向队头节点// 更新 frontq->front = q->front->next;// 如果出队后队列为空，rear 也要更新if (q->front == NULL) {q->rear = NULL;}// 释放原队头节点的内存free(temp);return value; // 返回出队的元素
}// 获取队列头部元素
int getFront(Queue* q) {if (isEmpty(q)) {printf("队列为空！\n");return -1; // 返回特殊值表示队列为空}return q->front->data;
}// 主程序
int main() {Queue q;initQueue(&q);// 入队操作示例enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);// 输出当前出队元素printf("出队元素: %d\n", dequeue(&q)); // 输出: 10printf("出队元素: %d\n", dequeue(&q)); // 输出: 20// 新的入队操作printf("入队元素: 40\n");enqueue(&q, 40);// 输出队列头部元素printf("队列头部元素: %d\n", getFront(&q)); // 输出: 30// 测试更多的入队和出队操作printf("入队元素: 50\n");enqueue(&q, 50);printf("入队元素: 60\n");enqueue(&q, 60);// 输出当前出队元素printf("出队元素: %d\n", dequeue(&q)); // 输出: 30printf("出队元素: %d\n", dequeue(&q)); // 输出: 40printf("出队元素: %d\n", dequeue(&q)); // 输出: 50printf("出队元素: %d\n", dequeue(&q)); // 输出: 60// 尝试出队时队列为空printf("出队元素: %d\n", dequeue(&q)); // 输出: 队列为空，无法出队！return 0;
}
