1、stack和queue常用接口
严格来说栈和队列的实现是容器适配器
1、常用接口:
栈:top、push、pop、size、emptystack - C++ Reference (cplusplus.com)
队列:top、push、pop、swap、size、emptyqueue - C++ Reference (cplusplus.com)
2、deque:双端队列
deque - C++ Reference (cplusplus.com)
queue使用的是deque实现的
deque是一个比较复杂的容器
结合了list和vector的优势
但是,在结构的设计上做出了必要的牺牲
deque是一个一个的小数组,小数组的大小N固定
每一个小数组使用一个中控数组控制
中控数组内部是每一个小数组的开始位置
访问数据第i个数据时:
小数组就是i/N
小数组内部的位置是i%N
同时,中控数组从中间开始开辟,这是为了支持尾插和头插
尾插就是在中控数组空间的右边开辟小数组,进行小数组的头插
头插就是在中控数组空间的左边开辟小数组,但是是小数组的尾插
尽管deque结构的设计使得其在尾插和头插方面具备了list和vector不具备的优势
但是,这样的结构设计也导致了一个致命的弱点:
1、中间插入很麻烦
2、[]访问相对不快,没有vector快
所以说,中间插入不如list,访问遍历不如vector
但是综合来说,已经不错了
所以说,stack和queue的底层是使用deque实现的,因为基本不会有中间插入的场景
3、容器适配器设计模式
栈:
#pragma once
#include<vector>
using namespace std;
namespace myspace
{
template <class T, class Container = vector<T> >
class stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
T& top()
{
return _con.back();
}
private:
Container _con;
};
};
队列:
#pragma once
#include<deque>
//使用deque实现
using namespace std;
namespace mysapce2
{
template<class T,class Container = deque<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
private:
Container _con;
};
}