C++中STL容器之双端队列——dequeue

1.双端队列介绍

双端队列(dequeue) 与vector很类似，采用线性表顺序存储结构，且支持随机访问，即可以直接用下标来访问元素。但与vector有区别:

deque采用分块的线性存储结构来存储数据，每块的大小一般为512B，将之称为deque块;

所有的deque块使用一个map块进行管理，每个map数据项记录各个deque块的首地址,所以允许较为快速的随机访问;

即它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪；

这样的话，deque块在头部和尾部都可以插入和删除,而不需要移动其他元素。

1.使用push_back()方法在尾部插入元素，会扩张队列;

2.使用push_front()方法在首部插入元素和使用insert()方法在中间插入元素(覆盖原有元素,不会增加新元素)。

一般来说，当考虑到容器元素的内存分配策略和操作的性能时deque相当于vector更有优势。它是vector和list的结合，复杂度处于二者之间。

复杂度

操作 复杂度

push_front() O(1)

pop_front() O(1)

push_back() O(1)

pop_back() O(1)

insert() O(n)

erase() O(n)

访问 O(1)

2.双端队列基本用法

2.1 dequeue的创建

与vector类似,deque<Type> d;

2.2 dequeue常见用法

操作 含义

a.push_back(e) 在尾部插入元素e,会不断扩张队列

a.push_front(e) 在头部插入元素e

a.pop_front() 在头部删除数据

a.pop_back() 在尾部删除数据

a.resize(num) 重新指定队列的长度

a.size() 返回容器中实际数据个数

a.max_size() //返回容器中最大数据的数量

简单测试代码:

root@fanpf:~/cpp_demos# cat deque.cpp

/****************************************************************************

@file:dequeue.cpp

@author:ebayboy@163.com

@date:2019-10-14 11:15

@version 1.0 

@description: cpp file

@Copyright (c)  all right reserved

**************************************************************************/

#include <iostream>

#include <deque>

using namespace std;

void show_deque(deque <int> d)

{

        for (deque<int>::iterator it=d.begin();

                        it != d.end(); it++) {

                cout << *it << " ";

        }

        cout << endl;

}

void show_deque2(deque <int> d)

{

        cout << __func__ << ":" << __LINE__ << endl;

        for (size_t i = 0; i < d.size(); i++) {

                cout << d[i] << " ";

        }

        cout << endl;

}

int main(int argc, char **argv)

{

        deque <int> d;

        /* push back */

        for (int i = 0; i <=5; i++) {

                d.push_back(i);

        }

        cout << endl << "push back:" << endl;

        show_deque(d);

        /* push front */

        d.push_front(6);

        d.push_front(7);

        cout << endl << "push front" << endl;

        show_deque(d);

        /* pop front */

        d.pop_front();

        cout << endl << "pop front:" << endl;

        show_deque(d);

        /* pop back */

        d.pop_back();

        cout << endl << "pop back:" << endl;

        show_deque(d);

        /* insert at pos */

        d.insert(d.begin()+ 1, 100);

        cout << endl << "insert at pos d.begin()+ 1):" << endl;

        show_deque(d);

        /* del at pos d.end() - 2 )*/

        d.erase(d.end() - 2);

        cout << endl << "del at pos - 2" << endl;

        show_deque(d);

        cout << "size:" << d.size() << endl;

        cout << "resize -> 2:" << endl;

        d.resize(2);

        show_deque(d);

        cout << "clear all:" << endl;

        d.clear();

        show_deque(d);

        return 0;

}

程序的输出：

root@fanpf:~/cpp_demos# ./deque

push back:

0 1 2 3 4 5

push front

7 6 0 1 2 3 4 5

pop front:

6 0 1 2 3 4 5

pop back:

6 0 1 2 3 4

insert at pos d.begin()+ 1):

6 100 0 1 2 3 4

del at pos - 2

6 100 0 1 2 4

size:6

resize -> 2:

6 100

clear all: