deque 订阅
deque(double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,相比list增加[]运算符重载。 展开全文
deque(double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,相比list增加[]运算符重载。
信息
全    名
double-ended queue
类    型
具有队列和栈的性质的数据结构
中文名
双端队列
外文名
deque
deque基本含义
deque (double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样,可以用一个铁道转轨网络来比喻双端队列。在实际使用中,还可以有输出受限的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列)和输入受限的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列)。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻的栈了。
收起全文
精华内容
下载资源
问答
  • deque

    2020-03-30 15:04:37
    文章目录1 deque简介2 deque的常用用法2.1 deque对象的默认构造2.2 deque对象的带参数构造2.3 deque头部和末尾的添加移除操作2.4 deque的数据存取2.5 deque与迭代器2.6 deque的赋值2.7 deque的大小2.8 deque的插入...

    1 deque简介

    deque容器概念:

    • deque是“double-ended queue”的缩写,和vector一样都是STL的容器,唯一不同的是:deque是双端数组,而vector是单端的。

    在这里插入图片描述
    Deque 特点:

    • deque在接口上和vector非常相似,在许多操作的地方可以直接替换。
    • deque可以随机存取元素(支持索引值直接存取,用[]操作符或at()方法)。
    • deque头部和尾部添加或移除元素都非常快速, 但是在中部安插元素或移除元素比较费时。

    使用时,包含头文件:#include <deque>


    2 deque的常用用法

    2.1 deque对象的默认构造

    deque也是采用模板类实现。
    deque对象的默认构造形式:deque<T> deqT

    例如:

    deque <int> deqInt;            //存放int的deque容器。
    deque <float> deqFloat;         //存放float的deque容器。
    deque <student> deqStu;        //存放student的deque容器。
    

    注意:尖括号内还可以设置指针类型或自定义类型。

    2.2 deque对象的带参数构造

    方式1:deque(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
    方式2:deque(n,elem); //构造函数将n个elem拷贝给本身。
    方式3:deque(const deque &deq); //拷贝构造函数。

    deque<int> deqIntA;
    deqIntA.push_back(1);
    deqIntA.push_back(2);
    deqIntA.push_back(3);
    deqIntA.push_back(4);
    
    deque<int> deqIntB(deqIntA.begin(),deqIntA.end());		//1 2 3 4 
    deque<int> deqIntC(8, 666);							//8 8 8 8 8
    deque<int> deqIntD(deqIntA);						//1 2 3 4
    

    2.3 deque头部和末尾的添加移除操作

    如下:
    deque.push_back(element); //容器尾部添加一个数据
    deque.push_front(element); //容器头部插入一个数据
    deque.pop_back(); //删除容器最后一个数据
    deque.pop_front(); //删除容器第一个数据

    deque<int> deqIntA;
    deqIntA.push_back(1);
    deqIntA.push_back(2);
    deqIntA.push_back(3);
    deqIntA.push_back(4);
    deqIntA.push_back(5);
    deqIntA.push_back(6);
    deqIntA.pop_front();
    deqIntA.pop_front();
    deqIntA.push_front(7);
    deqIntA.push_front(8);
    deqIntA.pop_back();
    deqIntA.pop_back();
    //deqIntA 中剩余元素: 8 7 3 4 
    

    2.4 deque的数据存取

    第一:使用下标操作 deqIntA[0] = 100;
    第二:使用at 方法 如: deqIntA.at(2) = 100;
    第三:接口返回的引用 deqIntA.front() 和 deqIntA.back() 。
    注意: 第一和第二种方式必须注意越界!

    例如:

    deque<int> deqIntA;
    deqIntA.push_back(1);
    deqIntA.push_back(2);
    deqIntA.push_back(3);
    deqIntA.push_back(4);
    deqIntA.push_back(5);
    
    int i1 = deqIntA.at(0);		//i1 = 1
    int i2 = deqIntA[1];			//i2 = 2
    deqIntA.at(0) = 666;		//第一个元素改成666
    deqIntA[1] = 888;			//第二个元素改成888
    
    int iFront = deqInt.front();	//666
    int iBack = deqInt.back();	//5
    deqInt.front() = 888;			//第一个元素改成  888
    deqInt.back() = 666;			//最后一个元素改成 666
    

    2.5 deque与迭代器

    主要有如下迭代器:

    • deque.begin(); //返回容器中第一个元素的迭代器。
    • deque.end(); //返回容器中最后一个元素之后的迭代器。
    • deque.rbegin(); //返回容器中倒数第一个元素的迭代器。
    • deque.rend(); //返回容器中倒数最后一个元素之后的迭代器。
    • deque.cbegin(); //返回容器中第一个元素的常量迭代器。
    • deque.cend(); //返回容器中最后一个元素之后的常量迭代器。
    eque<int> deqIntA;
    deqIntA.push_back(1);
    deqIntA.push_back(2);
    deqIntA.push_back(3);
    deqIntA.push_back(4);
    deqIntA.push_back(5);
    
    //普通迭代器
    for(deque<int>::iterator it = deqIntA.begin(); it!=deqIntA.end(); ++it){
    	(*it)++;  //*it++  (*it)++
    	cout<<*it;
    	cout<<" ";
    }
    
    //常量迭代器
    deque<int>::const_iterator cit = deqIntA.cbegin();
    for( ; cit!=deqIntA.cend(); cit++){
    	cout<<*cit;
    	cout<<" ";
    }
    
    //逆转的迭代器
    for(deque<int>::reverse_iterator rit=deqIntA.rbegin(); rit!=deqIntA.rend(); ++rit){
    	cout<<*rit;
    	cout<<" ";
    }
    

    2.6 deque的赋值

    如下:

    • deque.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
    • deque.assign(n,elem); //将n个elem拷贝赋值给本身。
    • deque& operator=(const deque &deq); //重载等号操作符
    • deque.swap(deq); // 将deque与本身的元素互换

    例如:

    deque<int> deqIntA,deqIntB,deqIntC,deqIntD;
    deque<int> deqIntA;
    deqIntA.push_back(1);
    deqIntA.push_back(2);
    deqIntA.push_back(3);
    deqIntA.push_back(4);
    deqIntA.push_back(5);
    
    
    deqIntB.assign(deqIntA.begin(),deqIntA.end());	// 1 2 3 4 5 
    		
    deqIntC.assign(4,888);						//888 888 888 888 
    
    deqIntD = deqIntA;							//1 2 3 4 5 
    
    deqIntC.swap(deqIntD);						//互换
    

    2.7 deque的大小

    如:

    • deque.size(); //返回容器中元素的个数
    • deque.empty(); //判断容器是否为空
    • deque.resize(num); //重新指定容器的长度为num,若容器变长,则以默认值0填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
    • deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
    deque<int> deqIntA;
    deqIntA.push_back(1);
    deqIntA.push_back(2);
    deqIntA.push_back(3);
    deqIntA.push_back(4);
    deqIntA.push_back(5);
    
    
    int iSize = deqIntA.size();  //5
    
    deqIntA.resize(7);		//1 2 3 4 5 0 0 
    deqIntA.resize(8,1);		//1 2 3 4 5 0 0 1
    deqIntA.resize(2);		//1 2
    

    2.8 deque的插入

    如下:

    • deque.insert(pos,elem); //在pos位置插入一个elem元素的拷贝,返回新数据 的位置。
    • deque.insert(pos,n,elem); //在pos位置插入n个elem数据,无返回值。
    • deque.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据,无返回值。
    // demo 15-30
    #include <deque>
    #include <iostream>
    
    using namespace std;
    
    int main(void){
    	deque<int> deqIntA;
    	deque<int> deqIntB;
    
    	deqIntA.push_back(1);
    	deqIntA.push_back(2);
    	deqIntA.push_back(3);
    	deqIntA.push_back(4);
    
    	deqIntB.push_back(11);
    	deqIntB.push_back(12);
    	deqIntB.push_back(13);
    	deqIntB.push_back(14);
    
    	deqIntA.insert(deqIntA.begin(), 0); // {0,1,2,3,4}
    	deqIntA.insert(deqIntA.begin()+1, 2, 88);  //{0,88,88,1,2,3,4}
    
    	deqIntA.insert(deqIntA.begin(), deqIntB.rbegin(), deqIntB.rend());{11,12,13,14,0,88,88,1,2,3,4}
    
    	for(deque<int>::iterator it = deqIntA.begin(); it!=deqIntA.end(); ++it){
    		cout<<*it;
    		cout<<" ";
    	}
    	system("pause");
    }
    

    2.9 deque的删除

    如下:

    • deque.clear(); //移除容器的所有数据
    • deque.erase(beg,end); //删除[beg,end)区间的数据,返回下一个数据的位置。
    • deque.erase(pos); //删除pos位置的数据,返回下一个数据的位置。
    // demo 15-30-2
    #include <deque>
    #include <iostream>
    
    using namespace std;
    
    int main(void){
    	deque<int> deqIntA;
    	
    	deqIntA.push_back(1);
    	deqIntA.push_back(2);
    	deqIntA.push_back(3);
    	deqIntA.push_back(4);
    	deqIntA.push_back(5);
    
    	//方式一 单独使用擦除的接口
    	//deqIntA.erase(deqIntA.begin()+1); //干掉第二个元素 {1,3,4,5}
    
    	//deqIntA.erase(deqIntA.begin()+1, deqIntA.begin()+3);// 干掉3 和4, 剩下{1, 5}
    
    	//deqIntA.clear(); //干掉所有的元素
    
    	//方式二 使用迭代器遍历删除
    	for(deque<int>::iterator it = deqIntA.begin(); it!=deqIntA.end();){
    		if(*it == 4){
    			it = deqIntA.erase(it);
    		}else {
    			cout<<*it;
    			cout<<" ";
    			it++;
    		}
    	}
    
    	system("pause");
    }
    

    参考资料:

    1. C/C++从入门到精通-高级程序员之路【奇牛学院】
    展开全文
  • Deque

    2021-03-16 19:35:32
    Queue继承collection接口,Deque继承Queue接口。 实现Deque接口的类有ArrayDeque和LinkedList. ArrayDeque底层实现了一个循环数组,其中queue方法由Deque方法实现。队列为尾增头删,栈为头增头删。 LinkedLink底层时...

    Queue继承collection接口,Deque继承Queue接口。
    实现Deque接口的类有ArrayDeque和LinkedList.
    ArrayDeque底层实现了一个循环数组,其中queue方法由Deque方法实现。队列为尾增头删,栈为头增头删。
    LinkedLink底层时一个双链表,其中queue方法由Deque方法实现。队列为尾增头删,栈为头增头删。

    展开全文
  • Deque

    2017-11-06 14:39:31
    The teacher gave Alice a sequence of number(named A) and a deque. The sequence exactly contains N integers. A deque is such a queue, that one is able to push or pop the element at its front end or ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 127,712
精华内容 51,084
关键字:

deque