容器适配器 stack、queue、priority_queue

╰+攻爆jí腚メ 2024-04-17 05:52 91阅读 0赞

stack 是一种容器适配器,为什么叫它适配器呢？适配器是啥意思?

就是把**一种接口转换为另一种接口,** 在 C++ 封装了一些基本的容器，使之具备了新的调用接口（函数功能），就比如把 deque 封装一下变为一个具有 stack 功能的数据结构，新得到的数据结构就叫适配器，C++ 中适配器一共有三种，分别是 stack，queue ，priority\_queue;

--------------------

queue (队列)也是一种容器适配器，从队尾端插入元素，队头端弹出元素

优先级队列 priority\_queue 也是容器适配器，其底层结构并不是 deque, 而是 vector 数组，第一个元素总是最大的，依次降之，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority\_queue 可以看做是堆,：**默认情况下 priority\_queue 是大堆**

基本操作

// 默认情况下，创建的是大堆，其底层按照小于号比较
    	vector<int> v{  3,2,7,6,0,4,1,9,8,5 };
    	priority_queue<int> q1(v.begin(),v.end());
    
    	cout << q1.top() << endl;//9
    	// 如果要创建小堆，将第三个模板参数换成greater比较方式
    	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
    	cout << q2.top() << endl;//0

如果优先级队列放的是自定义数据类型，还需要程序猿重载 > 和 < 符号以及 cout<< ，有时候还需要提供比较器的规则

**stack 和 queue 为什么不选择 list 或 vector 最为底层结构**？

stack 是一种后进先出的特殊线性数据结构，因此只要具有push\_back()和pop\_back()操作的线性结构，所以其实 vector 和 list 都可以作为 stack 的底层结构，但是为什么选择 deque 是因为 stack 和 queue 不需要遍历，只需要固定在一端或两端操作即可，还有一个理由就是 stack 在元素增长的时候，deque 比 vector 效率高，而且内存使用率也高。

--------------------

**stack 模拟实现**

template<class T, class Con = deque<T>>
    class Stack{ 
    public:
    	Stack() { }
    	void Push(const T& x) {  _c.push_back(x); }
    	void Pop() {  _c.pop_back(); }
    	T& Top() {  return _c.back(); }
    	const T& Top()const {  return _c.back(); }
    	size_t Size()const {  return _c.size(); }
    	bool Empty()const {  return _c.empty(); }
    private:
    	Con _c;
    };

**queue 模拟实现**

template<class T, class Con = deque<T>>
    class Queue
    { 
    public:
    	Queue() { }
    	void Push(const T& x) {  _c.push_back(x); }
    	void Pop() {  _c.pop_front(); }
    	T& Back() {  return _c.back(); }
    	const T& Back()const {  return _c.back(); }
    	T& Front() {  return _c.front(); }
    	const T& Front()const {  return _c.front(); }
    	size_t Size()const {  return _c.size(); }
    	bool Empty()const {  return _c.empty(); }
    private:
    	Con _c;
    };