🌏博客主页: 主页
🔖系列专栏: C++
❤️感谢大家点赞👍收藏⭐评论✍️
😍期待与大家一起进步!
前言
STL标准库中stack和queue的底层结构 :
虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque
一、deque的一些基本知识
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组
相比vector:
1.极大缓解了扩容问题以及头插头删问题
2.deque的下标访问不够极致,遇上遍历的时候要拉跨很多
3.deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下
相比list:
1.可以支持下标访问
2.cpu高速缓存效率不错
3.和list一样头插头删效率可以,但中间插入删除效率很拉跨
3为什么选择deque作为stack和queue的底层默认容器
stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高文章来源:https://www.toymoban.com/news/detail-616444.html
高频的头插头删,尾插尾删很合适文章来源地址https://www.toymoban.com/news/detail-616444.html
二、stack模拟实现
namespace simulation {
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.back();
}
size_t size() {
return _con.size();
}
bool empty() {
return _con.empty();
}
private:
Container _con;
};
}
三、queue的模拟实现
namespace simulationQ {
template<class T,class Container=deque<T>>
class queue {
public:
void push(const T&x) {
_con.push_back(x);
}
void pop() {
_con.pop_front();
}
T& front() {
return _con.front();
}
T& back() {
return _con.back();
}
size_t size() {
return _con.size();
}
bool empty() {
return _con.empty();
}
private:
Container _con;
};
}
到了这里,关于【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!