c++ - 有没有比在基于数组的队列实现中向左移动元素更好的算法

Question

我正在尝试提出一种在 C++ 中实现类似于 Java 的阻塞数组队列的设计。我注意到，一旦我将数组的前部始终保持在索引 0 处，那么我必须将元素从索引 1 移到数组中的后部到左侧 [ 代价高昂的操作 ]，以便队列可以再次插入后部。

有没有更好的实现呢？我看到有些人在 youtube 上有视频，其中的实现是在元素出列时不断移动队列的前指针。但是，一旦队列满载，当您从队列中出列时，您将如何让可用空间可用于插入？

如果您对问题仍有任何不清楚的地方，请指出。我试图确定是否有比将元素向左移动更好的方法，这似乎不可避免但效率低下。

标签： c++queue

Answer 1

对于生产代码，最佳方式是使用 std::deque。

如果这是一个供您学习的练习，那么您可以实现一个环形缓冲区。正如您所描述的，您保留两个索引：一个指向队列的第一个元素，一个指向末尾的一个。每当您排队或出队时，您都会移动这些索引之一。缓冲区环绕末端。

当您进入队列并需要额外空间时，您需要重新分配更大的缓冲区。如果您通过将大小加倍来做到这一点，平均而言，您将产生固定成本（这称为摊销线性）。