为什么选择deque作为stack和queue的底层默认容器
【摘要】 💦 为什么选择deque作为stack和queue的底层默认容器也就是说 stack 为啥不用 vector 作为默认容器;queue 为啥不用 list 做为默认容器 ❓stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back and pop_back 操作的线性结构,都可以作为 stack 的底层容器,比如 vector and list 都可以;queue 是...
💦 为什么选择deque作为stack和queue的底层默认容器
也就是说 stack 为啥不用 vector 作为默认容器;queue 为啥不用 list 做为默认容器 ❓
stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back and pop_back 操作的线性结构,都可以作为 stack 的底层容器,比如 vector and list 都可以;queue 是先进先出的特殊线性数据结构,只要具有 push_back and pop_front 操作的线性结构,都可以作为 queue 的底层容器,比如 list。但是 STL 中对 stack and queue 默认选择 deque 作为其底层容器,主要是因为:
- stack 和 queue 不需要遍历 (因此 stack and queue没有迭代器),只需要在固定的一端或者两端进行操作。
- 在 stack 中空间增长时,deque 比 vector 的效率高 (扩容时不需要搬移大量数据);queue 中的元素增长时,deque 不仅效率高,而且内存使用率高。
结合了 deque 的优点,而完美的避开了其缺陷。
💦 STL标准库中对于stack和queue的模拟实现
1、stack的模拟实现
#include<vector>
#include<list>
#include<deque>
#include<iostream>
using namespace std;
namespace bit
{
//stack是一个Container适配(封装转换)出来的,且它是一个缺省参数,deque容器,但是它的功能是不变的,所以叫做容器适配器
template<class T, class Container = deque<T>>
class stack
{
//Container的尾认定是栈顶
public:
void push(const T& x)//先进
{
_con.push_back(x);
}
void pop()//后出
{
_con.pop_back();
}
const T& top()
{
//不能用[],因为如果是list就不支持了,back更为通用
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_stack()
{
//stack<int, std::vector<int>> st;
//stack<int, std::list<int>> st;
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while(!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
}
int main()
{
bit::test_stack();
return 0;
}
2、queue的模拟实现
#include<vector>
#include<list>
#include<deque>
#include<iostream>
using namespace std;
namespace bit
{
//stack是一个Container适配(封装转换)出来的,且它是一个缺省参数,deque容器
template<class T, class Container = deque<T>>
class queue
{
//Container的尾认定是队尾,头是队头
public:
void push(const T& x)//先进
{
_con.push_back(x);
}
void pop()//先出
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_queue()
{
//queue<int, std::vector<int>> qu;//err,因为vector不支持头删接口,所以不能适配
//queue<int, std::list<int>> qu;
queue<int> qu;
qu.push(1);
qu.push(2);
qu.push(3);
while(!qu.empty())
{
cout << qu.front() << " ";
qu.pop();
}
cout << endl;
}
}
int main()
{
bit::test_queue();
return 0;
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)