模拟实现源代码已上传至gitee仓库:stack_queue_learn
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和 删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比 较高。
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维 数组:
如果需要尾插,就在中控数组中新开一个buffer数组,如果头插,就在中控数组前面开一个buffer数组,如果中控数组满了就扩容。
此时如何查找第i个值呢?
i=i-第一个buffer的数据个数
那deque是如何借助其迭代器维护其假想连续的结构呢?
deuqe内部有两个迭代器:iterator start
和iterator finish
与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。
与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。
#pragma once
#include<vector>
#include<list>
namespace gwj
{
//stack<int,vector<int>> st1;
//stack<int,list<int>> st2;
template<class T,class Container=std::vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top()
{
return _con.back();
}
private:
Container _con;
};
}
Container=std::vector<T>
这意味着如果用户不显式提供容器类型,将默认使用 std::vector 作为容器类型。
template<class T,class Container=std::vector<T>>
: 这是一个类模板的声明,定义了一个名为 stack
的类模板。它有两个模板参数:T
表示栈中元素的类型,Container
表示用于存储栈元素的容器类型。其中 Container=std::vector<T>
是默认模板参数,如果用户不显式指定容器类型,则默认使用 std::vector
#pragma once
#include<deque>
#include <list>
namespace gwj
{
template<class T, class Con =std::deque<T>>
//template<class T, class Con = list<T>>
class queue
{
public:
queue() {}
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& back() { return _c.back(); }
const T& back()const { return _c.back(); }
T& front() { return _c.front(); }
const T& front()const { return _c.front(); }
size_t size()const { return _c.size(); }
bool empty()const { return _c.empty(); }
private:
Con _c;
};
}
template<class T, class Con = std::deque<T>>
: 这是一个类模板的声明,定义了一个名为 queue
的类模板。它有两个模板参数:T
表示队列中元素的类型,Con
表示用于存储队列元素的容器类型。默认情况下,容器类型为 std::deque<T>
,即双端队列。
前面我们学习了string、vector、list现在我们来学习stack和queue时,我们会发现轻松了很多,在学习stl时,遇到不会的函数调用接口,我们直接去查阅文档即可。