C++的stack和queue类（一）：适配器模式、双端队列与优先级队列
目录
基本概念
适配器模式
stack.h
test.cpp
双端队列-deque
仿函数
优先级队列
基本概念
1、stack和queue不是容器是容器适配器，它们没有迭代器
2、stack的quque的默认容器是deque，因为：
- stack和queue不需要遍历，只需要在固定的一端或者两端进行操作。
- 在stack中元素增加需要扩容时，deque比vector的效率高（不需要搬移大量数据）
- queue中的元素增长时，deque不仅效率高，而且内存使用率高
适配器模式
适配器模式是一种设计模式，用于将一个类的接口转换成客户希望的另一个接口，这种类型的设计模式属于结构型模式，它涉及到单个类的功能增强，适配器模式中有三个主要角色：
- 目标接口：客户端所期待使用的接口，适配器通过实现这个目标接口来与用户进行交互
- 被适配者：需要被适配以符合目标接口规范的现有类
- 适配器：实现了目标接口，并持有一个对被适配者对象的引用，在其方法内部调用被适配者对象来完成特定操作
stack.h
#pragma once
#include <assert.h>
#include <vector>
#include <list>
namespace bit
{//适配器模式//stack<int,vector<int>> st1;//stack<int,list<int>> st2;template<class T, class Container>class stack{public://入栈void push(const T& x){_con.push_back(x);}//出栈void pop(){_con.pop_back();}//求大小size_t size(){return _con.size();}//判空bool empty(){return _con.empty();}//获取栈顶元素const T& top(){return _con.back();}private:Container _con;};
}- 目标接口：构成栈所需的操作接口
- 被适配者：实现栈的底层数据结构（数组或链表）
- 适配器：bit::stack类
test.cpp
#include "Queue.h"
#include "Stack.h"
#include <stack>
#include <iostream>
using namespace std;void test_stack1()
{bit::stack<int,vector<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}int main()
{test_stack1();return 0;
}注意事项：函数参数传递的是对象，模板参数传递的是类型，函数参数可以传递缺省值，模板参数也可以传递缺省值
template<class T, class Container = vector<int>>
bit::stack<int> st; //此时就等价于bit::stack<int,vector<int>> st双端队列-deque
vector优缺点
- 优点：支持下标随机访问
- 缺点：头部或中间插入删除效率低，扩容有消耗
list的优缺点：
- 优点：任意位置插入删除效率都不错
- 缺点：不支持下标的随机访问
（第一个stack和queue的2:30:00处）
基本概念：deque是一种双开口的”连续“空间的数据结构，与vector相比，头插效率高，不需要搬移元素，与list相比，空间利用率更高，deque不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组
优点：deque 允许在两端进行高效插入和删除操作，且支持下标的随机访问
缺点：中间插入删除效率一般、[]效率一般（遍历时deque要频繁的检查是否移动到小空间边界）
仿函数
基本概念：仿函数是一个类或结构体，它重载了函数调用运算符 operator()，通过重载该运算符，这个类的实例就可以被像函数一样调用
#include <iostream>//仿函数 + 函数模板
template <class T>
struct MyComparator
{bool operator()(const T& x,const T& y) {return x < y;}
};int main() {MyComparator<int> cmp;cout<< cmp(1, 2) << endl;//有名对象cout<< cmp.operator()(1, 2) << endl;//有名对象cout<< MyComparator<int>()(1, 2) << endl;//匿名对象cout<< MyComparator<int>().operator()(1, 2) << endl;//匿名对象return 0;
}
优先级队列
~over~