🐱作者：傻响
🐱专栏：《数据结构_STL》
🔥格言：你只管努力，剩下的交给时间！

目录

栈

Stack介绍

模拟实现

队列

Queue介绍

常用的函数接口介绍

模拟实现

优先级队列

Priority queue介绍

Priority queue函数接口介绍

Priority queue模拟实现

Priority queue增加仿函数/函数对象

栈

Stack介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：

• empty：判空操作

• back：获取尾部元素操作

• push_back：尾部插入元素操作

• pop_back：尾部删除元素操作

1. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

常用的函数接口介绍

模拟实现

采用设计模型：适配器模式思想

#include
#include
using namespace std;
​
namespace ShaXiang
{// 设计模式：// 适配器模式：将已经有的东西，进行封装转换出你想要的东西.template>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介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作:

• empty：检测队列是否为空

• size：返回队列中有效元素的个数

• front：返回队头元素的引用

• back：返回队尾元素的引用

• push_back：在队列尾部入队列

• pop_front：在队列头部出队列

1. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标 准容器deque。

常用的函数接口介绍

模拟实现

采用设计模型：适配器模式思想

#include
#include
using namespace std;
​
namespace ShaXiang
{// 设计模式：// 适配器模式：将已经有的东西，进行封装转换出你想要的东西.template>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介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元 素)。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问，并支持以下操作：

• empty()：检测容器是否为空

• size()：返回容器中有效元素个数

• front()：返回容器中第一个元素的引用

• push_back()：在容器尾部插入元素

• pop_back()：删除容器尾部元素

1. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指 定容器类，则使用vector。

2. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。

Priority queue函数接口介绍

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成 堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意： 默认情况下priority_queue是大堆。

默认优先级为大堆：

#include
#include
using namespace std;
​
int main(){priority_queue 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
#include
#include
using namespace std;
​
int main(){priority_queue, greater> 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 5

Priority queue模拟实现

采用设计模型：适配器模式思想

#pragma once
#include 
#include 
#include 
using namespace std;
​
namespace ShaXiang
{// 设计模式：适配器模式template>class PriorityQueue{private:Container _container;
​public:// 无参构造函数.PriorityQueue(){}
​// 迭代器构造函数.templatePriorityQueue(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 
#include 
using namespace std;
​
namespace ShaXiang {// 仿函数/函数对象 - 类templateclass Less {public:const bool operator()(const T& a, const T& b) const {return a < b;}
​};
​templateclass Greater{public:const bool operator()(const T& a, const T& b) const {return a > b;}};
}
​
// 使用仿函数改造一下冒泡排序.
template
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 less;        // 单一调用可以使用匿名对象.// ShaXiang::Greater greater;int arr[] = { 1,4,2,6,9,3,0,7 };
​BubbleSort(arr, sizeof(arr) / sizeof(arr[0]), ShaXiang::Less());for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i){cout << arr[i] << " ";}cout << endl;
​BubbleSort(arr, sizeof(arr) / sizeof(arr[0]), ShaXiang::Greater());for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i){cout << arr[i] << " ";}cout << endl;
​return 0;
}
仿函数和函数高级玩法。这里用日期类在试一下（写出自己指定的仿函数）：#include 
#include 
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 Date_Less {
public:bool operator()(const T& d1, const T& d2) const {return *d1 < *d2;}
​
};
​
template
class Date_Greater {
public:bool operator()(const T& d1, const T& d2) const {return *d1 > *d2;}
};
​
void TestPriorityQueue()
{// 大堆priority_queue 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, greater> 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_Less> 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_Greater> 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 
#include 
#include 
using namespace std;
​
namespace ShaXiang
{// 仿函数/函数对象 - 类templateclass PriorityQueue_Less {public:const bool operator()(const T& a, const T& b) const {return a < b;}
​};
​templateclass PriorityQueue_Greater {public:const bool operator()(const T& a, const T& b) const {return a > b;}};
​
​// 设计模式：适配器模式template, class Compare = PriorityQueue_Less>class PriorityQueue{private:Container _container;
​public:// 无参构造函数.PriorityQueue(){}
​// 迭代器构造函数.templatePriorityQueue(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();}};
}