【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现

快乐的流畅：个人主页

个人专栏：《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

一、容器适配器

STL并没有将stack和queue划分为容器，而是将其称为容器适配器，原因是stack和queue只是对其他容器的接口进行了封装。

这也让stack和queue模拟实现起来异常简单，所以两个合在一起讲解介绍。

二、stack

细节：

1. stack具有LIFO（后进先出）性质
2. 默认容器使用vector，使用尾插尾删效率高（STL库中使用deque）

template<class T, class Container = vector<T>>
class stack
{
public:
private:
	Container _con;
};
1
2
3
4
5
6
7

2.1 push

压栈

void push(const T& x)
{
	_con.push_back(x);
}
1
2
3
4

2.2 pop

出栈

void pop()
{
	_con.pop_back();
}
1
2
3
4

2.3 top

获取栈顶元素

const T& top() const
{
	return _con.back();
}
1
2
3
4

2.4 size

获取栈的有效元素个数

size_t size() const
{
	return _con.size();
}
1
2
3
4

2.5 empty

判断栈是否为空

bool empty() const
{
	return _con.empty();
}
1
2
3
4

三、queue

细节：

1. queue具有FIFO（先进先出）性质
2. 默认容器使用list，使用尾插头删效率高（STL库中使用deque）

template<class T, class Container = list<T>>
class queue
{
public:
private:
	Container _con;
};
1
2
3
4
5
6
7

3.1 push

入队

void push(const T& x)
{
	_con.push_back(x);
}
1
2
3
4

3.2 pop

出队

void pop()
{
	_con.pop_front();
}
1
2
3
4

3.3 front

获取队头元素

const T& front() const
{
	return _con.front();
}
1
2
3
4

3.4 back

获取队尾元素

const T& back() const
{
	return _con.back();
}
1
2
3
4

3.5 size

获取队列的有效元素个数

size_t size() const
{
	return _con.size();
}
1
2
3
4

3.6 empty

判断队列是否为空

bool empty() const
{
	return _con.empty();
}
1
2
3
4

四、deque

4.1 deque的介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

4.2 deque的底层结构

其实，deque并不是一整块连续空间，而是一段一段连续的小空间结合在一起。deque有一个中控数组，存放一段段小空间的指针，类似动态开辟的二维数组。

一开始在中间开辟空间，随后根据需求向两边进行扩容。

所以，针对分段连续的空间结构，为了支持随机访问，设计出了比较复杂的迭代器。

这样的空间结构，也导致遍历的效率变得十分低下，因为deque的迭代器需要频繁判断是否抵达分段空间的边界

4.3 deque的优势与缺陷

优势：

• 支持随机访问
• 头尾的插入删除，时间复杂度为O(1)

缺陷：

• 中间插入删除比较麻烦
• 不适合遍历

总体来说，deque结合了vector和list的优势，却又没有vector和list的性能那么极致，在大部分场景下都不太常用，所以这里只是简单介绍，并不模拟实现底层结构。

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

原因有两点：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长
   时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

总结

这次学习了容器适配器——stack和queue，了解到用容器作为模板的美妙与神奇，极大简化构建容器的代码量。同时简单了解deque的结构和使用场景，进一步理解STL容器的设计。

真诚点赞，手有余香