栈和队列接口函数
stack 栈接口函数
因为栈的结构限制，栈只能栈顶push和栈顶pop，
所以接口略少
queue 队列接口函数
队列只比栈多了一个接口:back
队列的front相当于栈的top
适配器
栈的类模板
其中第二个参数是Container，
且缺省参数为deque<T>
到这就可以引入一个概念：适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
可以类比为：
在数据结构的栈中，这种适配器是什么？
在C语言阶段实现栈时,我们
使用的底层是顺序表来实现,也就是
把顺序表做了一层封装和限制,让它
的功能变得和栈一样,C++这里也是一样!实现栈时不用再去写一个顺序表
而是直接调用库中的vector!
队列的类模板
其中第二个参数是Container，
且缺省参数为deque<T>
和stack是一样的
栈和队列模拟实现
栈
namespace wr
{
template<class T, class Container>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}队列
namespace wr1
{
template<class T,class Container = std::deque<T>>
class queue
{
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();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}我们和库中的缺省值保持一致,使用deque
这样实现栈十分方便，因为此时的栈就好像继承家业一样，
不用再去写构造和析构函数，默认生成的构造析构函数
会去调用内嵌类型的构造或析构，
在基础上实现接口函数就可以了。
deque基本介绍
deque也是STL库中的一个容器：
deque又被称为双端队列是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素,与list比较,空间利用率比较高（啥都能干，啥都干的不是特别好，既支持头插头删也有尾插尾删，也支持[]）
接口函数
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
deque通过一个叫中控数组的来控制（map箭头指向的数组）
deque扩容是直接另外开辟一份空间
再让中控数组指向新开辟的空间
再将原先空间的内容拷贝至新空间
优先级队列
优先级队列：priority_queue
它也是一个容量适配器
优先级队列默认是大堆
它的底层适配器默认是vector
优先级队列默认有三个类模板,第三个
模板就是决定此优先级队列是大堆还是小堆
它是仿函数,默认的less是大堆
我们显示传参greater时是小堆!
优先级队列的接口函数:
如果你想使用小堆,就要将前两个模板参数实例化后才能实例化第三个当less变成greater时,就是小堆
如果要改变大小堆，需要将参数补全，vector<int>也需要写上
优先级队列的模拟实现
由于优先级队列实际上就是个堆
所以在插入,删除之后.都需要做一件事
那就是向上调整或向下调整!所以插入和
删除的关键其实就在于向上/下调整!
向上调整：
void up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
break;
}
}向下调整：
void down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child + 1] > _con[child])
{
++child;
}
if (_con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}全部代码：
namespace wr2
{
template<class T,class Container=std::vector<T>>
class priority
{
public:
size_t size()
{
return _con.size();
}
void up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
break;
}
}
void down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child + 1] > _con[child])
{
++child;
}
if (_con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void push(const T& x)
{
_con.push_back(x);
up(_con.size() - 1);
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
down(0);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}总结
通过前面的容器学习，栈和队列学习起来也更加得心应手，
不仅仅是模拟实现，可以复用以前的容器，
连使用方法和函数接口都和之前一样，
而deque更像一个”六边形战士“，
不过各项能力都不出众。
