前言

在C++ STL的众多容器中，stack和queue可以说是最“守规矩”的两个——一个坚持“后进先出”，一个恪守“先进先出”。而我们今天的主角std::deque（双端队列），则是一个在两端都能自由进出的“全能选手”，它既是stack和queue的默认底层容器，本身也是个功能强大的序列容器。

一、容器适配器

在正式介绍deque之前，我们需要先理解一个重要的设计思想——适配器。

适配器是一种经典的设计模式。软件设计里，当我们已经有一个功能完备的类，但它的接口不符合当前需求时，我们并不想修改这个类本身，而是创造一个“转接头”，把原有接口转换成客户端期望的样子。C++ STL借用了这一思想，提出了**容器适配器（Container Adapter）**的概念：它不是从零开始实现数据存储，而是封装一个已有的容器，对外提供一套新的、更受限或更专用的接口。

stack和queue就是容器适配器的典型代表。

为什么需要容器适配器？
  • 语义清晰：声明一个stack，你就立刻明白这里只允许后进先出，不能用下标访问，不能遍历。如果用vector作为底层，谁能保证以后不会有人偷偷调用push_front或者越界访问呢？
  • 复用现有容器：不需要重新实现动态数组或链表的内存管理，直接站在vector、list、deque的肩膀上。
  • 接口转换：底层容器提供了push_back、pop_back、back等方法，适配器只暴露出push、pop、top这几个方法，强迫使用者按栈的规则操作。

因此，stack和queue这类容器适配器都有一个特征：没有迭代器。因为迭代器意味着可以遍历、修改任意位置元素，这破坏了栈和队列规定的受限访问规则。

二、stack：后进先出的“守序者”

stack的典型操作包括：push（压栈）、pop（出栈）、top（返回栈顶元素引用）、size（元素个数）、empty（判空）。

把这些操作映射到底层容器，自然就是：在容器末尾插入、在容器末尾删除、获取最后一个元素、获取大小、判空。也就是说，底层容器只要支持push_back、pop_back、back、size、empty这几个接口，就能充当stack的底层存储。C++标准库中，vector、list、deque都满足这个要求。

模拟实现

下面的stack类模板实现：

#pragma once
#include<iostream>
#include<deque>

namespace ray
{
	template<class T, class container = deque<T>>
	class stack 
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		T& top()
		{
			return *(_con.end()-1);
		}
		const T& top() const
		{
			return *(_con.end() - 1);
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}
	private:
		container _con;
	};
}

这个实现非常简单：将所有操作直接转发给底层容器_con，对外只暴露符合栈语义的接口。其中默认使用deque<T>作为底层容器，当然我们也可以手动指定为vector<T>或list<T>。

三、queue：先进先出的“排队者”

queue的操作与stack略有不同：push（队尾入队）、pop（队首出队）、front（获取队首元素）、back（获取队尾元素）。

类似于stack，queue也需要底层容器支持push_back、pop_front、front、back、size、empty。这些接口deque和list都支持，但vector不支持pop_front，因此不能作为queue的底层容器。

模拟实现
#pragma once
#include<iostream>
#include<deque>

namespace ray
{
	template<class T, class container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}
		T& front()
		{
			return *(_con.begin());
		}
		const T& front() const 
		{
			return *(_con.begin());
		}
		T& back()
		{
			return *(_con.end() - 1);
		}
		const T& back() const
		{
			return *(_con.end() - 1);
		}
	private:
		container _con;
	};
}

四、deque：stack和queue背后的“幕后功臣”

刚刚我们已经看到，stack和queue都默认使用deque<T>作为底层容器。为什么是deque？原因很简单：deque既能从尾部高效操作（push_back/pop_back），也能从头部高效操作（push_front/pop_front），完美满足stack和queue的所有需求，且无论哪一端操作都是O(1)的常数时间复杂度。

4.1 什么是deque？

std::deque全称double-ended queue，叫作双端队列，是C++ STL中序列式容器之一。一句话概括：deque是一种支持头尾常数时间插入删除、支持随机访问、底层分段连续的序列容器，兼具vector和list的部分优势。

4.2 核心特性总览
特性 说明
头尾插入/删除 O(1)，效率极高
随机访问 支持[]、at()访问元素，像数组一样
底层结构 分段连续内存，不是整块连续，也不是双向链表
中间插入/删除 O(n)，效率较低
自动扩容 无需手动管理内存

deque通过**中控数组（map）+ 数据缓冲区（buffer）**的存储模型，实现了分段连续存储。每块缓冲区是固定大小的连续数组，中控数组是一个指针数组，每个元素存放一块缓冲区的起始地址。

4.3 deque常用接口大全

deque提供了丰富的成员函数，下面分类介绍：

构造函数

#include <deque>

deque<int> dq1;              // 创建空的双端队列
deque<int> dq2(5);           // 5个元素，初始化为默认值（int默认为0）
deque<int> dq3(5, 10);       // 5个元素，初始值均为10
deque<int> dq4{1, 2, 3, 4};  // 初始化列表构造
deque<int> dq5(dq4);         // 拷贝构造
deque<int> dq6(dq3.begin(), dq3.end()); // 迭代器区间构造

上述构造方式中，dq2创建了5个位置但内容为默认值（0），dq3批量填充了5个10，dq6则可以用其他容器的迭代器范围来构造。

插入操作（deque最强的一点——“两端都能插，中间也能插”）

dq.push_back(x);    // 尾部插入元素x
dq.push_front(x);   // 头部插入元素x（这是vector没有的）
dq.insert(dq.begin()+2, 99);   // 在指定位置插入
dq.emplace_back(args...);      // 原地构造，比push更高效
dq.emplace_front(args...);     // 原地构造，在头部插入

删除操作

dq.pop_back();      // 尾部删除
dq.pop_front();     // 头部删除
dq.erase(dq.begin()+1);        // 删除指定位置
dq.erase(dq.begin(), dq.begin()+3); // 删除区间[begin, begin+3)
dq.clear();         // 清空所有元素

元素访问

dq.front();    // 获取队首元素引用
dq.back();     // 获取队尾元素引用
dq[0];         // 下标随机访问，不检查越界
dq.at(1);      // 带越界检查访问，越界时抛出out_of_range异常

容量操作

dq.size();      // 返回有效元素个数
dq.empty();     // 判断是否为空
dq.max_size();  // 返回容器能容纳的最大元素个数
dq.resize(10);  // 重新指定大小，新元素默认值填充

遍历方式

// 普通迭代器遍历
for(auto it = dq.begin(); it != dq.end(); ++it) 
    cout << *it << " ";

// 范围for遍历
for(auto x : dq) 
    cout << x << " ";

// 反向迭代器遍历
for(auto it = dq.rbegin(); it != dq.rend(); ++it)
    cout << *it << " ";
4.4 deque vs vector vs list 三大容器对比

了解deque的特性后，我们来看看它与vector、list的区别：

对比维度 vector deque list
底层结构 整块连续数组 中控表 + 分段连续缓冲区 双向循环链表
尾部增删 O(1) O(1) O(1)
头部增删 O(n) 极慢 O(1) 极快 O(1) 极快
随机访问 [] 支持 O(1) 支持 O(1) 不支持
内存连续性 完全连续 分段连续 完全不连续
中间插入/删除 O(n) O(n) O(1)
遍历效率 最高 中等 较低
迭代器失效 极易失效 仅当前块迭代器失效 仅被删除节点迭代器失效
4.5 操作复杂度速查表
操作 时间复杂度 说明
push_front() O(1) 头部插入，摊销常数时间
push_back() O(1) 尾部插入，摊销常数时间
pop_front() O(1) 头部删除
pop_back() O(1) 尾部删除
insert() (中间) O(n) 需要移动元素
erase() (中间) O(n) 需要移动元素
operator[] O(1) 随机访问
at() O(1) 带边界检查的访问

五、使用注意事项

  1. 包含头文件：使用deque前必须包含#include <deque>头文件。
  2. 中间插入删除效率低：deque在头部和尾部的操作效率极高，但在中间位置插入或删除元素需要移动大量数据，时间复杂度为O(n)。
  3. 内存不连续：deque不保证所有元素在连续内存中存储，因此不能依赖于指针算术运算来跨块访问。
  4. 适合场景：deque适合实现双端队列、滑动窗口、任务调度等需要频繁在两端操作的场景。
  5. 迭代器稳定性：deque的迭代器在插入操作后可能失效，特别是插入位置在中间时。

结语

通过本文，我们深入剖析了stack和queue作为容器适配器的设计思想，并手动实现了这两个经典容器。同时也详细介绍了它们背后的“幕后功臣”——deque双端队列的使用方法。deque这个“全能选手”既能像vector一样随机访问，又能像queue一样双端操作，虽然不及list在中间插入的高效，但胜在灵活多变。

希望这篇文章能帮助你彻底掌握stack、queue和deque这些STL中的重要组件。如果觉得有用，欢迎点赞收藏

# c++ # 数据结构
Logo
亚马逊云科技技术品牌专区

更多推荐

2026年人工智能专业学习数据分析的价值

掌握Python数据分析栈（Pandas、NumPy、Scikit-learn）。完成1-2个Kaggle竞赛或开源项目。考取CDA数据分析师证书证书优势（1）提升数据分析能力CDA 认证涵盖了数据分析的各个方面，包括数据采集、处理、分析和可视化等。通过 CDA 认证的学习和考试，可以系统地掌握数据分析的知识和技能，提升自己在数据分析方面的能力。（2）增强就业竞争力在就业市场上，拥有 CDA 认证

avatar 亚马逊云科技技术品牌专区

如果你写云数据库（3）

一些分布式数据库在这个方面就很吃亏，多副本，为了追求高可靠，就自然要把副本放到多个 AZ 中，这样一来，计算流量就很容易在多个 AZ 之间来回蹿，费用蹭蹭涨。所以啊，云原生的数据库，还是 Snowflake 玩得溜，卡了一个非常好的位，把这些乱七八糟的需求全部绕过了，一个 AZ 管够。那么，如果你在设计产品的时候，就需要时时刻刻把网络这件事情放在心上，最好，每一次查询涉及到的机器都不要跨 AZ。甚

avatar 亚马逊云科技技术品牌专区
cover

Google Search Console AI Performance Reports：企业如何追踪 AI Overview 和 AI Mode 可见性

avatar 亚马逊云科技技术品牌专区