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

阅读本书更多章节>>>>

快乐的流畅：个人主页

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

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

---

文章目录

一、容器适配器二、stack2.1 push2.2 pop2.3 top2.4 size2.5 empty 三、queue3.1 push3.2 pop3.3 front3.4 back3.5 size3.6 empty 四、deque4.1 deque的介绍4.2 deque的底层结构4.3 deque的优势与缺陷4.4 为什么选择deque作为stack和queue的底层默认容器 总结

一、容器适配器

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

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

二、stack

细节：

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

template<class T, class Container = vector<T>>class stack{public:private:Container _con;};

2.1 push

压栈

void push(const T& x){_con.push_back(x);}

2.2 pop

出栈

void pop(){_con.pop_back();}

2.3 top

获取栈顶元素

const T& top() const{return _con.back();}

2.4 size

获取栈的有效元素个数

size_t size() const{return _con.size();}

2.5 empty

判断栈是否为空

bool empty() const{return _con.empty();}

三、queue

细节：

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

template<class T, class Container = list<T>>class queue{public:private:Container _con;};

3.1 push

入队

void push(const T& x){_con.push_back(x);}

3.2 pop

出队

void pop(){_con.pop_front();}

3.3 front

获取队头元素

const T& front() const{return _con.front();}

3.4 back

获取队尾元素

const T& back() const{return _con.back();}

3.5 size

获取队列的有效元素个数

size_t size() const{return _con.size();}

3.6 empty

判断队列是否为空

bool empty() const{return _con.empty();}

四、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的底层默认容器

原因有两点：

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

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

总结

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

真诚点赞，手有余香
阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-24/148155.html，文章来源：网络cs，作者：亙句，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！