C++ stack (STL容器适配器)

浅浅的花香味﹌ 2023-06-08 03:19 139阅读 0赞

**目录**

适配器

stack

stack的使用

stack模拟实现

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

### **适配器** ###

> 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，适配器是将一个类的接口转换成客户希望的另外一个接口。
> 
> 举个栗子, 咱们香港的插头和我们内地是不一的, 如下图, 这种插头在咱们内地是不方便使用的, 要是香港同胞到对岸深圳转一转, 被繁华的深圳所吸引, 不禁多留了两天, 那这时候手机要充电怎么充电啊, 不过没关系, 我们有适配器, 其实真正给手机充电的还是手机充电器, 适配器只是方便了人们的使用而已. 
> 
>    ![format_png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]  
>           港版充电器                                                     适配器                                                           适配器的使用
> 
> 常见的**容器适配器**有stack , queue,  priority\_queue,  它们就相当于上图的适配器, 真正给手机充电的是还是充电头, 同样的道理, 它们**底层是靠别的容器实现的**  
> 例如:  
> stack可以用vector, deque, list实现.   
> queue可以用 deque, list实现  
> priority\_queue, 可以用 deque, vector实现

### stack ###

> 1. stack是一种容器适配器，专门用在具有后进先出操作的需求中，其删除只能从容器的一端进行元素的插入与提取操作。  
> 2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。  
> 3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类**必须支持以下操作**：  
>     empty：判空操作  
>     back：获取尾部元素操作  
>     push\_back：尾部插入元素操作  
>     pop\_back：尾部删除元素操作  
> 4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。  
> 5. 需要头文件\#include<stack>  
> 6. 为什么选择deque作为stack的底层默认容器  
> 主要原因  
> deque优点: 两端插入删除最快的  
> deque缺点: 迭代器复杂效率低  
> stack利用了优点规避了缺点, 在末端插删, 且并未使用迭代器, 所以deque最优
> 
> stack图示 :  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]
> 
> [C++STL容器适配器之queue][C_STL_queue]  
> [C++ STL容器适配器之priority\_queue][C_ STL_priority_queue]

### stack的使用 ###

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th>函数名称</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>stack()&nbsp;</td> 
   <td>构造空的栈</td> 
  </tr> 
  <tr> 
   <td>empty()&nbsp;</td> 
   <td>检测stack是否为空</td> 
  </tr> 
  <tr> 
   <td>size()&nbsp;</td> 
   <td>返回stack中元素的个数</td> 
  </tr> 
  <tr> 
   <td>top()</td> 
   <td>返回栈顶元素的引用</td> 
  </tr> 
  <tr> 
   <td>push()</td> 
   <td>将元素val压入stack中</td> 
  </tr> 
  <tr> 
   <td>pop()&nbsp;</td> 
   <td>将stack中栈顶的元素弹出</td> 
  </tr> 
 </tbody> 
</table>

### stack模拟实现 ###

mystack.h

#pragma once
    #include<deque>
    using namespace std;
    template<class T, class Con = deque<T>>
    class mystack {
    	Con s;
    public:
    	mystack() {
    
    	}
    
    	void push(const T& val) {
    		s.push_back(val);
    	}
    	void pop() {
    		s.pop_back();
    	}
    	T& top() {
    		return s.back();
    	}
    	int size() {
    		return s.size();
    	}
    	bool empty() {
    		return s.empty();
    	}
    };

测试入口main.cpp

#include<iostream>
    #include<stack>
    #include<deque>
    #include<list>
    #include<vector>
    #include"mystack.h"
    using namespace std;
    
    void Test_stack() {
    	cout << "STL中的stack\n";
    	stack<int, deque<int>> s;
    	for (int i = 1; i <= 5; ++i) {
    		s.push(i);
    	}
    	cout << "size = " << s.size() << endl;
    	while (!s.empty()) {
    		cout << s.top() << endl;
    		s.pop();
    	}
    	cout << "size = " << s.size() << endl;
    }
    void Test_mystack() {
    	cout << "自己实现的的stack\n";
    	mystack<int> s;
    	//mystack<int, list<int>> s;
    	//mystack<int, vector<int>> s;
    	for (int i = 1; i <= 5; ++i) {
    		s.push(i);
    	}
    	cout << "size = " << s.size() << endl;
    	while (!s.empty()) {
    		cout << s.top() << endl;
    		s.pop();
    	}
    	cout << "size = " << s.size() << endl;
    }
    int main() {
    	Test_stack();
    	Test_mystack();
    	system("pause");
    	return 0;
    }

运行结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly90aW1nc2EuYmFpZHUuY29tL3RpbWc_aW1hZ2UmcXVhbGl0eT04MCZzaXplPWI5OTk5XzEwMDAwJnNlYz0xNTcxMTYxNTIyMTczJmRpPTg2NzUzYzk3MDY2OTczODBlYTAxZDQyMzM3MGVjN2M2JmltZ3R5cGU9MCZzcmM9aHR0cCUzQSUyRiUyRnd3dy50LWppYWp1LmNvbSUyRnR1ampKREV3TG1Gc2FXTmtiaTVqYjIwdmFUSXZOamd3TlRrMk5qazFMMVJDTWpoWFVqQmhNMUpyY0hWR2Fua3hlbVZZV0dNdU5rWllZVjhoSVRZNE1EVTVOalk1TlNRNS5qcGc?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: /images/20230531/17d55c46c28249da9bdb2390f7f4dbf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: /images/20230531/9d9b0aab28264ab2844f7cdb5d608fcc.png
[C_STL_queue]: https://blog.csdn.net/qq_41071068/article/details/102577283#%C2%A0queue
[C_ STL_priority_queue]: https://blog.csdn.net/qq_41071068/article/details/102581747#priority_queue
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2]: /images/20230531/9e81f28b125e473e860aad09c1adf100.png