c++中的Stack与Queue
c++中的Stack与Queue
一·queue与stack：
1.queue介绍：
①队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
②只要是能满足对队列功能函数实现的容器，都可以作为它的底层容器。
底层容器具备条件：
empty：检测队列是否为空.
size：返回队列中有效元素的个数.
front：返回队头元素的引用.
back：返回队尾元素的引用.
push_back：在队列尾部入队列.
pop_front：在队列头部出队列.
③但是默认的是deque（一种双端队列，后续讲到）。
2.queue模拟实现：
#pragma once
namespace sq {
template<class T, class Con = deque<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;
};
}3stack介绍：
同上面queue也是容器适配器，本身不是容器，但是有底层容器，像list，vector这样的容器都可以做，但是默认是deque。
4stack模拟实现：
#pragma once
namespace sq {
template<class T, class Con = deque<T>>
class stack
{
public:
stack() {
}
void push(const T& x) {
_c.push_back(x);
}
void pop() {
_c.pop_back();
}
T& top() {
return _c.back();
}
const T& top()const {
return _c.back();
}
size_t size()const {
return _c.size();
}
bool empty()const {
return _c.empty();
}
private:
Con _c;
};
}二·priority_queue（优先队列）：
1·介绍：
①容器适配器，它的第一个元素是最大的元素。
②理想结构类似于堆，只能访问它的top（访问队头，删队头时候与队尾互换，再删除）。
③底层容器用vector和list都可以，但是一般默认为vector。
④含有的接口函数：
priority_queue()与priority_queue(first, last) 构造一个空的优先级队列，也可以用迭代器区间初始化。
empty( ) 检测优先级队列是否为空，是返回true，否 则返回false。
top( ) 返回优先级队列中最大(最小元素)，即堆顶元 素。
push(x) 在优先级队列中插入元素x。
pop() 删除优先级队列中最大(最小)元素，即堆顶元 素。
2·仿函数：
即一种模版，它重载了operator()；使得该模版类的对象可以像函数一样使用。如：
template<class T>
class Great {
public:
bool operator()(const T& a, const T& b) {
return a > b;
}
};
template<class T>
class Less {
public:
bool operator()(const T& a, const T& b) {
return a < b;
}
};仿函数特性：
在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态。
仿函数即使定义相同，也可能有不同的类型。
仿函数通常比一般函数速度慢。
仿函数使程序代码变简单。
3·模拟实现：
#pragma once
#include<vector>
namespace pq
{
template<class T>
class Great {
public:
bool operator()(const T& a, const T& b) {
return a > b;
}
};
template<class T>
class Less {
public:
bool operator()(const T& a, const T& b) {
return a < b;
}
};
template <class T, class Container = vector<T>, class Compare = pq::Less<T> >
//默认less大堆
class priority_queue
{
public:
//保证原来堆都是有一定大小堆序的，故上调
void upadjust(int child) {
int parent = (child-1)/2;
while (child > 0) {
if (com(c[parent],c[child])) {
swap(c[child] ,c[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void downadjust(int parent) {
int child = 2 * parent + 1;
while (child<c.size()) {
if (child+1<c.size()&&com(c[child], c[child + 1])) {
child++;
}
if (com( c[parent],c[child])) {
swap(c[child], c[parent]);
parent=child;
child = 2 * parent + 1;
}
else {
break;
}
}
}
priority_queue() {
}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last) {
while (first != last) {
c.push_back(*first);
upadjust(c.size() - 1);
first++;
}
}
const bool empty() const {
return c.empty();
}
const size_t size() const {
return c.size();
}
const T& top() const {
return c.front();
}
void push(const T& x) {
c.push_back(x);
upadjust(c.size() - 1);
}
void pop() {
swap(c[0], c[c.size() - 1]);
c.pop_back();
downadjust(0);
}
private:
Container c;
Compare com;
};
}三.容器适配器：
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设 计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
简单来说就是：它自己不是容器，用的其他的容器进行封装然后再使用，那么这个类就是容器适配器。
比如queue和stack的实现它们就是容器适配器，但它们不是容器，而是对底层容器进行封装，即对deque封装。
如：
template<class T, class Con = deque<T>>//底层容器的类型四.deque：
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
注：deque的空间不是绝对连续的:它并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组。
如：
访问它就可以利用类似二维数组，但是它的底层实现是复杂的，如要判断数据相对位置，控制四个指针的指向。故通常作为了解即可。
当然可以理解为它是vector和list结合，但并不完全。与vector相比，它头插，头删，尾插，可以直接进行，不用大量挪动以及容量不足的时候扩大量空间，与list相比，它的底层空间中控数组里面存着的指针所指向的数组是连续的，这样就可以提高一定空间利用率。
但是不可能能完全综合了优点，还存在个致命的缺点：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际遍历不用它。 故这里只是在stack和queue的封装，底层用了它。
那为什么这里会用deque而不是vector或者list：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的 元素增长时，deque不仅效率高，而且内存使用率高。
腾讯云开发者
