欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++STL之双端队列Deque

程序员文章站 2024-02-11 23:32:58
...

deque双端队列容器与vector很类似,采用线性表顺序存储结构。但与vector区别,deque采用分块的线性存储结构来存储数据,每块的大小一般为512B,将之称为deque块,所有的deque块使用一个map块进行管理,每个map数据项记录各个deque块的首地址,这样的话,deque块在头部和尾部都可以插入和删除。而不需要移动任何元素,而不需要移动其他元素(使用push_back()方法在尾部插入元素,会扩张队列,而使用push_front()方法在首部插入元素和使用insert()方法在中间插入元素,只是将原位置上的元素进行覆盖,不会增加新元素)一般来说,当考虑到容器元素的内存分配策略和操作的性能时deque相当于vector更有优势。
C++STL之双端队列Deque
*创建deque对象
与vector类似

*插入元素
使用push_back()方法从尾部插入元素,会不断扩张队列。

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

 int main()
 {
    deque<int> d;
    d.push_back(1);
    d.push_back(2);

    cout<<d[0]<<" : "<<d[1]<<endl;

    return 0;
 }

从头部插入元素,不会增加新元素,只将原来有的元素覆盖。

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

 int main()
 {
    deque<int> d;

    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    d.push_front(10);//d.insert(d.begin()+1, 10);
    d.push_front(20);//d.insert(d.begin()+2, 20);

    cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;

    return 0;
 }
--------------------- 
作者:xiaowei_nbu 
来源:CSDN 
原文:https://blog.csdn.net/caicai_zju/article/details/49227927 
版权声明:本文为博主原创文章,转载请附上博文链接!

*遍历

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

 int main()
 {
    deque<int> d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    for(int i = 0; i < d.size(); i ++)
        cout<<d[i]<<" ";
    cout<<endl;

    deque<int>::iterator it;
    for(it = d.begin(); it != d.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    deque<int>::reverse_iterator rit;
    for(rit = d.rbegin(); rit != d.rend(); rit ++)
        cout<<*rit<<" ";
    cout<<endl;

    return 0;
 }

*删除元素
可以从双端队列的手部,尾部,中部删除元素,并可以清空双端队列容器

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

int main()
{
    deque<int> d;
    for(int i = 1; i < 6; i ++)
        d.push_back(i);

    d.pop_front();
    d.pop_front();

    deque<int>::iterator it;
    for(it = d.begin(); it != d.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    d.pop_back();
    for(it = d.begin(); it != d.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    d.erase(d.begin()+1);
    for(it = d.begin(); it != d.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    d.clear();
    cout<<d.size()<<endl;

    return 0;
}