【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】

Rossy Yan

修改于 2024-12-26 10:34:08

4100

代码可运行

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

运行总次数：0

代码可运行

任务描述

本关任务：编写一个程序实现环形队列的基本运算。

相关知识

为了完成本关任务，你需要掌握：

初始化队列
销毁队列
判断队列是否为空
进队列
出队列

1. 初始化队列

概念：在使用队列之前，需要先为队列分配内存空间并进行初始化设置，这包括确定队列的数据结构、存储方式以及相关指针（如果是链式队列）或索引（如果是顺序队列）的初始状态。

示例（顺序队列）：假设用数组queueArray实现一个简单的顺序队列，并且有两个指针front和rear分别指向队头和队尾。初始化时，设置front = rear = -1，表示队列为空。

#define MAX_SIZE 100
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 *********/
#include <iostream>
#include <string>
#include <vector>

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 **********/