c++--stack，queue，priority
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
前言
对于栈和队列我们是不陌生的在数据结构阶段已经学习过记得当时我们还是用c语言将它一步一步造出来因为压栈与出栈正好满足数组的尾插与头删数组的代价是及小的。对于队列是头出队列尾插。所以就栈的实现就用的数组队列实现就用链表。在c++中呢vector和list就完美解决。priority_queue叫优先级队列实质就是大小堆堆的实现就是数组。
在很多时候stackqueuepriority_queue他们都叫做适配器这里简单的提一下它们就好比是农夫山泉不生产水是大自然的搬运工。也就意味着它“不生产代码,只是代码的搬运工”。下面我们通过底层代码的实现就能看出这一特性。
目录
一、stack-栈
stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。
1.1 stack的使用
下面这些接口的使用我相信大家已经是游刃有余了这里就不用过多演示若不熟悉查文档即可。
| 函数说明 | 接口说明 |
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
void test_stack()
{
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
}1.2stack的模拟实现
对stack的实现现在只关注它的实现全是调用。关于dequeContainer下面我们就会进行探究。
#pragma once
#include<vector>
#include <list>
namespace qhx
{
template<class T, class Container = deque<T>>
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;
};
}二、queue-队列
队列也是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。
2.1queue的使用
队列的接口其实与栈的接口基本一样而且使用方法也是一样。
| 函数声明 | 接口说明 |
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空是返回true否则返回false |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
void test_queue()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
2.2queue的模拟实现
#pragma once
#include<vector>
#include <list>
namespace qhx
{
template<class T, class Container = 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;
};
}queue的模拟实现也是非常简单的都是复用其他人代码。栈和队列的实现中我们发现都有class Container = deque<T>。
在queue和stack中都有这样一段话。
Queue
queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.
翻译队列是一种容器适配器专门设计用于在 FIFO 上下文先进先出中运行其中元素插入容器的一端并从另一端提取。
Stacks
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.
翻译
队列是一种容器适配器专门设计用于在 FIFO 上下文先进先出中运行其中元素插入容器的一端并从另一端提取。
class Container = deque<T>在这里就是容器适配器。
2.3容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。
设计模式的使用将提高软件系统的开发效率和软件质量节省开发成本。有助于初学者深入理解面向对象思想设计模式使设计方案更加灵活方便后期维护修改。
在stackqueue中 deque<T>接口转换到Container中。deque是什么呢我们不是说stack可以用vectorqueue用list吗怎么这里用的deque。
三、deque
在容器适配器为什么会选择deque那么就必须得从vectorlist的优缺点说起
3.1vectorlist的优缺点
vector
stack可以随机访问但是头部中部插入删除效率低并且还需要扩容
list
虽然queue在任何地方插入删除效率高但是不支持随机访问CPU高速缓存命中率低
对于deque就完美兼容vectorlist的优点。所以对于接口选择就是deque。
3.2deque的原理介绍
deque(双端队列)是一种双开口的"连续"空间的数据结构双开口的含义是可以在头尾两端进行插入和 删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。
这个是deque一段的buffer数组所以deque并不是真正连续的空间它是由一段一段这样的buffer数组链接而成一段一段的buffer数组被放在中控这个中控就是一个指针数组实际上deque类似于一个动态的二维数组 如图
这里的缓冲区就是buffer数组用于存放数据。map就是中控器就是存放指针。当map空间不够后会再开辟一个中控-map。
3.3deque--插入
插入操作--头插
插入操作--尾插
查找即相当于二维数组一样先找map中的地址第一层然后在找buffer第二层
缺点
那么我们发现它下标访问有一定的消耗没有vector快。当我们中间插入时候它的中间插入的时候需要挪动数据与list相比也是有消耗的。
deque不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作 为stack和queue的底层数据结构。
我们通过发现deque其实是没有想象中那样完美的它与vector和list相比是不够极致的。vector是吕布list是诸葛亮那么deque就是魏延。所以更多的时候我们更需要极致。
deque的底层实现是比较复杂的不仅仅是上诉简单两句的问题。
根据上图对于deque的维护是通过两个迭代器start和finsh。因为daque是作为stack和queue的底层默认容器一般来说deque是不需要进行中间插入的那么start和finsh就很好的处理头插和尾插。它通过frist和last指向头尾头插通过start的frist如果满了node链接map新开辟buffer的指针位置。尾插通过finish的last控制。如果top()和back(),即通过start的cur和finish的cur控制。、
3.4deque的接口
通过stackqueue的接口与deque的接口对比发现直接调用deque是非常适合充当stackqueue的默认容器。stackqueue就是直接调用deque的接口。
四、priority_queue-优先级队列
优先队列是一种容器适配器而它实质就是堆。是否还记得堆是完全二叉树中用数组实现的因为数组正好满足堆下标随机存取的需求标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。相对dequevector更加极致。priority_queue是默认大根堆。
4.1priority_queue的使用
priority_queue的使用来说也是比较简单的接口也比较少。
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first, last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空是返回true否则返回 false |
| top( ) | 返回优先级队列中最大(最小元素)即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素即堆顶元素 |
对于priority_queue的头文件我们通过手册发现priority_queue与queue都是一个头文件。
接口演示
//默认大根堆
void test()
{
priority_queue<int> p;
p.push(7);
p.push(1);
p.push(9);
p.push(2);
p.push(3);
p.push(4);
while (!p.empty())
{
cout << p.top() << " ";
p.pop();
}
}
结果9 7 4 3 2 1
小根堆 --greater
void test()
{
priority_queue<int, vector<int>, greater<int> > p;
p.push(7);
p.push(1);
p.push(9);
p.push(2);
p.push(3);
p.push(4);
while (!p.empty())
{
cout << p.top() << " ";
p.pop();
}
}结果1 2 3 4 7 9
4.2模拟实现
#pragma once
namespace qhx
{
template <class T,class Container = vector<int>>
class priority_queue
{
public:
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first,last)
{
//建堆-推荐向下调整建堆时间复杂度更小
for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; --i)//
{
adjust_down(i);
}
}
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] < con[child])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void adjust_down(size_t parent)
{
size_t michild = parent * 2 + 1;
while (michild < _con.size())
{
if (michild< _con.size() && _con[michild]>_con[michild + 1])
{
michild++;
}
if ( _con[michild]>] < _con[parent])
{
swap(_con[michild], _con[parent]);
parent = michild;
michild = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con(_con.size(-1)));
_con.pop_back();
adjust_down(0);
}
const T&top()const
{
return _con[0];
}
const empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
};
如果对向上/向下调整忘记了的就可以看下面图片回忆。
向上调整
向下调整
五、仿函数/函数对象
仿函数(functor)就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()这个类就有了类似函数的行为就是一个仿函数类了。
5.1仿函数的实现
这里是实现的比较大小的仿函数
#include <iostream>
using namespace std;
//仿函数/函数对象
namespace qhx
{
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y)
{
return x>y;
}
};
};
int main()
{
qhx::less<int> lessFunc;
if (lessFunc(3, 2))
cout << "yes" << endl;
else
cout << "no" << endl;
return 0;
}5.2仿函数的使用
冒泡排序
template <class T>
void BubbleSort(T* a, int n)
{
for (int i = 0; i < n; i++)
{
int flag = 0;
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
swap(&a[j - 1], &a[j]);
flag = 1;
}
if (flag == 0)
break;
}
}在C语言时期冒泡函数进行比较的时候是需要进入冒泡函数内部改变">","<"。或者是通过函数指针的方式在多增加一个函数参数。
方法一
if (a[j - 1] > a[j]) //改变其大与小
对于封装的好的函数来说这样对使用者是非常不友好的那么就可以通过接口的方式增加函数指针。
方法二
void BubbleSort(T* a, int nbool*pcom(int,int))
方法二的话这个方法是比较搓的使用的函数时需要传太多变量阅读性也不够强。那么c++中函数模板就起到了重要的作用了。我们可以增加一个模板参数再增加给函数的参数通过类型的对象去比较可以想函数一样去是使用。
template <class T,class compaer>
// 冒泡排序
void BubbleSort(T* a, int n,compaer com)
{
for (int i = 0; i < n; i++)
{
int flag = 0;
for (int j = 1; j < n - i; j++)
{
//if (a[j - 1] > a[j])
if (com(a[j - 1] , a[j]))
swap(a[j - 1], a[j]);
flag = 1;
}
if (flag == 0)
break;
}
}
void test_less()
{
qhx::less<int> lessFunc;
if (lessFunc(3, 2))
cout << "yes" << endl;
else
cout << "no" << endl;
}
void test_BubbleSort()
{
qhx::less<int> lessFunc;
int arr[] = { 1, 2, 4, 9, 8, 3, 6, 7 };
//BubbleSort(arr, sizeof(arr) / sizeof(arr[0]),lessFunc);
BubbleSort(arr, sizeof(arr) / sizeof(arr[0]), lessFunc);
for (auto e : arr)
{
cout << e << " ";
}
}
int main()
{
test_BubbleSort();
return 0;
}运行结果9 8 7 6 4 3 2 1
这里的less是根据优先级队列来定义的这里是降序greater就是升序。
注意这里模板参数是类函数调用类模板增加的代码内存时不多的。例如上述只增加1个字节。
5.2仿函数的用法进阶版
这里是比较Daet--自定义类型的大小。我们有Date类型比较大小的方式后但是对于Date*的比较是没有的故此我们创建一个struct类-默认公共类然后通过函数模板的调用实现了比较非自定义变量指针的大小。
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
struct PDateLess
{
bool operator()(const Date* d1, const Date* d2)
{
return *d1 < *d2;
}
};
struct PDateGreater
{
bool operator()(const Date* d1, const Date* d2)
{
return *d1 > *d2;
}
};
void TestPriorityQueue()
{
// 大堆需要用户在自定义类型中提供<的重载
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout << q1.top() << endl;
// 如果要创建小堆需要用户提供>的重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout << q2.top() << endl;
// 大堆
priority_queue<Date*, vector<Date*>, PDateLess> q3;
q3.push(new Date(2018, 10, 29));
q3.push(new Date(2018, 10, 28));
q3.push(new Date(2018, 10, 30));
cout << *q3.top() << endl;
// 小堆
priority_queue<Date*, vector<Date*>, PDateGreater> q4;
q4.push(new Date(2018, 10, 29));
q4.push(new Date(2018, 10, 28));
q4.push(new Date(2018, 10, 30));
cout << *q4.top() << endl;
}
int main()
{
TestPriorityQueue();
return 0;
}