栈、队列、优先级队列的模拟实现
优先级队列的模拟实现
- 栈
- stack的模拟实现
- push()
- pop()
- top()
- size()
- empty()
- swap()
- stack总代码
- 队列
- queue的模拟实现
- push()
- pop()
- front()
- back()
- empty()
- size()
- swap()
- queue总代码
- 优先级队列(堆)
- push()
- pop()
- top()
- empty()
- size()
- swap()
- priority_queue总代码
- deque的了解
栈
在C++STL中栈并不属于容器一类，而属于适配器！
1、栈是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2、stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定
的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3、stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下
操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
4、标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。
stack的模拟实现
对于栈的话，我们可以在其底层封装一个容器来实现：
template<class T, class Container=std::deque<T>>
class stack
{
private:
Container _con;//使用该容器来实现栈，具体使用那个类型的容器，完全由程序员自己决定！默认情况是使用缺省值(deque)双端队列来实现！
}
对于stack我们可以不用写构造函数、拷贝构造函数、析构函数、重载赋值运算符！因为stack类的成员变量是个自定义类型，如果我们使用stack的默认构造函数的话，编译器会调用自定义类型的默认构造函数来初始化_con成员变量；同理如果使用默认拷贝构造的话，对于自定义类型也会调用自定义类型的拷贝构造函数；如果使用默认析构函数的话，对于自定义类型也会调用自定义类型的析构函数来释放空间，不会造成内存泄漏；赋值运算符同理！
push()
void push(const T& val)//对于栈的插入，也就是对于容器_con的尾插
{
_con.push_back(val);
}
pop()
void pop()//对于stack的删除就是对于容器_con的尾删除!
{
assert(empty() == false);
_con.pop_back();
}
top()
T Top()const//获取stack的栈顶元素就是获取容器_con的尾部元素
{
assert(empty()==false);
return _con.back();
}
size()
size_t size()const//获取stack的元素就是获取容器_con的元素个数
{
return _con.size();
}
empty()
bool empty()const//判断stack是不是空就是判断容器_con是不是空
{ return _con.empty();
}
swap()
void swap(stack<T,Container>&st)//交换stack就是交换两个stack内部的容器_con
{
_con.swap(st._con);
}
stack总代码
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<list>
#include<deque>
namespace MySpace
{
template<class T, class Container=std::deque<T>>
class stack
{
public:
explicit stack(const Container&con= Container())
:_con(con)
{
}
bool empty()const
{ return _con.empty();
}
size_t size()const
{
return _con.size();
}
T Top()const
{
assert(empty()==false);
return _con.back();
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
assert(empty() == false);
_con.pop_back();
}
void swap(stack<T,Container>&st)
{
_con.swap(st._con);
}
private:
Container _con;//组成stack的容器
};
}
队列
1、 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端
提取元素。
2、队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的
成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3、底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操
作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4、标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
queue的模拟实现
队列与栈一样不属于容器，而属于适配器；因此队列的底层也是封装的一个容器；
因此队列也不需要自己写默认构造函数、拷贝构造函数、赋值运算符重载、析构函数，我们用编译器默认生成的就够了！
template <class T,class Container=std::deque<T>>//不建议使用vector作为容器，这样的话头插效率低
class queue
{
private:
Container _con;
}
push()
void push(const T& val)//对于queue的插入就是对于容器的尾插
{
_con.push_back(val);
}
pop()
void pop()//对于queue的删除就是对于容器_con的头删
{
assert(empty() == false);
_con.erase(_con.begin());
}
front()
T front()const//获取queue队头元素,也就是获取容器_con首元素
{
assert(empty() == false);
return _con.front();
}
back()
T back()const//获取队尾元素，也就是获取容器_con的尾元素
{
assert(empty() == false);
return _con.back();
}
empty()
bool empty()const//对于queue的判空，也就是对于容器_con的判空
{
return _con.empty();
}
size()
size_t size()const {//对于queue的大小就是容器_con的大小
return _con.size();
}
swap()
void swap(queue<T, Container> &q)//对于queue的交换就是交换底层的两个容器；
{
_con.swap(q._con);
}
queue总代码
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<list>
#include<deque>
namespace MySpace
{
template <class T,class Container=std::deque<T>>//不建议使用vector作为容器，这样的话头插效率低
class queue
{
public:
explicit queue(const Container& con = Container())
:_con(con)
{}
bool empty()const
{
return _con.empty();
}
size_t size()const {
return _con.size();
}
T front()const
{
assert(empty() == false);
return _con.front();
}
T back()const
{
assert(empty() == false);
return _con.back();
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
assert(empty() == false);
_con.erase(_con.begin());
}
void swap(queue<T, Container> &q)
{
_con.swap(q._con);
}
private:
Container _con;
};
}
优先级队列(堆)
学过数据结构的读者应该直到数据结构中有一种叫做“堆”的数据结构，在C++中这种数据结构叫做“优先级队列”！关于堆的详细了解可以参考我的另一篇博客：二叉树和堆
优先级队列在STL中也是一个适配器！
因此对于优先级队列的定义我们可以参照stack和queue:
template <class T,class Container=std::vector<int>,class Compare=std::less<T>>
class priority_queue
{
private:
Container _con;
}
其中模板参数Container是容器类型；T是元素类型:Compare是仿函数的类型！用于控制建立大堆还是建立小堆；
其中根据STL的实现方法是：优先级队列默认是建大堆，如果需要建小堆的话，Compare模板参数需要传递greater <T>;
push()
优先级队列的push与stack、queue的插入不同，优先级队列push过后还需要调整当前的堆结构，使其再插入一个元素过后仍然保持堆结构，我们通常使用向上调整的算法建队！
void push(const T& val)
{
//先插入
_con.push_back(val);
//向上调整
AdjustUp(_con.size()-1);
}
void AdjustUp(int child)//向上调整算法
{
Compare com;//实例化一个比较对象
//如果Compare是个小于类的话，那么com实例化出来的就是小于对象，里面的operator(A，B)函数是比较A是否小于B的
int parent = (child - 1) / 2;
while (child>0)
{
//if (_con[child] > _con[parent])//判断[parent]是否小于[child]
if (com(_con[parent], _con[child]))//如果_con[parent]<_con[child]就建立小堆；如果_con[parent]>_con[child]就建立大堆；至于_con[parent]与_con[child]使用<比较还是>比较由我们传递的类型参数Compare来决定！
{
std::swap(_con[child],_con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
pop()
优先级队列删除元素，是删除堆顶的元素，再删除堆顶元素过后，我们仍需要保持该结构是个堆；为了降低调整成本，优先级队列的删除操作的步骤一般都是，交换堆顶元素与堆底元素，然后堆的大小减1，然后再从对顶开始执行向下调整算法调整堆；
void pop()
{
assert(empty()==false);
//swap
std::swap(_con[0],_con[_con.size()-1]);
//size--
_con.pop_back();
//向下调整
AdjustDown(0);
}
void AdjustDown(int parent)
{
Compare com;//实例化一个比较对象
int child = 2 * parent + 1;
while (child < _con.size())
{
//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
if (child + 1 < _con.size() && com(_con[child],_con[child+1]))
child++;
//if (_con[child] > _con[parent])
if (com(_con[parent],_con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
}
else
break;
}
}
top()
const T& top()const//返回堆顶元素,也就死返回容器_con的首元素
{
return _con.front();
}
empty()
bool empty()const//判断一个优先级队列是不是空，就是判断一个容器是不是空
{
return _con.empty();
}
size()
size_t size()const//求优先级队列的元素个数，就是返回容器的元素个数
{
return _con.size();
}
swap()
void swap(priority_queue<T, Container, Compare>&pq)//两个优先级队列之间的交换就是交换底层的容器;
{
_con.swap(pq._con);
}
priority_queue总代码
#pragma once
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<assert.h>
namespace MySpace
{
template<class T>
struct less//小于模板(用于建大堆)
{
bool operator()(const T& v1, const T& v2)//这个函数的目的是为了比较v1是否小于v2
{
return v1 < v2;
}
};
template<class T>
struct less<T*>//小于模板偏特化，如果less模板的模板参数是指针，则用这个版本的less模板实例化对象
{
bool operator()( T* x, T * y)const
{
return *x < *y;
}
};
template<class T>
struct greater//大于模板(用于建小堆)
{
bool operator()(const T& v1, const T& v2)const//这个函数的目的是为了比较v1是否大于v2
{
return v1 > v2;
}
};
template<class T>
struct greater<T*>//大于模板偏特化，如果greater模板的模板参数为指针类型，那么编译器就用这个版本的greater模板实例化对象！
{
bool operator()( T* x, T* y)
{
return *x > *y;
}
};
//默认建的是大堆，建大堆用less(小于)
//建小堆用greter;
template <class T,class Container=std::vector<int>,class Compare=MySpace::less<T>>
class priority_queue
{
public:
void push(const T& val)
{
//先插入
_con.push_back(val);
//向上调整
AdjustUp(_con.size()-1);
}
void pop()
{
assert(empty()==false);
//swap
std::swap(_con[0],_con[_con.size()-1]);
//size--
_con.pop_back();
//向下调整
AdjustDown(0);
}
const T& top()const
{
return _con.front();
}
bool empty()const
{
return _con.empty();
}
void swap(priority_queue<T, Container, Compare>&pq)
{
_con.swap(pq._con);
}
size_t size()const
{
return _con.size();
}
private:
void AdjustDown(int parent)
{
Compare com;//实例化一个比较对象
int child = 2 * parent + 1;
while (child < _con.size())
{
//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
if (child + 1 < _con.size() && com(_con[child],_con[child+1]))
child++;
//if (_con[child] > _con[parent])
if (com(_con[parent],_con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
}
else
break;
}
}
void AdjustUp(int child)
{
Compare com;//实例化一个比较对象
int parent = (child - 1) / 2;
while (child>0)
{
//if (_con[child] > _con[parent])//判断[parent]是否小于[child]
if (com(_con[parent], _con[child]))//判断[parent]是否小于[child]
{
std::swap(_con[child],_con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
Container _con;//容器
};
}
deque的了解
通过前面的学习，我们知道了vector与list的优缺点:
vector:
优点：
1、支持随机访问；
2、尾插尾删效率高；
缺点：
1、中间和头部的插入删除，效率极低！
list
优点：
1、插入删除效率高；
缺点：
2、不支持随机访问；
那么有没有结合vector与list两个容器的优点的数据结构呢？
答案是有的！
双端队列(deque)就出现了：
什么是deque?
deque是一个两端开口，逻辑上空间是连续的数据结构，该数据结构的头部插入删除、尾部插入删除效率极高，时间复杂度为O(1)；与list比较，空间利用率比较高！它的每个元素中不需要像list那样存储下一个节点的指针！
同时deque也支持像vector一样用[ ]来访问元素！
但是deque的底层真正实现并不是一块连续的空间，刚才我们也说了deque是在逻辑上连续的空间！真正的deque是由一段一段的连续空间组成起来的，有点类似于C语言中的二维数组！
其底层结构如下：
既然deque这么强，那么为什么还没替代掉vector和list呢？
deque的缺点：
与vector相比，头插头删效率的确高，不需要挪动元素，同时扩容代价下，deque的扩容只需要对中控数组进行扩容，不需要对存储元素的小段数组进行扩容，拷贝过来的也是这些小段数组的指针！
与list相比，空间利用率的确变高了，同时也支持了随机访问；
但是deque有一个致命的缺点：不适合遍历，因为deque迭代器在遍历的时候，会频繁的检测这次遍历是否移动到下一个小段数组中去，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，同时deque特别不适合中间来插入和删除数据，在中间删除和插入数据都需要大量的挪动数据，代价非常大！
而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构；