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

曾经终败给现在 2023-06-08 03:20 2阅读 0赞

**目录**

适配器

queue

queue的使用

queue的模拟实现

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

### 适配器  ###

> 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，适配器是将一个类的接口转换成客户希望的另外一个接口。
> 
> 举个栗子, 咱们香港的插头和我们内地是不一的, 如下图, 这种插头在咱们内地是不方便使用的, 要是香港同胞到对岸深圳转一转, 被繁华的深圳所吸引, 不禁多留了两天, 那这时候手机要充电怎么充电啊, 不过没关系, 我们有适配器, 其实真正给手机充电的还是手机充电器, 适配器只是方便了人们的使用而已 . ![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实现

###  queue ###

> 1. 队列是一种容器适配器，专门用于在(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。  
> 2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。  
> 3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。**该底层容器应至少支持**以下操作:
> 
> empty：检测队列是否为空  
> size：返回队列中有效元素的个数  
> front：返回队头元素的引用  
> back：返回队尾元素的引用  
> push\_back：在队列尾部入队列  
> pop\_front：在队列头部出队列  
> 4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有实例化指定容器，则使用标准容器deque。  
> 5. 需要头文件\#include<queue>  
> 6. 为什么选择deque作为queue的底层默认容器  
> 主要原因  
> deque优点: 两端插入删除最快的  
> deque缺点: 迭代器复杂效率低  
> queue利用了优点规避了缺点, 在两端插删, 且并未使用迭代器, 所以deque最优
> 
> queue图示 :  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]
> 
> [C++STL容器适配器之stack][C_STL_stack]  
> [C++ STL容器适配器之priority\_queue][C_ STL_priority_queue]

### queue的使用 ###

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th>函数名称</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>queue()</td> 
   <td>构造空的队列</td> 
  </tr> 
  <tr> 
   <td>empty()</td> 
   <td>检测队列是否为空，是返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回队列中有效元素的个数</td> 
  </tr> 
  <tr> 
   <td>back()</td> 
   <td>返回队尾元素的引用</td> 
  </tr> 
  <tr> 
   <td>front()</td> 
   <td>返回队头元素的引用</td> 
  </tr> 
  <tr> 
   <td>push()</td> 
   <td>在队尾将元素val入队列</td> 
  </tr> 
  <tr> 
   <td>pop()</td> 
   <td>将队头元素出队列</td> 
  </tr> 
 </tbody> 
</table>

### queue的模拟实现 ###

myqueue.h

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

测试入口main.cpp

#include<iostream>
    #include<deque>
    #include<queue>
    #include<list>
    #include"myqueue.h"
    using namespace std;
    
    void Test_queue() {
    	cout << "STL中的queue\n";
    	queue<int, deque<int>> qu;
    	for (int i = 1; i <= 5; ++i) {
    		qu.push(i);
    	}
    	cout << "size = " << qu.size() << endl;
    	cout << qu.back() << endl;
    	while (!qu.empty()) {
    		cout << qu.front() << endl;
    		qu.pop();
    	}
    	cout << "size = " << qu.size() << endl;
    }
    void Test_myqueue() {
    	cout << "自己实现的的queue\n";
    	myqueue<int> qu;
    	//myqueue<int, list<int>> qu;
    	for (int i = 1; i <= 5; ++i) {
    		qu.push(i);
    	}
    	cout << "size = " << qu.size() << endl;
    	cout << qu.back() << endl;
    	while (!qu.empty()) {
    		cout << qu.front() << endl;
    		qu.pop();
    	}
    	cout << "size = " << qu.size() << endl;
    }
    int main() {
    	Test_queue();
    	Test_myqueue();
    	system("pause");
    	return 0;
    }

运行结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: /images/20230531/54d587e9a15c4b4cadc88bc095809cfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: /images/20230531/867cc2de73694f9cb03a9ccbcb2de75d.png
[C_STL_stack]: https://blog.csdn.net/qq_41071068/article/details/102576720#stack
[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/4523b74553f2464fac6e0d14ec01475b.png