栈和队列的模拟实现

容器适配器

容器适配器（Container Adapter） 是一种基于现有容器类（如 vector、deque、list 等）构建的 包装器（Wrapper）。

1.容器适配器本身不直接管理数据存储，而是依赖底层容器（称为 底层容器 或 基础容器）实现存储和访问操作。例如：

stack 默认基于 deque 实现。
queue 默认基于 deque 实现。
priority_queue 默认基于 vector 实现。

2.适配器会屏蔽底层容器的部分接口，仅暴露特定操作所需的接口。

栈（stack） 只允许在栈顶进行插入（push）和删除（pop）操作，屏蔽了随机访问等功能。
队列（queue） 只允许在队尾插入（push）、队头删除（pop），屏蔽了中间元素的操作。

3.底层容器可定制。

#include <stack>
#include <vector>
#include <list>// 使用 vector 作为底层容器
std::stack<int, std::vector<int>> stack1;// 使用 list 作为底层容器
std::stack<int, std::list<int>> stack2;

priority_queue(优先级队列）

priority_queue的使用

int main()
{priority_queue<int> pq;//默认是大的优先级高(大堆）//变小堆//priority_queue<int,vector<int>,greater<int>> pq;pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

大堆调试：

小堆调试：

priority_queue的模拟实现：

#include<vector>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;}
};namespace bit
{// 默认是大堆template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_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);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){// 先假设左孩子小size_t child = parent * 2 + 1;Compare com;while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

仿函数

什么叫仿函数？

仿函数：本质是一个类，这个类重载operator(),他的对象可以像函数一样使用

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;}
};// < 升序
// > 降序
template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{for (int j = 0; j < n; j++){// 单趟int flag = 0;for (int i = 1; i < n - j; i++){//if (a[i] < a[i - 1])if (com(a[i], a[i - 1])){swap(a[i - 1], a[i]);flag = 1;}}if (flag == 0){break;}}
}int main()
{Less<int> LessFunc;Greater<int> GreaterFunc;// 函数对象（仿函数）本质是一个对象cout << LessFunc(1, 2) << endl;cout << LessFunc.operator()(1, 2) << endl;int a[] = { 9,1,2,5,7,4,6,3 };BubbleSort(a, 8, LessFunc);BubbleSort(a, 8, GreaterFunc);BubbleSort(a, 8, Less<int>());BubbleSort(a, 8, Greater<int>());return 0;
}

需要自己实现仿函数的情况：

1.类类型不支持比较大小。
2.支持比较大小，但是比较的逻辑不是你想要的。

class Date
{friend ostream& operator<<(ostream& _cout, const Date& d);
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);}
private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}class DateLess
{
public:bool operator()(Date* p1, Date* p2){return *p1 < *p2;}
};
//测试
priority_queue<Date*, vector<Date*>, DateLess> q2;priority_queue<Date*> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();

栈的模拟实现

#include<deque>namespace bit
{// Container适配转换出stacktemplate<class T, class Container = deque<T>>//deque:vector和list的缝合怪class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

队列的模拟实现

#include<deque>namespace bit
{// Container适配转换出queuetemplate<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() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

deque（vector和list的缝合怪）

为什么选择deque作为stack和queue的底层默认容器？

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

deque的优缺点

vector和list的优缺点