数据结构之队列实验

引言

在计算机科学中，进制转换是基础但重要的操作。例如将一个十进制数转换为二进制或八进制表示时，我们通常使用“短除法”——即不断用目标进制去除当前数，记录余数，直到商为0为止。

这种方法得到的是低位先产生的结果（如十进制 10 转二进制是 1010，计算顺序是 0 -> 1 -> 0 -> 1），而我们希望输出的结果是高位在前、低位在后（即 1010）。

这就需要一种数据结构来保存这些余数，并支持先进先出（FIFO）的操作方式。于是，队列就自然而然地成为了我们的选择。

同时，为了高效利用空间，我们采用循环队列结构，其基本结构图如下图所示。

---

一、需求分析

1.1 功能要求

1. 输入一个非负整数
2. 输出其对应的二进制和八进制表示
3. 使用循环队列作为中间存储结构
4. 程序具有良好的健壮性（如输入非法值提示）

1.2 技术目标

1. 掌握循环队列的基本操作（初始化、入队、出队、判断空满）
2. 学会用队列辅助完成进制转换
3. 理解队列与栈在数据处理中的不同应用场景

---

二、实验思路

我们从几个问题开始，来逐步构建和完善实现【进制转换】的实验思路。

问题一：如何进行进制转换？

使用“短除法”，每次取余数并压入队列中。由于余数是从低位到高位依次产生，所以最终打印时要逆序输出。

示例：十进制 10 转二进制

10 ÷ 2 = 5 余 0 → Enqueue(0)
5  ÷ 2 = 2 余 1 → Enqueue(1)
2  ÷ 2 = 1 余 0 → Enqueue(0)
1  ÷ 2 = 0 余 1 → Enqueue(1)

此时队列内容为：[0, 1, 0, 1]
我们需要逆序输出：1010

问题二：为什么要用循环队列？

普通数组模拟的队列存在“假溢出”问题，即当 rear 到达数组末尾时，即使前面有空位也无法继续入队。

循环队列通过模运算让指针“绕回来”，从而充分利用空间。

预留一个位置用于区分队列空和满的情况（避免 front == rear 无法判断状态的问题）。

此时可能会存在疑问：为什么要用队列？不用数组或栈？

因为我们采用的是“短除法”，每次得到的是低位数字（如余数），而最终输出需要高位在前、低位在后。队列正好支持先进先出（FIFO）的操作方式，适合这种按顺序入队、按顺序出队后再逆序输出的需求。如果用栈的话，虽然也能做到逆序输出，但逻辑上不如队列直观，也不符合“先进先出”的语义。

问题三：如何组织程序结构？

我们将整个程序划分为以下几个模块：

1. 队列结构定义与基本操作函数
2. 进制转换核心逻辑函数
3. 主函数负责用户交互与调用转换函数

---

三、代码编写

接下来，我们开始按照前面的基本思路，逐步编写各个函数以及完整的程序。

3.1 队列结构体定义与初始化

3.1.1 队列结构体定义

这是一个典型的 ADT（抽象数据类型）设计方法。我们把队列的行为封装成一个结构体，并配合一组操作函数来控制它的行为。选择 int data[MAX_QUEUE_SIZE] 是为了固定长度的数组实现，简单高效；预留空间是为了方便判断空满状态。

同时我们需要一种方式来保存进制转换过程中产生的每一位数字（余数）。这些数字是低位先产生，高位后产生，因此需要一个先进先出的数据结构来按顺序保存它们。

#define MAX_QUEUE_SIZE 200          // 最大队列长度// 队列结构体定义（循环队列[预留空位用于区分首尾]）
typedef struct 
{int data[MAX_QUEUE_SIZE];int front;  // 队头指针int rear;   // 队尾指针
} Queue;

值得注意的是：

1. 数组大小不能太小，避免溢出（比如非常大的十进制数）
2. 使用循环结构要注意模运算
3. 队列预留了一个位置用于区分空和满的状态

3.1.2 队列的初始化

队列作为一个抽象数据类型（ADT），也应该有初始化函数来确保其处于干净、可用的状态。就像你声明一个数组后，如果要用它存储数据，通常也需要先清空内容或设置初始值一样。

我们要使用的循环队列结构体 Queue，它内部有两个指针变量 front 和 rear，这两个指针分别指向队列的第一个元素位置和下一个可插入的位置。在每次使用队列之前，必须将这两个指针都重置为初始状态（即 0），否则可能会读取到上一次操作残留的数据或出现越界错误。

因此，我们要进行队列的定初始化：

void InitializeQueue(Queue* q) 
{q->front = 0;q->rear = 0;
}

值得注意的是：

1. 指针初始值为 0 表示队列为空。
2. 必须传入一个合法的 Queue* 类型指针。
3. 不要在多个转换之间共用未重新初始化的队列。

3.2 队列基本操作定义

3.2.1 队列状态判断

在进行出入队操作前，必须确认队列是否为空，防止访问非法内存。实现如下：

int IsQueueEmpty(const Queue* q) 
{/* 队首与队尾指向同一处即为空 */return q->front == q->rear;
}

值得注意的是：

1. 判断的是指针是否相等，而不是数组内容；
2. const 表示该函数不会修改队列内容，增强语义安全。

在进行入队操作前，必须判断队列是否已满，防止越界访问，因此还需要有判断队列是否满的操作。而普通队列存在“假溢出”问题，而循环队列虽然解决了这个问题，但判断是否已满变得复杂了。

故这里采用了一种经典的判断方式——预留一个位置，当所处位置的后一个与首指针相同，即 (rear + 1) % MAX == front 时就表示队列满了。实现如下：

int IsQueueFull(const Queue* q) 
{/* 由于循环队列，所以会预留空位。即队尾的后一位与队首相等表示满了 */return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

值得注意的是：

1. 要注意模运算的正确使用；
2. 如果不预留空位，就无法区分“空”和“满”的状态（两者都是 front == rear）。

3.2.2 入队操作

我们要将短除法得到的余数依次压入队列中，等待后续处理。而且这也是队列的核心操作之一，用来向队列尾部添加元素。同时我们希望这个操作能被重复调用，且具备良好的错误处理机制，所以在入队前需要判断队列是否存在或是否已满等状况。代码实现如下：

void Enqueue(Queue* q, int value) 
{/* 入队合法性判断 */if (IsQueueFull(q))     // 队列未满是才可入队{printf("错误：队列已满，无法入队。\n");exit(EXIT_FAILURE);}/* 数据入队后，队尾指针往后移 */q->data[q->rear] = value;q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}

值得注意的是：

1. 入队前必须检查是否已满
2. 插入完成后更新 rear 指针（记得模运算）
3. 错误处理建议退出程序，避免继续运行导致不可预测结果

3.2.3 出队操作

由于我们要从队列头部取出元素，用于输出处理，且这也是队列的另一个核心操作。同时，由于我们采用了循环结构，front 指针移动也要用模运算。代码实现如下：

int Dequeue(Queue* q) 
{/* 出队合法性判断 */if (IsQueueEmpty(q))        // 队列非空才可出队{printf("错误：队列为空。\n");exit(EXIT_FAILURE);}/* 数据出队，对头指针后移 */int value = q->data[q->front];q->front = (q->front + 1) % MAX_QUEUE_SIZE;return value;
}

值得注意的是：

1. 出队前必须检查是否为空
2. 返回值是当前 front 所指的元素
3. 更新 front 指针时记得取模

3.3 进制转换操作

3.3.1 进制转换

这是整个程序的核心算法所在。我们使用短除法来实现这一核心逻辑，短除法是常常用来实现进制转换的一种方法，我们要将输入的十进制数转换为目标进制的各个位数，使用短除法计算余数并按顺序入队就是个不错的方式了。代码实现如下：

void ConvertToBase(int number, int base, Queue* q) 
{/* 转换数字为0时直接入队 */if (number == 0) {Enqueue(q, 0);  // 处理输入为0的情况return;}/* 大于0时，短除法转换为二进制，低至高逐位入队 */while (number > 0) {Enqueue(q, number % base);number /= base;}
}

值得注意的是：

1. 特别处理 number == 0 的情况，否则会跳过循环
2. 循环结束后，队列中是低位先入队
3. 余数是整数，可以直接用 int 类型存储

3.3.2 反转队列输出

因为我们是按低位先入队的方式存储余数，直接打印会变成低位在左，不符合我们读数习惯。而队列只能从前往后读，不能随机访问，于是我们决定先将各个数依次出队存储在临时数组，然后逆序输出，这样就能实现队列反转了。代码实现如下：

void PrintReversedQueue(Queue* q) 
{/* 1. 定义出队的数据暂存数组以及索引 */int temp_buffer[MAX_QUEUE_SIZE];int count = 0;/* 2. 队列非空时持续出队，并将出队数据存储至暂存数组 */while (!IsQueueEmpty(q)) {temp_buffer[count++] = Dequeue(q);}/* 3. 逆序打印出出队的数据 */for (int i = count - 1; i >= 0; --i) {printf("%d", temp_buffer[i]);}
}

值得注意的是：

1. 出队之后队列为空，原始数据不再保留
2. 中间数组不能太大也不能太小，要合理控制
3. 打印时不换行，便于拼接多个输出

3.3.3 整合转换处理逻辑

为了让主函数简洁，同时复用转换逻辑，我们将其封装为一个统一接口函数。那么我们将前面所有函数整合成一个完整的转换流程就好了，即初始化 → 转换 → 输出。这样也便于扩展其他进制转换逻辑。代码实现如下：

void CovProcess(Queue* q, int decNum, int base)
{InitializeQueue(q);                     // 初始化队列ConvertToBase(decNum, base, q);         // 进制转换/* 根据转换的进制数给出不同的提示 */switch (base)       {case 2:{printf("二进制表示为：\t");break;}case 8:{printf("八进制表示为：\t");break;}default:break;}/* 打印转换数据 */PrintReversedQueue(q);                  printf("\n");
}

值得注意的是：

1. 每次转换前都要重新初始化队列，否则残留数据会影响结果
2. 支持扩展更多进制，只需增加 case 即可
3. 打印完换行，保持格式整洁

3.4 主函数整合测试

这里，按照完整的流程逐步调用相关函数即可。代码如下：

int main(void) 
{int decimal_number;Queue conversion_queue;printf("\t=== 十进制转二进制与八进制 ===\n");printf("请输入一个非负整数：");/* 输入数据合法性判断 */if (scanf("%d", &decimal_number) != 1 || decimal_number < 0) {printf("输入无效，请输入一个非负整数。\n");return EXIT_FAILURE;}/* 输出进制转换 */CovProcess(&conversion_queue, decimal_number, 2);       // 二进制转换CovProcess(&conversion_queue, decimal_number, 8);       // 八进制转换return 0;
}

值得注意的是：

1. 输入验证很重要，防止非法输入导致程序崩溃
2. 两次调用 CovProcess 时要确保队列被重新初始化
3. 输出要有提示信息，提高用户体验

---

四、源代码展示

最后，将所有代码整合起来，完整代码如下：

#define   _CRT_SECURE_NO_WARNINGS	-1/**
* 利用循环队列实现进制转换（如2、8）
* 
*/#include <stdio.h>
#include <stdlib.h>#define MAX_QUEUE_SIZE 200          // 最大队列长度// 队列结构体定义（循环队列[预留空位用于区分首尾]）
typedef struct 
{int data[MAX_QUEUE_SIZE];int front;  // 队头指针int rear;   // 队尾指针
} Queue;void InitializeQueue(Queue* q);                         // 队列初始化
int IsQueueEmpty(const Queue* q);                       // 判断队列是否为空
int IsQueueFull(const Queue* q);                        // 判断队列是否已满
void Enqueue(Queue* q, int value);                      // 入队
int Dequeue(Queue* q);                                  // 出队
void ConvertToBase(int number, int base, Queue* q);     // A2B进制转换
void PrintReversedQueue(Queue* q);                      // 逆序输出队列数据
void CovProcess(Queue* q, int decNum, int base);        // 进制转换处理/*** 主函数：用户交互与进制转换*/
int main(void) 
{int decimal_number;Queue conversion_queue;printf("\t=== 十进制转二进制与八进制 ===\n");printf("请输入一个非负整数：");/* 输入数据合法性判断 */if (scanf("%d", &decimal_number) != 1 || decimal_number < 0) {printf("输入无效，请输入一个非负整数。\n");return EXIT_FAILURE;}/* 输出进制转换 */CovProcess(&conversion_queue, decimal_number, 2);       // 二进制转换CovProcess(&conversion_queue, decimal_number, 8);       // 八进制转换return 0;
}/*** 初始化队列** @param q 指向队列的指针*/
void InitializeQueue(Queue* q) 
{q->front = 0;q->rear = 0;
}/*** 判断队列是否为空** @param q 指向队列的指针* @return 如果为空返回 1，否则返回 0*/
int IsQueueEmpty(const Queue* q) 
{/* 队首与队尾指向同一处即为空 */return q->front == q->rear;
}/*** 判断队列是否已满** @param q 指向队列的指针* @return 如果已满返回 1，否则返回 0*/
int IsQueueFull(const Queue* q) 
{/* 由于循环队列，所以会预留空位。即队尾的后一位与队首相等表示满了 */return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}/*** 入队操作** @param q 指向队列的指针* @param value 要入队的值*/
void Enqueue(Queue* q, int value) 
{/* 入队合法性判断 */if (IsQueueFull(q))     // 队列未满是才可入队{printf("错误：队列已满，无法入队。\n");exit(EXIT_FAILURE);}/* 数据入队后，队尾指针往后移 */q->data[q->rear] = value;q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}/*** 出队操作** @param q 指向队列的指针* @return 出队的值*/
int Dequeue(Queue* q) 
{/* 出队合法性判断 */if (IsQueueEmpty(q))        // 队列非空才可出队{printf("错误：队列为空。\n");exit(EXIT_FAILURE);}/* 数据出队，对头指针后移 */int value = q->data[q->front];q->front = (q->front + 1) % MAX_QUEUE_SIZE;return value;
}/*** 十进制转任意进制，并将结果存入队列中** @param number 原始十进制数* @param base 目标进制（如 2、8）* @param q 存储转换结果的队列*/
void ConvertToBase(int number, int base, Queue* q) 
{/* 转换数字为0时直接入队 */if (number == 0) {Enqueue(q, 0);  // 处理输入为0的情况return;}/* 大于0时，短除法转换为二进制，低至高逐位入队 */while (number > 0) {Enqueue(q, number % base);number /= base;}
}/*** 逆序输出队列中的数字*转换后的各个位数据低至高入队，根据队列FIFO特性，需要逆序输出才能呈现低位在右* * @param q 指向包含转换结果的队列*/
void PrintReversedQueue(Queue* q) 
{/* 1. 定义出队的数据暂存数组以及索引 */int temp_buffer[MAX_QUEUE_SIZE];int count = 0;/* 2. 队列非空时持续出队，并将出队数据存储至暂存数组 */while (!IsQueueEmpty(q)) {temp_buffer[count++] = Dequeue(q);}/* 3. 逆序打印出出队的数据 */for (int i = count - 1; i >= 0; --i) {printf("%d", temp_buffer[i]);}
}/*** 进制转换处理（如2、8）** @param q 存储转换结果的队列* @param decNum 需要进行转换的数值* @param base 目标进制（如 2、8）*/
void CovProcess(Queue* q, int decNum, int base)
{InitializeQueue(q);                     // 初始化队列ConvertToBase(decNum, base, q);         // 进制转换/* 根据转换的进制数给出不同的提示 */switch (base)       {case 2:{printf("二进制表示为：\t");break;}case 8:{printf("八进制表示为：\t");break;}default:break;}/* 打印转换数据 */PrintReversedQueue(q);                  printf("\n");
}

---

五、实验总结

本次实验通过使用循环队列实现了十进制数向二进制和八进制的转换，不仅加深了对队列这一数据结构的理解，也锻炼了将理论算法（短除法）与实际数据结构相结合的编程能力。
在实现过程中，我们简单设计了队列的基本操作函数，利用其先进先出的特性保存进制转换过程中产生的余数，并通过逆序输出得到正确结果。

---

以上便是本次文章的所有内容，欢迎各位朋友在评论区讨论，本人也是一名初学小白，愿大家共同努力，一起进步吧！

鉴于笔者能力有限，难免出现一些纰漏和不足，望大家在评论区批评指正，谢谢！