C++ 用数组模拟队列

在C++中,使用数组模拟队列通常涉及到两个主要的操作:入队(enqueue)和出队(dequeue)。由于数组是一个固定大小的数据结构,当使用数组模拟队列时,需要手动管理队列的头部和尾部位置。以下是使用数组模拟队列的一种简单实现方法:

#include <iostream>
#include <vector>

class ArrayQueue {
private:
    std::vector<int> data; // 使用vector来动态管理数组的大小
    int front; // 队列头部的索引
    int rear;  // 队列尾部的索引
    int count; // 队列中元素的数量

public:
    ArrayQueue() : front(0), rear(-1), count(0) {}

    // 入队操作
    bool enqueue(int value) {
        if (count == data.size()) {
            // 如果队列满了,需要扩容
            if (data.size() == 0 || rear == 0) {
                data.resize(data.size() * 2);
            } else {
                // 将队列元素向前移动,重新利用数组空间
                for (int i = front; i != rear + 1; ++i) {
                    data[i - front] = data[i];
                }
                rear -= front;
                front = 0;
            }
        }
        data[++rear] = value;
        ++count;
        return true;
    }

    // 出队操作
    bool dequeue() {
        if (count == 0) {
            std::cout << "Queue is empty" << std::endl;
            return false;
        }
        if (front == rear) {
            // 队列为空,重置front和rear
            front = rear = 0;
        } else {
            ++front;
        }
        --count;
        return true;
    }

    // 查看队首元素
    int frontValue() const {
        if (count == 0) {
            throw std::runtime_error("Queue is empty");
        }
        return data[front];
    }

    // 检查队列是否为空
    bool isEmpty() const {
        return count == 0;
    }

    // 获取队列的大小
    int size() const {
        return count;
    }
};

int main() {
    ArrayQueue queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    std::cout << "Front value: " << queue.frontValue() << std::endl; // 输出队首元素

    queue.dequeue();
    std::cout << "Front value after dequeue: " << queue.frontValue() << std::endl;

    std::cout << "Queue size: " << queue.size() << std::endl; // 输出队列大小

    while (!queue.isEmpty()) {
        std::cout << "Dequeued: " << queue.frontValue() << std::endl;
        queue.dequeue();
    }

    return 0;
}

这个例子中,我们使用了 std::vector 来避免固定大小数组带来的限制,使得队列可以根据需要自动扩容。front 和 rear 分别指向队列的头部和尾部,count 记录队列中的元素数量。

请注意,当数组填满时,我们可以选择扩容数组或者将数组中的元素向前移动,以重新利用数组空间。在这个例子中,我们选择了后者,这样可以避免频繁的内存分配和复制操作。但是,这种方法要求数组的初始位置不为0,或者在移动元素后更新 front 和 rear 的值。

相关推荐

  1. C++ 数组模拟队列

    2024-06-07 09:12:01       29 阅读
  2. 数组简单构成队列C++写法

    2024-06-07 09:12:01       23 阅读
  3. 数组模拟栈和队列

    2024-06-07 09:12:01       24 阅读
  4. 队列——数组来表示

    2024-06-07 09:12:01       32 阅读
  5. 队列实现栈(C

    2024-06-07 09:12:01       32 阅读
  6. C数据结构:队列

    2024-06-07 09:12:01       38 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-07 09:12:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-07 09:12:01       100 阅读
  3. 在Django里面运行非项目文件

    2024-06-07 09:12:01       82 阅读
  4. Python语言-面向对象

    2024-06-07 09:12:01       91 阅读

热门阅读

  1. 2269. 找到一个数字的 K 美丽值

    2024-06-07 09:12:01       26 阅读
  2. 数分—AB测试

    2024-06-07 09:12:01       33 阅读
  3. opencv--3d数据拟合平面并对倾斜平面矫正

    2024-06-07 09:12:01       28 阅读
  4. jmeter基础入门练习题

    2024-06-07 09:12:01       27 阅读
  5. 求最小公倍数

    2024-06-07 09:12:01       33 阅读
  6. 【Flutter 面试题】 JIT 与 AOT分别是什么?

    2024-06-07 09:12:01       33 阅读
  7. 预测预测---通过KIMI来预测上海高考语文题目

    2024-06-07 09:12:01       27 阅读