C++基础：STL之双向队列deque

╰+攻爆jí腚メ 2022-12-18 03:55 224阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
这篇文章介绍一下STL中队列deque的基本使用方法。

### 目录 ###

*  双向队列deque
 *  头文件和命名空间
 *  常用的成员函数
 *  代码使用示例
 *  示例执行结果
 *  总结

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

# 双向队列deque #

> 双向队列也是队列，是最为常见的一种数据结构，双向队列在STL中有deque的实现。包含双向队列在内，队列中的元素满足FIFO（先进先出）。主要特点如下：

*  元素需满足FIFO：First In First Out
 *  出口端称为队头（Front），入口端称为队尾（Rear）
 *  可以使用数组或者链表来存储数据
 *  操作主要有入队（Enqueue）和出队（Dequeue）
 *  可以根据需要实现循环队列或者双向队列
 *  只能在队尾插入数据，在队头删除数据
 *  关于队列的说明内容可参看：[https://blog.csdn.net/liumiaocn/article/details/108091698][https_blog.csdn.net_liumiaocn_article_details_108091698]

# 头文件和命名空间 #

> \#include <deque>  
> using namespace std;

# 常用的成员函数 #

<table> 
 <thead> 
  <tr> 
   <th>queue函数名</th> 
   <th>用途</th> 
   <th>功能说明</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>查询遍历</td> 
   <td>获取元素个数</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>begin()</td> 
   <td>查询遍历</td> 
   <td>获取指向第一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>end()</td> 
   <td>查询遍历</td> 
   <td>获取指向最后一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>front()</td> 
   <td>查询遍历</td> 
   <td>获取指向第一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>back()</td> 
   <td>查询遍历</td> 
   <td>获取指向最后已给元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>push_back</td> 
   <td>插入</td> 
   <td>在末尾插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop_back</td> 
   <td>删除</td> 
   <td>删除最后一个元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>push_front</td> 
   <td>插入</td> 
   <td>在末尾插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop_front</td> 
   <td>删除</td> 
   <td>删除最后一个元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>删除</td> 
   <td>删除所有元素</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

> 注：deque的成员函数主要包括插入和删除，实际对应着队列操作的入队和出队两个操作，然后就是获取元素个数和对头元素的操作，都是负载度为O (1)的操作。和stack相比，上述5个函数的函数名只是front和top有区别，其他函数名一致。

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

# 代码使用示例 #

#include <iostream>
    #include <deque>
    using namespace std;
    
    void print_element(deque <char> q) {
        if (!q.empty()) {
            cout << "Size:" << q.size() << " Queue Top Element : " << q.back()  << " Queue:";
        } else {
            cout << "Size:" << q.size() << endl;
        }
    
        deque<char>::iterator it = q.begin();
        while(it != q.end()) cout << *it++;
        cout << endl;
    }
    
    int main() {
        deque <char> q;
    
        cout << "Queue Element In " << endl;
        print_element(q);
        q.push_back('L');
        print_element(q);
        q.push_back('i');
        print_element(q);
        q.push_back('u');
        print_element(q);
    
        cout << endl << "Queue Element Out " << endl;
        q.pop_back();
        print_element(q);
        q.pop_back();
        print_element(q);
        q.clear();
        print_element(q);
    
        q.push_back('i');
        print_element(q);
        q.push_front('L');
        print_element(q);
        q.push_back('u');
        print_element(q);
        q.pop_back();
        print_element(q);
        q.pop_front();
        print_element(q);
        q.pop_front();
        print_element(q);
    }

# 示例执行结果 #

Queue Element In 
    Size:0
    
    Size:1 Queue Top Element : L Queue:L
    Size:2 Queue Top Element : i Queue:Li
    Size:3 Queue Top Element : u Queue:Liu
    
    Queue Element Out 
    Size:2 Queue Top Element : i Queue:Li
    Size:1 Queue Top Element : L Queue:L
    Size:0
    
    Size:1 Queue Top Element : i Queue:i
    Size:2 Queue Top Element : i Queue:Li
    Size:3 Queue Top Element : u Queue:Liu
    Size:2 Queue Top Element : i Queue:Li
    Size:1 Queue Top Element : i Queue:i
    Size:0

# 总结 #

变长支持、泛化类型、常用功能函数内嵌、可以使用其他多种STL的函数、使用简单，而且也支持迭代器等，都是deque被使用的原因。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/cae33158eef441a1a442b288d5b0c0e6.png
[https_blog.csdn.net_liumiaocn_article_details_108091698]: https://blog.csdn.net/liumiaocn/article/details/108091698