简介:
deque双端队列容器(double-ended queue)与vector非常相似,算法的时间复杂度也是常数阶O(1),deque内部的数据机制和执行性能与vector不同,一般说来,当考虑到容器元素的内存分配策略和操作的性能时,deque相对vector较为有优势。deque双端队列采用分块的线性结构来存储数据,具有高效的删除首尾元素的函数,由于deque容器是以deque块为单位进行内存的分配,并使用了二级的Map进行管理,因此不容易实现类似于vector的capacity和reverse函数,而且deque容器也不需要这样的获取和调整容器大小的函数。
deque应用基础:
创建deque对象:
1、deque() 创建一个空的deque对象。
如:deque<int> d;
2、deque(size_type n) 创建一个具有n个元素的deque对象,每个deque元素具有它的类型下的默认值。
如:deque<int> d(10);
3、deque(size_type n, const T& value) 创建一个具有n个元素的deque对象,每个元素具有初始值value。
如:deque<int> d(10, 5);
4、deque(const deque&) 通过拷贝一个deque对象的各个元素值,创建一个新的deque对象。
如:deque<int> d1(10, 5); deque<int> d2(d1);
5、deque(const InputIterator first, const InputIterator last, const A& a=A()) 通过拷贝迭代器区间[first, last)的元素值,创建一个新的deque对象中,内存分配器可省略。
如:int iArray[] = {1,2,3}; deque<int> d(iArray, iArray+3);
初始化赋值:
deque提供的push_back函数常用来进行deque容器的初始化,push_back函数在容器的尾端插入新元素value。
void push_back(const T&)
元素的遍历访问:
deque的元素可采用数组或迭代器的方式进行遍历访问。
元素的插入:
由于deque使用了两个迭代器分别指向双端队列的首尾,因此deque具有高效的头部插入元素的函数push_front()
void push_front(const T&)
其它位置的插入,将涉及相关元素的移位拷贝,insert函数的一个较常用的原型为:
iterator insert(iterator pos, const T& x)
元素的删除:
void pop_front() 删除deque的第一个元素
void pop_back() 删除deque的最后一个元素
iterator erase(iterator pos) 删除迭代器pos所指的元素
iterator erase(iterator first, iterator last) 删除迭代器区间[first, last)的所有元素
void clear() 调用erase函数,清除所有元素
元素的反向遍历:
reverse_iterator rbegin()
reverse_iterator rend()
deque的交换:
void swap(deque&)
其它常用函数:
bool empty()
size_type size()
size_type max_size()
reference front()
reference back()
举例分析:
1、
//用数组的方式访问deque元素
#include <iostream>
#include <deque>
using namespace std;
int main(void)
{
deque<int> d;
d.push_back(13);
d.push_back(32);
d.push_back(29);
for (int i=0; i<d.size(); i++)
{
cout << "d[" << i << "] = " << d[i] << endl;
}
return 0;
}
2、
//用迭代器访问deque元素
#include <deque>
#include <iostream>
using namespace std;
int main(void)
{
deque<string> d;
d.push_back("a");
d.push_back("b");
d.push_back("c");
deque<string>::iterator i, iend;
iend = d.end();
int j;
for (i=d.begin(),j=0; i!=iend; i++,j++)
{
cout << *i << " ";
}
cout << endl;
return 0;
}
3、
//头部和中间位置插入deque元素
#include <deque>
#include <iostream>
using namespace std;
int main(void)
{
deque<int> d;
d.push_back(6);
d.push_back(7);
//头部插入
d.push_front(5);
for (int i=0; i<d.size(); i++)
{
cout << d[i] << " ";
}
cout << endl;
//中间位置插入
d.insert(d.begin()+1, 9);
for (int j=0; j<d.size(); j++)
{
cout << d[j] << ' ';
}
cout << endl;
return 0;
}
4、
//头尾和其它位置删除deque元素
#include <deque>
#include <iostream>
using namespace std;
int main(void)
{
deque<int> d;
d.push_back(4);
d.push_back(5);
d.push_back(3);
d.push_back(3);
d.push_back(3);
d.push_back(6);
for (int i=0; i<d.size(); i++)
{
cout << d[i] << ' ' ;
}
cout << endl;
//头尾和任意位置删除元素
d.erase(d.begin()+1);
d.pop_front();
d.pop_back();
for (int j=0; j<d.size(); j++)
{
cout << d[j] << ' ' ;
}
cout << endl;
//删除所有元素
d.clear();
cout << "执行clear()" << endl << "deque元素全部清除" << endl;
return 0;
}
5、
//deque元素的反向遍历
#include <deque>
#include <iostream>
using namespace std;
int main(void)
{
deque<int> d;
d.push_back(1);
d.push_back(3);
d.push_back(5);
d.push_back(7);
d.push_back(9);
//deque元素的前向遍历
deque<int>::iterator i, iend;
iend = d.end();
for (i=d.begin(); i!=iend; i++)
{
cout << *i << " ";
}
cout << endl;
//deque元素的反向遍历
deque<int>::reverse_iterator ri, riend;
riend = d.rend();
for (ri=d.rbegin(); ri!=riend; ri++)
{
cout << *ri << " ";
}
cout << endl;
return 0;
}
6、
//两个deque容器的元素交换
#include <deque>
#include <iostream>
using namespace std;
void print(deque<int>& d)
{
for (int i=0; i<d.size(); i++)
{
cout << d[i] << " ";
}
cout << endl;
}
int main(void)
{
deque<int> d1;
d1.push_back(11);
d1.push_back(12);
d1.push_back(13);
cout << "d1 = ";
print(d1);
deque<int> d2;
d2.push_back(90);
d2.push_back(91);
d2.push_back(92);
cout << "d2 = ";
print(d2);
//d1和d2交换
d1.swap(d2);
cout << "d1与d2交换后" << endl;
cout << "d1 = ";
print(d1);
cout << "d2 = ";
print(d2);
return 0;
}
7、
//deque其它常用函数的使用
#include <deque>
#include <iostream>
using namespace std;
int main(void)
{
deque<string> d;
//打印deque为空
cout << "d是否为空: " << d.empty() << endl;
//装入元素
d.push_back("红楼梦");
d.push_back("源氏物语");
d.push_back("教父");
d.push_back("水浒传");
d.push_back("24史");
//打印deque所有元素
deque<string>::iterator i, iend;
iend = d.end();
for (i=d.begin(); i!=iend; i++)
{
cout << *i << " ";
}
cout << endl;
//打印首元素
cout << "deque首元素为: " << d.front() << endl;
//打印末元素
cout << "deque末元素为: " << d.back() << endl;
//打印元素个数
cout << "deque元素个数为: " << d.size() << endl;
//打印可支持的最大deque元素个数
cout << "deque最大元素个数为: " << d.max_size() << endl;
return 0;
}
相关推荐
python--双端队列deque(csdn)————程序
双端队列Deque及Python实现双端队列Deque双端队列Deque的Python实现双端队列Deque的应用:“回文词”判断 双端队列Deque 与队列类似,双端队列有两个人口,不同之处在于双端队列的两个口都既可以是入口也可以是出口...
双端队列,在基础类上派生 用来实现平移递推滤波数据存储
双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端:队首(front)、队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样...
所谓双端队列(double-ended queue,deque),就是在列表的两端都可以插入和删除数据。 因此它允许的操作有Create、IsEmpty、IsFull、Left、Right、AddLeft、AddRight、DeleteLeft、 DeleteRight。使用循环数组方式...
双端队列(deque,double-ended queue),是一种具有队列和栈的性质的数据结构。 双端队列中每一端,都可以进行存入和取出,去其中一段,都像一个栈一样。 存取也只限定在两端,不能在中间 双端队列的实现 通过...
用双端队列(deque)实现栈的功能, 数据结构作业 栈(先进后出)的一种数据结构 内含一个cpp文件和两个头文件。
双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。 双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。 操作 Deque() ...
设计循环双端队列 题目 设计实现双端队列。 请不要使用内置的双端队列库。 链接:https://leetcode-cn.com/problems/design-circular-deque/ 思路 题目要求不使用内置的双端队列库,那么可以考虑使用双指针,即队首...
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
deque结构可以看作是内置的list结构的加强版,且比队列提供了更强大的方法,下面就通过几个小例子来详解Python的collections模块中的deque双端队列结构:
riften :: Deque一种无出血边缘的无锁定单生产者多消费者,Chase-Lev工作窃取双端队列,如论文“动态圆蜗杆riften :: Deque一种无边缘的无锁定单生产者多端”中介绍的消费者,Chase-Lev的工作窃取双端队列,如“动态...
[284ko后记] 由Haim Kaplan和Robert E.Tarjan撰写ACM杂志31:11-16(1999)1709-1723... 这些双端队列的示例应用程序包括: 使用滑动窗口通过简单的Deque.tl (Deque.snoc ngram chr)枚举字符串的ngram。 如Oege de Moor
双端队列 Haskell 中类型对齐的双端队列
Projet_deque:Projet INFO0402双端队列
双端队列和随机队列 算法的双端队列和随机队列的实现I
双端队列是在队列的基础上进行改进的。关于队列的博客链接:https://blog.csdn.net/sf9898/article/details/104941655 灵魂画手,凑合着看吧 和队列的区别正如名称中所说的,双端队列可以在两端进行操作,即可以在...