c++中如何用vector实现队列_c++用vector模拟队列实现-C++-PHP中文网

c++中如何用vector实现队列_c++用vector模拟队列实现

穿越時空

发布： 2025-10-03 17:30:02

原创

946人浏览过

用vector模拟队列可通过尾部入队、头部出队实现，但erase(begin())导致O(n)时间复杂度；2. 优化方案使用frontIndex记录队首位置，出队仅移动索引，避免数据搬移，性能接近O(1)；3. 实际开发推荐std::queue，因基于deque更高效。

c++中如何用vector实现队列_c++用vector模拟队列实现

在C++中，vector 本身不是为队列操作设计的，但它可以通过一些方式模拟 queue（先进先出，FIFO）的行为。虽然标准库中的 std::queue 更适合此用途，但在某些场景下（如学习数据结构或受限环境），使用 vector 模拟队列是有意义的。

基本思路：用vector模拟队列

队列有两个核心操作：入队（push） 和 出队（pop）。分别对应在尾部添加元素，在头部移除元素。而 std::vector 支持在尾部高效地插入和删除，但头部删除效率较低（需要整体前移）。尽管如此，仍可通过以下方式实现：

方法一：尾部入队，头部出队（简单但低效）

入队：使用 push_back() 在末尾添加元素
出队：删除第一个元素，可用 erase(begin())

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;
<p>class QueueWithVector {
private:
vector<int> data;</p><p>public:
void enqueue(int value) {
data.push_back(value);
}</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">bool dequeue() {
    if (data.empty()) return false;
    data.erase(data.begin()); // 效率低，O(n)
    return true;
}

int front() {
    if (data.empty()) throw runtime_error("Queue is empty");
    return data[0];
}

bool empty() {
    return data.empty();
}

登录后复制

};

⚠️ 缺点：每次 erase(begin()) 都要移动所有后续元素，时间复杂度为 O(n)，不推荐频繁出队时使用。

优化方案：使用头索引避免移动元素

为了提升性能，可以不真正删除头部元素，而是用一个变量记录当前队首位置，实现“伪出队”。

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

改进版：双指针 + 标记头位置

保留 vector 存储所有元素
用 frontIndex 记录当前有效队首位置
出队时只移动索引，不删除元素
可选：当 frontIndex 过大时，整体前移并重置索引

示例代码：

立即学习“C++免费学习笔记（深入）”；

class EfficientQueue {
private:
    vector<int> data;
    int frontIndex;
<p>public:
EfficientQueue() : frontIndex(0) {}</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">void enqueue(int value) {
    data.push_back(value);
}

bool dequeue() {
    if (empty()) return false;
    frontIndex++;
    // 可在此加入优化：当 frontIndex 占据一半以上时，清理前面空间
    if (frontIndex * 2 > data.size()) {
        data.erase(data.begin(), data.begin() + frontIndex);
        frontIndex = 0;
    }
    return true;
}

int getFront() {
    if (empty()) throw runtime_error("Queue is empty");
    return data[frontIndex];
}

bool empty() {
    return frontIndex >= data.size();
}

登录后复制

};

✅ 优点：出队接近 O(1)，避免频繁移动数据。