第一部分：C语言队列的基础知识
队列是一种先进先出的线性数据结构，就像在超市排队结账一样，先来的人先完成结账离开，在队列中，元素从队尾加入，从队头移除。
队列的核心操作
- 初始化: 创建一个空队列。
- 入队: 在队尾添加一个新元素。
- 出队: 从队头移除一个元素。
- 判空: 检查队列是否为空。
- 判满: 检查队列是否已满（对于固定大小的数组实现）。
- 获取队头元素: 查看队头元素,但不移除它。
队列的两种主要实现方式
在 C 语言中，我们通常不使用内置的“队列”类型，而是通过其他数据结构来模拟它,最常见的方式有两种：
基于数组的静态实现（循环队列）
这是最经典、最高效的实现方式，可以避免数组元素被“出队”后造成的空间浪费。
- 数据结构：一个数组、一个指向队头的指针（
front）、一个指向队尾的指针（rear）。 - 循环技巧：利用取模运算 来实现指针的循环移动，当指针到达数组末尾时,下一个位置就回到数组开头。
- 判空条件：
front == rear - 判满条件：
(rear + 1) % MAXSIZE == front，这里会牺牲一个存储单元来区分“满”和“空”的状态。
基于链表的动态实现
这种方式更加灵活，队列的大小可以动态增长,不受预先定义大小的限制。
- 数据结构：一个链表，需要两个指针：
front（指向第一个节点，即队头）和rear（指向最后一个节点，即队尾）。 - 节点结构：每个节点包含数据域和指向下一个节点的指针。
- 优点：内存利用率高,没有容量限制。
- 缺点：相比数组实现，每个节点都需要额外的空间来存储指针,且存在一定的指针操作开销。
第二部分：基于数组的循环队列实现
下面我们来实现一个通用的循环队列,并解释其关键代码。
定义队列结构体
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 使用 bool 类型
#define MAXSIZE 100 // 队列的最大容量
// 定义队列结构体
typedef struct {
int data[MAXSIZE]; // 存储队列元素的数组
int front; // 队头指针
int rear; // 队尾指针
} SqQueue;
核心函数实现
// 1. 初始化队列
void InitQueue(SqQueue *Q) {
Q->front = 0;
Q->rear = 0;
}
// 2. 判断队列是否为空
bool IsEmpty(SqQueue *Q) {
return Q->front == Q->rear;
}
// 3. 判断队列是否已满
bool IsFull(SqQueue *Q) {
return (Q->rear + 1) % MAXSIZE == Q->front;
}
// 4. 入队
bool EnQueue(SqQueue *Q, int element) {
if (IsFull(Q)) {
printf("Error: Queue is full. Cannot enqueue %d.\n", element);
return false; // 入队失败
}
Q->data[Q->rear] = element; // 将元素放入队尾
Q->rear = (Q->rear + 1) % MAXSIZE; // 队尾指针后移（循环）
return true; // 入队成功
}
// 5. 出队
bool DeQueue(SqQueue *Q, int *element) {
if (IsEmpty(Q)) {
printf("Error: Queue is empty. Cannot dequeue.\n");
return false; // 出队失败
}
*element = Q->data[Q->front]; // 获取队头元素
Q->front = (Q->front + 1) % MAXSIZE; // 队头指针后移（循环）
return true; // 出队成功
}
// 6. 获取队头元素（不删除）
bool GetHead(SqQueue *Q, int *element) {
if (IsEmpty(Q)) {
printf("Error: Queue is empty. Cannot get head.\n");
return false;
}
*element = Q->data[Q->front];
return true;
}
测试代码
// 打印队列内容（辅助函数）
void PrintQueue(SqQueue *Q) {
if (IsEmpty(Q)) {
printf("Queue is empty.\n");
return;
}
printf("Queue: ");
int i = Q->front;
while (i != Q->rear) {
printf("%d ", Q->data[i]);
i = (i + 1) % MAXSIZE;
}
printf("\n");
}
int main() {
SqQueue myQueue;
InitQueue(&myQueue);
EnQueue(&myQueue, 10);
EnQueue(&myQueue, 20);
EnQueue(&myQueue, 30);
PrintQueue(&myQueue); // 输出: 10 20 30
int head_val;
if (GetHead(&myQueue, &head_val)) {
printf("Head element is: %d\n", head_val); // 输出: 10
}
int dequeued_val;
DeQueue(&myQueue, &dequeued_val);
printf("Dequeued element: %d\n", dequeued_val); // 输出: 10
PrintQueue(&myQueue); // 输出: 20 30
EnQueue(&myQueue, 40);
EnQueue(&myQueue, 50);
PrintQueue(&myQueue); // 输出: 20 30 40 50
// 测试循环
// 假设 MAXSIZE=6, 当前队列有 4 个元素 (20,30,40,50)
// front=1, rear=5. (rear+1)%6 = 0, 不等于 front, 所以未满
EnQueue(&myQueue, 60); // 60 应该放在 data[5]
PrintQueue(&myQueue); // 输出: 20 30 40 50 60
// rear=(5+1)%6=0. front=1.
// (rear+1)%6 = (0+1)%6 = 1. 等于 front. 队列已满
EnQueue(&myQueue, 70); // 应该报错
PrintQueue(&myQueue); // 输出: 20 30 40 50 60
DeQueue(&myQueue, &dequeued_val); // 出队 20
// front=(1+1)%6=2. rear=0.
// (rear+1)%6 = (0+1)%6 = 1. 不等于 front. 队列未满
EnQueue(&myQueue, 70); // 70 应该可以入队，放在 data[0]
PrintQueue(&myQueue); // 输出: 30 40 50 60 70
return 0;
}
第三部分：经典题目示例 - PAT 乙级 1003
链接：PAT 乙级 1003 要求
“我是不会在代码中写注释的。” —— 某位不愿透露姓名的神秘大神 本题要求你实现一个简单的代码格式化工具，将给定的代码中的连续三个连续的 替换成一个 。
输入格式： 输入为多行代码，直到文件末尾（EOF）为止。
输出格式： 将输入中的连续三个 替换成一个 ,并输出处理后的代码。
输入样例 1：
i//like//programming输出样例 1：
i/**/like//programming输入样例 2：
i////like//programming输出样例 2：
i/**/like/**/programming解题思路
这个问题的关键在于“连续三个”，我们不能简单地一次替换一个 ,因为那样会破坏后续的匹配。
对于 i////like：
- 如果我们找到第一组 （在
i/和 之间），替换成 ，得到i/**/like，这样第二组 就被破坏了。 - 我们需要找到三个连续的 ，然后将它们中间的两个 变成 。
使用队列的思路： 我们可以逐个字符读取输入,并同时维护一个队列来存放最近的字符。
- 初始化一个队列。
- 循环读取每个字符
c。 - 将
c入队。 - 检查队列中是否有连续的三个 。
- 一个简单的方法是检查队列的最后三个元素（队尾、队尾前一个、队尾前两个）是否都是 。
- 在循环队列中，可以通过
(rear - 1 + MAXSIZE) % MAXSIZE和(rear - 2 + MAXSIZE) % MAXSIZE来获取倒数第二个和倒数第三个元素。
- 如果满足条件：
- 说明找到了 。
- 我们需要出队两次，移除中间的两个 。
- 将 入队两次，形成 。
- 这样， 就被替换成了 。
- 如果不满足条件：
继续读取下一个字符。
- 当所有字符都读取完毕后,将队列中剩余的所有元素依次出队并输出即可。
C语言代码实现（使用我们上面定义的队列）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 1000000 // 假设输入的代码行数和长度不会超过这个值
// --- 循环队列的实现 (与上文相同) ---
typedef struct {
char data[MAXSIZE];
int front;
int rear;
} SqQueue;
void InitQueue(SqQueue *Q) {
Q->front = 0;
Q->rear = 0;
}
bool IsEmpty(SqQueue *Q) {
return Q->front == Q->rear;
}
bool IsFull(SqQueue *Q) {
return (Q->rear + 1) % MAXSIZE == Q->front;
}
bool EnQueue(SqQueue *Q, char element) {
if (IsFull(Q)) {
// 在实际比赛中，如果输入规模大，这里可能会溢出，但PAT题目通常保证输入合法
return false;
}
Q->data[Q->rear] = element;
Q->rear = (Q->rear + 1) % MAXSIZE;
return true;
}
bool DeQueue(SqQueue *Q, char *element) {
if (IsEmpty(Q)) {
return false;
}
*element = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return true;
}
// --- PAT 1003 问题的主逻辑 ---
int main() {
SqQueue Q;
InitQueue(&Q);
char c;
// 使用 getchar() 逐个字符读取，直到遇到 EOF
while ((c = getchar()) != EOF) {
EnQueue(&Q, c);
// 检查队列末尾的三个字符是否都是 '/'
// 循环队列中，获取倒数第1, 2, 3个元素
char first, second, third;
if (Q.rear >= 3) {
first = Q.data[Q.rear - 1];
second = Q.data[Q.rear - 2];
third = Q.data[Q.rear - 3];
} else {
// 处理循环情况，例如队列中只有2个元素，rear=2
// 我们想检查 data[1], data[0], data[MAXSIZE-1]
first = Q.data[(Q.rear - 1 + MAXSIZE) % MAXSIZE];
second = Q.data[(Q.rear - 2 + MAXSIZE) % MAXSIZE];
third = Q.data[(Q.rear - 3 + MAXSIZE) % MAXSIZE];
}
// 如果找到连续的三个 '/'
if (first == '/' && second == '/' && third == '/') {
// 出队两次，移除中间的两个 '/'
DeQueue(&Q, &c); // 移除第一个'/'
DeQueue(&Q, &c); // 移除第二个'/'
// 入队 '*' 两次，形成 '*/'
EnQueue(&Q, '*');
EnQueue(&Q, '/');
}
}
// 输出队列中所有剩余的字符
char output_char;
while (!IsEmpty(&Q)) {
DeQueue(&Q, &output_char);
putchar(output_char);
}
return 0;
}
代码讲解
- 队列定义：我们定义了一个存储
char类型的循环队列SqQueue。 - 逐字符读取：
while ((c = getchar()) != EOF)是处理多行文本输入的标准方法，它会一直读取字符,直到输入流结束。 - 入队：每读取一个字符,就立即入队。
- 核心判断逻辑：
- 在每次入队后,我们检查队列的最后三个字符。
- 由于队列是循环的，获取倒数第
n个元素需要使用(rear - n + MAXSIZE) % MAXSIZE的公式来处理指针越界问题。 - 如果这三个字符都是 ，就说明我们找到了目标模式 。
- 替换操作：
DeQueue(&Q, &c);执行两次，相当于把 （从队尾数的第二个和第三个）移除。EnQueue(&Q, '*');和EnQueue(&Q, '/');执行两次，将 加入队列，完成了 -> 的转换。
- 最终输出：当所有输入处理完毕后，队列中存放的就是格式化后的完整代码,我们只需将队列中的所有元素依次出队并打印即可。
这个例子很好地展示了队列在处理流式数据和需要“记忆”最近几个元素的场景下的强大作用。
