在 C++ 标准库中,std::deque
实现了可以 地在头尾两端插入或删除元素,以及给定下标访问任意元素的线性表。这对于一些用途很方便,但是它的时间常数和占用内存都较大。std::queue
和 std::stack
默认情况下是 std::queue
的包装器,因此也有同样的问题。
在 2023 年校程序设计竞赛中,多位选手编写了含有
std::queue<int> q[1000000];
的代码,这导致他们的程序刚开始运行就超过内存限制而 RE。
std::stack
时,使用 std::stack<T, std::vector<T>>
,而不是简单的 std::stack<T>
(默认为 std::stack<T, std::deque<T>>
:这个默认值毫无道理,但却是 C++ 标准库从古早的 STL 继承的历史包袱)std::deque
或 std::queue
,如果真的需要大量的 (双端) 队列,可以用 std::vector
封装一个循环队列类型