当前位置：首页 > news >正文

【C++】stack和queue的模拟实现

news 2025/7/27 15:27:59

一、stack和queue的模拟实现

1.1 容器适配器

在C++标准库（STL）中，容器适配器（Container Adaptors）是一种特殊的容器，它们基于现有的STL容器（如vector、deque、list等）进行封装，提供了一种受限的、特定用途的接口。容器适配器本身并不直接管理内存或存储元素，而是依赖底层容器来实现功能，并通过限制或扩展接口来满足特定的数据结构需求。

容器适配器的核心特点：

基于现有容器：适配器（如stack、queue、priority_queue）通过组合一个底层容器（如deque、vector）来实现功能。
接口受限：仅暴露特定操作（如stack只允许一端操作（后进先出），queue是先进先出）。
不提供迭代器：无法直接遍历适配器中的元素（例如不能对stack用for(auto it : s)）。
复用底层容器的实现：内存管理、元素存储等均由底层容器处理。

1.2 stack的模拟实现

stack容器的基本使用方法是push(尾插)、pop(尾删)、size()、empty()、top()。所以它的底层容器都必须能够使用这些方法，其中vector就是符合的，但STL库中使用了deque，这个容器也能完全符合特点，我们稍后作为了解。
在这里插入图片描述
模拟实现代码：

namespace ST
{template<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T& top(){return _con.back();}const T& top() const{return _con.back();}private:Container _con;};
}

由于stack所有的接口里面的功能实现都是使用底层容器的，所以直接调用底层容器的成员函数就好了。

测试：

void test1()
{ST::stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (st.size()){cout << st.top() << " ";st.pop();}
}

在这里插入图片描述

1.3 queue的模拟实现

queue的基本使用方法是push(尾插)、pop(头删)、front()、back()、size()、empty()。其中它所需求的这些功能list是具备的，但STL库中依旧使用了deque。
在这里插入图片描述

模拟实现：

namespace QUE
{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.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}private:Container _con;};
}

测试：

void test2()
{QUE::queue<int> q;q.push(1);q.push(2);q.pop();cout << q.front() << " ";q.push(3);q.push(4);q.push(5);while (q.size()){cout << q.front() << " ";q.pop();}
}

在这里插入图片描述

1.4 deque的了解认识

deque（双端队列，全称double-ended queue）是C++标准模板库(STL)中的一个重要容器，它结合了vector和list的优点，提供了高效的双端插入和删除操作。
在这里插入图片描述
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，重担落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
在这里插入图片描述

指针成员	作用	示意图对应位置
`cur`	指向当前迭代器访问的具体元素（当前块的某个位置）	图中`0/1/2`等元素的直接指针
`first`	指向当前所属内存块的起始地址（块的首元素）	图中每块的第一个元素地址
`last`	指向当前所属内存块的结束地址（块的尾后位置）	图中每块的最后一个元素的下一位
`node`	指向中央映射表`（map）`中当前块的控制节点（保存该块的指针）	图中`map`数组的某个槽位

协作关系：
1、定位元素：

通过node找到当前块在中央映射表中的指针，再结合first/last确定块的范围。
cur在[first, last)范围内移动，访问具体元素。

2、跨块跳转：

当cur移动到last时（如++iter到块末尾），迭代器会：
通过node找到下一个块的指针
更新first/last为新块的边界
将cur指向新块的起始位置（first）

3、反向移动：

当cur移动到first之前时（如--iter到块开头），迭代器会：
通过node找到上一个块的指针
更新first/last
将cur指向上一块的末尾（last - 1）

1.5 deque的优缺点

与vector比较，deque的优势：头删时不需要搬移元素，在扩容时也不需要搬移大量元素，效率比vector高。
与list比较，deque的优势：其底层是连续空间，空间利用率比较高，不需要存储额外字段。

deque的致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，在STL用其作为stack和queue的底层容器。

1.6 为什么选择`deque`作为`stack和queue`的底层默认容器

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作；在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。可以说stack和queue完美利用了deque的优点，并且完美避开了它的缺陷。