目录😋
任务描述
本关任务：编写一个程序实现环形队列的基本运算。
相关知识
为了完成本关任务，你需要掌握：
- 初始化队列
- 销毁队列
- 判断队列是否为空
- 进队列
- 出队列
1. 初始化队列
- 概念：在使用队列之前，需要先为队列分配内存空间并进行初始化设置，这包括确定队列的数据结构、存储方式以及相关指针（如果是链式队列）或索引（如果是顺序队列）的初始状态。
- 示例（顺序队列）：假设用数组
queueArray实现一个简单的顺序队列，并且有两个指针front和rear分别指向队头和队尾。初始化时，设置front = rear = -1，表示队列为空。
int queueArray[MAX_SIZE]; int front = -1; int rear = -1;
- 示例（链式队列）：对于链式队列，需要定义一个节点结构体，包含数据域和指针域。初始化时，创建一个空的头节点（带头节点的链式队列），头节点的指针域初始化为
NULL，队头和队尾指针都指向头节点。
// 链式队列节点结构体 typedef struct QueueNode { int data; struct QueueNode* next; } QueueNode; // 初始化链式队列 QueueNode* front = NULL; QueueNode* rear = NULL; QueueNode* createQueue() { QueueNode* head = (QueueNode*)malloc(sizeof(QueueNode)); head->next = NULL; front = rear = head; return head; }
2. 销毁队列
- 概念：当队列不再使用时，需要释放队列占用的内存空间。对于顺序队列，主要是释放数组空间；对于链式队列，则需要逐个释放节点的内存。
- 示例（顺序队列）：
// 释放顺序队列的数组空间 void destroyQueue() { // 这里没有动态分配内存，数组空间在程序结束时自动释放 // 如果是动态分配的数组，使用free函数释放 // free(queueArray); }
- 示例（链式队列）：
// 释放链式队列的所有节点 void destroyQueue() { QueueNode* current = front; QueueNode* next; while (current!= NULL) { next = current->next; free(current); current = next; } front = rear = NULL; }
3. 判断队列是否为空
- 概念：通过检查队列的状态来确定队列中是否有元素。对于顺序队列，通常根据队头和队尾指针的位置判断；对于链式队列，检查队头指针是否指向头节点（带头节点的情况）或
NULL（不带头节点的情况）。- 示例（顺序队列）：
// 判断顺序队列是否为空 bool isEmpty() { return (front == -1 && rear == -1); }
- 示例（链式队列）：
// 判断链式队列是否为空 bool isEmpty() { return (front == rear); }
4. 进队列（入队）
- 概念：将元素添加到队列的尾部。对于顺序队列，需要先检查队列是否已满，然后将元素放入队尾，更新队尾指针；对于链式队列，创建新节点，将元素存入新节点，然后将新节点插入到队尾，更新队尾指针。
- 示例（顺序队列）：
// 顺序队列入队操作 bool enqueue(int value) { if (rear == MAX_SIZE - 1) { // 队列已满 return false; } if (front == -1) { // 队列为空，初始化队头 front = 0; } rear++; queueArray[rear] = value; return true; }
- 示例（链式队列）：
// 链式队列入队操作 bool enqueue(int value) { QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { return false; } newNode->data = value; newNode->next = NULL; if (front == rear && front == NULL) { // 队列为空 front = rear = newNode; } else { rear->next = newNode; rear = newNode; } return true; }
5. 出队列（离队）
- 概念：从队列的头部移除元素。对于顺序队列，需要先检查队列是否为空，然后取出队头元素，更新队头指针；对于链式队列，取出队头节点的数据，释放队头节点，更新队头指针。
- 示例（顺序队列）：
// 顺序队列出队操作 int dequeue() { if (isEmpty()) { // 队列为空，返回错误值（这里返回 -1） return -1; } int value = queueArray[front]; if (front == rear) { // 队列中只有一个元素，出队后队列为空 front = rear = -1; } else { front++; } return value; }
- 示例（链式队列）：
// 链式队列出队操作 int dequeue() { if (isEmpty()) { // 队列为空，返回错误值（这里返回 -1） return -1; } QueueNode* temp = front; int value = front->data; front = front->next; if (front == NULL) { rear = NULL; } free(temp); return value; }
测试说明
平台会对你编写的代码进行测试：
测试输入：
abc def
预期输出：
(1)初始化队列q (2)依次进队列元素:a b c (3)队列为非空 (4)出队一个元素a (5)依次进队列元素:d e f (6)出队列序列:b c d e f (7)释放队列
测试输入：
xyz opq2*
预期输出：
(1)初始化队列q (2)依次进队列元素:x y z (3)队列为非空 (4)出队一个元素x (5)依次进队列元素:o p q 2 * (6)出队列序列:y z o p q 2 * (7)释放队列
开始你的任务吧，祝你成功！
通关代码
// 请在Begin-End之间添加你的代码， //实现环形队列的如下基本运算// //(1)初始化队列q// //(2)判断队列q是否非空，输出判断结果// //(3)依次进队列元素，注：进队列元素由用户输入// //(4)出队一个元素，输出该元素// //(5)依次进队列元素，注：进队列元素由用户输入// //(6)输出出队序列// //(7)释放队列// /********** Begin *********/ using namespace std; class CircularQueue{ private: vector<char>buffer; int head; int tail; int size; public: CircularQueue(int capacity) :buffer(capacity),head(-1),tail(-1),size(capacity){} bool isEmpty() {return head == -1;} bool isFull() {return (tail + 1) % size == head;} void enqueue(char item){ if(isFull()){ cout<<"(3)列队为满"<<endl; return; } if(isEmpty()){ head = 0; } tail = (tail + 1) % size; buffer[tail] = item; } char dequeue(){ if (isEmpty()){ cout <<"(3)列队为空"<<endl; return '\0'; } char item = buffer[head]; if(head == tail){ head = tail = -1; }else{ head = (head + 1) % size; } return item; } void displayQueue(){ if(isEmpty()){ cout <<"(3)列队为空"<<endl; return; } int i = head; while (true){ cout << buffer[i] << " "; if(i == tail) break; i = (i + 1)% size; } } void destroy(){ buffer.clear(); head = tail = -1; } }; int main(){ string input1,input2; getline(cin,input1); getline(cin,input2); CircularQueue q(10); cout <<"(1)初始化队列q"<<endl; for(char c : input1){ q.enqueue(c); } cout <<"(2)依次进队列元素:"; q.displayQueue(); cout <<endl; if(!q.isEmpty()){ cout << "(3)队列为非空"<<endl; cout << "(4)出队一个元素"<<q.dequeue()<<endl; }else{ cout<<"(3)队列为空"<<endl; return 0; } for(char c : input2){ q.enqueue(c); } cout <<"(5)依次进队列元素:"; for(char c : input2){ cout << c <<" "; } cout <<endl; cout <<"(6)出队列序列:"; while(!q.isEmpty()){ cout <<q.dequeue()<<" "; } cout << endl; cout <<"(7)释放队列"; q.destroy(); return 0; } /********** End **********/
测试结果
