C++最优算法实现:假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。

发布时间:2024年01月12日

题目:
假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。

解决方式:
循环队列是一种利用固定大小的数组来模拟队列操作的数据结构,它可以在不进行数据移动的情况下实现队列的循环使用。在循环队列中,队头和队尾是连续的位置,当指针移至数组末尾时会循环到数组开头。以下是循环队列的队空条件和队满条件的定义,以及插入和删除元素的操作。

队空条件:当队头指针(假设为front)和队尾指针(假设为rear)相等时,队列为空。 队满条件:当队头指针和队尾指针之差(取模运算)等于队列长度(假设为length)减一时,队列已满。

插入元素(enqueue)的操作:

1.如果队满,则拒绝插入。
2.否则,将队尾指针(rear)后移(取模运算以实现循环)。
3.将新元素存储在队尾指针指向的位置。
4.如果队头指针等于队尾指针,说明队列在插入前为空,需要将队头指针也后移。
5.增加队列长度(length)。

删除元素(dequeue)的操作:

1.如果队空,则拒绝删除。
2.否则,将队头指针(front)后移(取模运算以实现循环)。
3.减少队列长度(length)。

以下是具体的代码实现:

#include <iostream>
#define MAX_SIZE 100 // 定义队列的最大容量

typedef struct {
    int Q[MAX_SIZE];
    int front; // 队头指针
    int rear;  // 队尾指针
    int length; // 队列长度
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue &queue) {
    queue.front = queue.rear = queue.length = 0;
}

// 判断队列是否为空
bool isEmpty(CircularQueue queue) {
    return queue.front == queue.rear;
}

// 判断队列是否已满
bool isFull(CircularQueue queue) {
    return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE == 1;
}

// 插入元素
bool enqueue(CircularQueue &queue, int value) {
    if (isFull(queue)) {
        std::cout << "Queue is full, cannot enqueue." << std::endl;
        return false;
    }
    queue.Q[queue.rear] = value;
    queue.rear = (queue.rear + 1) % MAX_SIZE;
    queue.length++;
    if (queue.front == queue.rear) {
        queue.front++;
    }
    return true;
}

// 删除元素
bool dequeue(CircularQueue &queue, int &value) {
    if (isEmpty(queue)) {
        std::cout << "Queue is empty, cannot dequeue." << std::endl;
        return false;
    }
    value = queue.Q[queue.front];
    queue.front = (queue.front + 1) % MAX_SIZE;
    queue.length--;
    return true;
}

int main() {
    CircularQueue queue;
    initQueue(queue);

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);

    int value;
    if (dequeue(queue, value)) {
        std::cout << "Dequeued value: " << value << std::endl;
    }

    return 0;
}

在这个实现中,我们使用了取模运算来处理队列的循环。当队列不为空时,front指针指向队列的第一个元素,rear指针指向队列的最后一个元素的下一个位置。每次插入操作都会增加length,而每次删除操作都会减少length。队空和队满的条件检查是为了避免在队列已满时尝试插入元素,或在队空时尝试删除元素。

文章来源:https://blog.csdn.net/qq_35320456/article/details/135560481
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。