【C++】STL - Stack - Queue - PriorityQueue使用和模拟实现
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
🐱作者傻响
🐱专栏《数据结构_STL》
🔥格言你只管努力剩下的交给时间
目录
栈
Stack介绍
-
stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行 元素的插入与提取操作。
-
stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定 的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。
-
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下 操作
empty判空操作
back获取尾部元素操作
push_back尾部插入元素操作
pop_back尾部删除元素操作
-
标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器 默认情况下使用deque。
常用的函数接口介绍
模拟实现
采用设计模型适配器模式思想
#include<iostream>
#include<deque>
using namespace std;
namespace ShaXiang
{
// 设计模式
// 适配器模式将已经有的东西进行封装转换出你想要的东西.
template<class T, class Container = deque<T>>
class Stack
{
private:
Container _container;
public:
// 入栈
void Push(const T& val)
{
_container.push_back(val);
}
// 删除数据
void Pop()
{
_container.pop_back();
}
// 读取栈顶数据
const T& Top()
{
return _container.back();
}
// 栈大小
size_t Size()
{
return _container.size();
}
// 判断栈是否为空
bool Empty()
{
return _container.empty();
}
};
}队列
Queue介绍
-
队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端 提取元素。
-
队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列从队头出队列。
-
底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作:
empty检测队列是否为空
size返回队列中有效元素的个数
front返回队头元素的引用
back返回队尾元素的引用
push_back在队列尾部入队列
pop_front在队列头部出队列
-
标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标 准容器deque。
常用的函数接口介绍
模拟实现
采用设计模型适配器模式思想
#include<iostream>
#include<deque>
using namespace std;
namespace ShaXiang
{
// 设计模式
// 适配器模式将已经有的东西进行封装转换出你想要的东西.
template<class T, class Container = deque<T>>
class Queue
{
public:
// Push入
void Push(const T& val)
{
_container.push_back(val);
}
// Pop出
void Pop()
{
_container.pop_front();
}
// 返回头数据
const T& Front()
{
return _container.front();
}
// 返回尾数据
const T& Back()
{
return _container.back();
}
// 列大小
size_t Size()
{
return _container.size();
}
// 判断列是否为空
bool Empty()
{
return _container.empty();
}
private:
Container _container;
};
}上面的Stack和Queue是适配了list和vector的底层实现的但是vector和list是不完美的。
-
vector的缺点头部中部插入删除效率慢扩容消耗时间。
-
list的缺点不支持随机访问CPU高速缓存命中低。
deque完美的融合兼具vector和list的优点但是下标随机访问有一定的消耗没有vector快中间插入删除也有一定的消耗相比list的中间插入删除不够极致没有list快。
优先级队列
Priority queue介绍
-
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。
-
此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素)。
-
优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。
-
底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作
-
empty()检测容器是否为空
-
size()返回容器中有效元素个数
-
front()返回容器中第一个元素的引用
-
push_back()在容器尾部插入元素
-
pop_back()删除容器尾部元素
-
标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指 定容器类则使用vector。
-
需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
Priority queue函数接口介绍
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。
默认优先级为大堆
#include<iostream>
#include<queue>
using namespace std;
int main(){
priority_queue<int> pq;
pq.push(3);
pq.push(2);
pq.push(1);
pq.push(4);
pq.push(5);
while (!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
// 打印结果5 4 3 2 1将默认优先级改为小堆
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
int main(){
priority_queue<int,vector<int>, greater<int>> pq;
pq.push(3); // less 大堆
pq.push(2); // greater 小堆
pq.push(1);
pq.push(4);
pq.push(5);
while (!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
// 打印结果1 2 3 4 5Priority queue模拟实现
采用设计模型适配器模式思想
#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
namespace ShaXiang
{
// 设计模式适配器模式
template<class T, class Container = vector<T>>
class PriorityQueue
{
private:
Container _container;
public:
// 无参构造函数.
PriorityQueue()
{}
// 迭代器构造函数.
template<class InputIterator>
PriorityQueue(InputIterator first, InputIterator last)
: _container(first,last)
{
for (int i = (int(_container.size()) - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
public:
// 堆->向上调整.
void AdjustUp(size_t child) {
// 求出父亲节点.
size_t parent = (child - 1) / 2;
while (child > 0) {
if (_container[child] > _container[parent]) {
swap(_container[child], _container[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
// 堆->向下调整.
void AdjustDown(size_t parent) {
// 模糊算法找最小的孩子.
size_t minChild = parent * 2 + 1;
while (minChild < _container.size()) {
if (minChild + 1 < _container.size() && _container[minChild + 1] > _container[minChild]) {
++minChild;
}
if (_container[minChild] > _container[parent]) {
swap(_container[minChild], _container[parent]);
parent = minChild;
minChild = parent * 2 + 1;
}
else {
break;
}
}
}
// 插入数据.
void Push(const T& val) {
_container.push_back(val);
AdjustUp(_container.size() - 1);
}
// 删除数据.
void Pop() {
swap(_container[0], _container[_container.size() - 1]);
_container.pop_back();
AdjustDown(0);
}
// 访问栈顶数据.
const T& Top() const {
return _container[0];
}
// 判断是否为空
bool Empty() const {
return _container.empty();
}
// 获取大小
size_t Size() const {
return _container.size();
}
};
}Priority queue增加仿函数/函数对象
仿函数和函数对象实际是一个类。
我们可以使用仿函数/函数对象来改造一个冒泡排序看一下效果
#pragma once
#include <iostream>
#include <algorithm>
using namespace std;
namespace ShaXiang {
// 仿函数/函数对象 - 类
template<class T>
class Less {
public:
const bool operator()(const T& a, const T& b) const {
return a < b;
}
};
template<class T>
class Greater{
public:
const bool operator()(const T& a, const T& b) const {
return a > b;
}
};
}
// 使用仿函数改造一下冒泡排序.
template<class T, class Compare>
void BubbleSort(T* data, size_t n, Compare compare) {
int flag = 0;
for (size_t i = 0; i < n ; ++i) {
for (size_t j = 1; j < n - i; ++j) {
if (compare(data[j], data[j-1])) {
swap(data[j - 1], data[j]);
flag = 1;
}
}
if (flag == 0)
break;
}
}
int main() {
// ShaXiang::Less<int> less; // 单一调用可以使用匿名对象.
// ShaXiang::Greater<int> greater;
int arr[] = { 1,4,2,6,9,3,0,7 };
BubbleSort<int>(arr, sizeof(arr) / sizeof(arr[0]), ShaXiang::Less<int>());
for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
cout << arr[i] << " ";
}
cout << endl;
BubbleSort<int>(arr, sizeof(arr) / sizeof(arr[0]), ShaXiang::Greater<int>());
for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
仿函数和函数高级玩法。
这里用日期类在试一下写出自己指定的仿函数
#include <iostream>
#include <queue>
using namespace std;
class Date {
private:
int _year;
int _month;
int _day;
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
public:
friend ostream& operator<<(ostream& out, const Date& d)
{
out << d._year << "-" << d._month << "-" << d._day;
return out;
}
public:
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);
}
};
// 仿函数/函数对象 - 类
template<class T>
class Date_Less {
public:
bool operator()(const T& d1, const T& d2) const {
return *d1 < *d2;
}
};
template<class T>
class Date_Greater {
public:
bool operator()(const T& d1, const T& d2) const {
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*>, Date_Less<Date*>> 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*>, Date_Greater<Date*>> 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;
}嵌入Priority queue中
#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
namespace ShaXiang
{
// 仿函数/函数对象 - 类
template<class T>
class PriorityQueue_Less {
public:
const bool operator()(const T& a, const T& b) const {
return a < b;
}
};
template<class T>
class PriorityQueue_Greater {
public:
const bool operator()(const T& a, const T& b) const {
return a > b;
}
};
// 设计模式适配器模式
template<class T, class Container = vector<T>, class Compare = PriorityQueue_Less<T>>
class PriorityQueue
{
private:
Container _container;
public:
// 无参构造函数.
PriorityQueue()
{}
// 迭代器构造函数.
template<class InputIterator>
PriorityQueue(InputIterator first, InputIterator last)
: _container(first,last)
{
for (int i = (int(_container.size()) - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
public:
// 堆->向上调整.
void AdjustUp(size_t child) {
// 使用仿函数/函数对象.
Compare compare;
// 求出父亲节点.
size_t parent = (child - 1) / 2;
while (child > 0) {
if (compare(_container[parent], _container[child])) {
swap(_container[child], _container[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
// 堆->向下调整.
void AdjustDown(size_t parent) {
// 使用仿函数/函数对象.
Compare compare;
// 模糊算法找最小的孩子.
size_t minChild = parent * 2 + 1;
while (minChild < _container.size()) {
if (minChild + 1 < _container.size() && compare(_container[minChild], _container[minChild + 1])) {
++minChild;
}
if (compare(_container[parent], _container[minChild])) {
swap(_container[minChild], _container[parent]);
parent = minChild;
minChild = parent * 2 + 1;
}
else {
break;
}
}
}
// 插入数据.
void Push(const T& val) {
_container.push_back(val);
AdjustUp(_container.size() - 1);
}
// 删除数据.
void Pop() {
swap(_container[0], _container[_container.size() - 1]);
_container.pop_back();
AdjustDown(0);
}
// 访问栈顶数据.
const T& Top() const {
return _container[0];
}
// 判断是否为空
bool Empty() const {
return _container.empty();
}
// 获取大小
size_t Size() const {
return _container.size();
}
};
}