C++ STL之 queue和deque用法详解

queue<数据类型，容器类型> q;

数据类型：可以是int、double等基本类型，也可以是自定义的结构体。
容器类型：一般为deque或者list（双向链表），可省略，省略时以deque为默认容器。

声明代码如下：

queue q;  //使用默认的双端队列为底层容器创建一个空的queue队列对象q，数据元素为int类型。
queue q[20];  //规定队列元素数量
queue> q1;
queue> q2(q1);

只能队尾插入，队首弹出。无法index遍历，也不可以迭代器遍历

q.push(x);      //入队，将元素 x 从队尾插入（尾插法）
q.pop();        //出队，删除对首元素，并返回其值
q.size();       //返回队中元素个数
q.front();      //返回队首元素
q.back();       //返回队尾元素
q.empty();      //判断是否为空（空返回 1，非空返回 0）

queue q1;
q1.push(1); //队尾插入
q1.push(2); //队尾插入
q1.push(3); //队尾插入
cout << q1.size() << " " << q1.front() << " " << q1.back() << endl;
q1.pop(); //队首弹出
cout << q1.size() << " " << q1.front() << " " << q1.back() << endl;

 empty()函数可以判断队列是否为空，但无法使用clear清空。queue有swap函数

queue q2;
if (q1.empty()) {
cout << “q1 is empty” << endl;
}
q1.swap(q2);
if (q1.empty()) {
cout << “q1 is empty after swap” << endl;
}

优先队列是一种会按照默认或自定义的优先级进行自动排序的队列，其特点是优先级高的元素排在队首，低的排在队尾。头文件#include< queue > 中提供了两种可直接引用的优先规则（排序规则）：greater、less；其中，less是默认优先规则，表示数字大的优先级大（字符型用ASCLL码比较），放在队首；greater表示数字小的优先级大，放在队首。

创建priority_queue对象：

//priority_queue< 数据类型，容器类型，优先规则> pq;

 声明代码如下：

priority_queue pq;
priority_queue,less > pq;   //以less为排列规则（大顶堆，表示顶堆元素比其他都大）
priority_queue,greater > pq; //以greater为排列规则（小顶堆，表示顶堆元素比其他都小）

基本操作

pq.push();    //入队
pq.pop();     //出队
pq.size()     //返回当前对中元素个数
pq.top();     //优先队列   取队首元素
pq.empty();   //判断是否为空（空返回 1，非空返回 0）

     可以队首和队尾插入，也可以队首和队尾弹出，支持随机访问，即可以直接用下标来访问元素。它和vector有点像，因为它可以index索引和at()函数索引，当然，也可以迭代器索引。此外，它可以进行指定尺寸的构造-queue就不可以指定尺寸构造。

#include
#include
 
using namespace std;
 
int main()
{
	deque q1;
	deque q2(6,8);
	deque q3(q2.begin() + 2, q2.end());
	deque q4(q2);
	for (auto &i : q1)
	{
		cout << i << " ";
	}
	cout << endl;
	for (auto &i : q2)
	{
		cout << i << " ";
	}
	cout << endl;
	for (auto &i : q3)
	{
		cout << i << " ";
	}
	cout << endl;
	for (auto &i : q4)
	{
		cout << i << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

deque常用的操作函数

1. assign(beg, end);  //将[beg,end)区间中的数据拷贝赋值给本身。
2. assign(n,elem); //将n个elem拷贝赋值给本身。
3. empty(); //判断容器是否为空
4. size(); //返回容器中的元素的个数
5. resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
                      //如果容器变短，则末尾超出容器长度的元素被删除。
6. resize(num,elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
                           //如果容器变短，则末尾超出容器长度的元素被删除。
7. push_back(elem);  //在容器尾部添加一个数据
8. push_front(elem);  //在容器头部插入一个数据
9. pop_back();  //删除容器最后一个数据
10. pop_front();  //删除容器第一个数据
11. insert(pos,elem);  //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
12. insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值
13. insert(pos,beg,end);  //在pos位置插入[beg,end)区间的数据，无返回值
14. clear();  //清空容器的所有数据
15. erase(beg,end);  //删除[beg,end)区间的数据，返回下一个数据的位置。
16. erase(pos); //删除pos位置的数据，返回下一个数据的位置。
17. at(int idx); //返回索引idx所指的数据
18. operator[]; //返回索引idx所指的数据
19. front(); //返回容器中第一个数据元素
20. back(); //返回容器中最后一个数据元素

插入和删除

#include 
#include  

using namespace std;


void printDeuque(const deque& d) 
{
    for (deque::const_iterator it = d.begin(); it != d.end(); it++)  //表示只读迭代器
    {
        cout << *it << " ";
    }
    cout << endl;
}

void test04()
{
    deque d1; 
    
    //尾插
    d1.push_back(10);
    d1.push_back(20);

    //头插
    d1.push_front(100);
    d1.push_front(200);
    
    printDeuque(d1);

    //尾删
    d1.pop_back();
    printDeuque(d1);

    //头删
    d1.pop_front();
    printDeuque(d1);
}

void test05()
{
    deque d2;
    d2.push_back(10);
    d2.push_back(20);
    d2.push_front(100);
    d2.push_front(200);

    printDeuque(d2);

    d2.insert(d2.begin(), 1000);
    printDeuque(d2);

    d2.insert(d2.begin(), 2, 9999);
    printDeuque(d2);

    deque d3;
    d3.push_back(1);
    d3.push_back(2);
    d3.push_front(3);

    d3.insert(d3.begin(), d2.begin(), d2.end()); //在d3.begin()的位置，插入区间d2.begin()-d2.end()之间的数
    printDeuque(d3);

}

void test06()
{
    deque d1;
    d1.push_back(10);
    d1.push_back(20);
    d1.push_front(100);
    d1.push_front(200);

    //删除
    deque::iterator it = d1.begin();
    it++;//第二个元素
    d1.erase(it); //d1.erase()为删除所有;d1.clear()也为清空容器所有数据
    printDeuque(d1);

    //按区间方式删除
    d1.erase(d1.begin(), d1.end());
    printDeuque(d1);

}

int main()
{
    test04();
    test05();
    test06();

    return 0;
}

运行结果为：

遍历

#include
#include
using namespace std;

//用下标遍历队列
void showdeque1(deque& d) {
	for (int i = 0; i < d.size(); i++) cout << d[i] << " ";
	cout << endl;
}
//用迭代器迭代队列
void showdeque2(deque& d) {
	for (deque::iterator it = d.begin(); it != d.end(); it++) 
    {cout << *it << " ";}
	cout << endl;
}
int main()
{
	deque d; //初始化一个双端队列
	for (int i = 1; i <= 5; i++) d.push_back(i);//遍历双端队列
	cout << "初始队列:"; //从尾部插入元素[1,2,3,4,5],会不断扩张队列
	showdeque1(d);

	d.push_front(6);
	d.push_front(7);//从头部插入元素

	//用迭代器迭代队列
	cout << "在头部插入6,7后的队列:";
	showdeque2(d);

	//在双端队列的头部删除元素
	d.pop_front();
	cout << "删除一个头部元素后:";
	showdeque1(d);

	//在双端队列的尾部删除元素
	d.pop_back();
	cout << "删除一个尾部元素后:";
	showdeque1(d);

	//从中间插入元素
	d.insert(d.begin() + 1, 100);
	cout << "在开头的第二个位置插入元素100:";
	showdeque1(d);

	//删除中间元素
	d.erase(d.end() - 2);
	cout << "删除倒数第二个元素:";
	showdeque1(d);

	cout << "size = " << d.size() << endl;
	//重新指定大小,容量增加默认值为0
	d.resize(6);
	cout << "扩容到size = 6 :";
	showdeque1(d);
	cout << "减少容量到size = 2:";
	d.resize(2); showdeque1(d);
	d.clear();
	cout << "清除容器后empty?" << d.empty() << endl;

	system("pause");
	return 0;
}

//程序输出

赋值

#include 
#include  

using namespace std;

//deque容器 赋值操作

void printDeuque(const deque& d) 
{
    for (deque::const_iterator it = d.begin(); it != d.end(); it++)  //表示只读迭代器
    {
        cout << *it << " ";
    }
    cout << endl;
}

void test02()
{
    deque d1; 

    for (int i = 0; i < 10; i++)
    {
        d1.push_back(i);
    }
    printDeuque(d1);

    //operator= 赋值
    deque d2;
    d2 = d1;       //operator= 重载“="赋值
    printDeuque(d2);

    deque d3;
    d3.assign(d1.begin(), d1.end());//assign 赋值
    printDeuque(d3);
    
    deque d4(10,100);
    printDeuque(d4);

    deque d5
    d5.assign(10,100);
    printDeuque(d5);
}

int main()
{
    test02();
    
    return 0;
}

 对deque中的数据的存取操作

除了用迭代器获取deque容器中元素，[]和at也可以

#include 
#include  

using namespace std;


void printDeuque(const deque&d) 
{
    for (deque::const_iterator it = d.begin(); it != d.end(); it++)  //表示只读迭代器
    {
        cout << *it << " ";
    }
    cout << endl;
}

void test07()
{
    deque d1; 

    d1.push_back(10);
    d1.push_back(20);
    d1.push_back(30);

    d1.push_front(100);
    d1.push_front(200);
    d1.push_front(300);

    //通过[]方式访问元素
    for (int i = 0; i < d1.size(); i++)
    {
        cout << d1[i] << " ";
    }
    cout << endl;
    
    //通过at方式访问元素
    for (int i = 0; i < d1.size(); i++)
    {
        cout << d1.at(i) << " ";
    }
    cout << endl;
    
    cout << "第一个元素为：" << d1.front() << endl;
    cout << "最后一个元素为：" << d1.back() << endl;
}

int main()
{
    test07();

    return 0;
}

利用算法实现对deque容器进行排序

sort(iterator beg, iterator end)  //对beg和end区间内元素进行排序

 sort使用时包含头文件algorithm即可。

#include 
#include  
#include   //标准算法头文件

using namespace std;


void printDeuque(const deque&d) 
{
    for (deque::const_iterator it = d.begin(); it != d.end(); it++)  //表示只读迭代器
    {
        cout << *it << " ";
    }
    cout << endl;
}

void test08()
{
    dequed1; 
 
    d1.push_back(10);
    d1.push_back(20);
    d1.push_back(30);

    d1.push_front(100);
    d1.push_front(200);
    d1.push_front(300);

    printDeuque(d1);

    //排序  默认排序规则  从小到大 升序
    //对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序
    //vector容器也可以利用sort进行排序
    sort(d1.begin(), d1.end());
    cout << "排序后：" << endl;
    printDeuque(d1);
}


int main()
{
    test08();

    return 0;
}

deque也有swap函数 要求也必须是同一种类型

2.3 deque与vector区别：

1. vector对于头部的插入效率低，数据量越大，效率越低，例如头部后有十万个数据，则往头部插入一个数据时，十万个数据都需要往后挪一挪才能在头部插入数据。deque相对而言，对头部的插入删除速度会比vector快。
2. vector访问元素时的速度会比deque快，这和两者内部实现有关。

3.  deque提供了一些与vector相似的功能，但deque在头部和尾部进行数据插入和删除操作更加效。与vector不同的是，deque不能保证所有的元素存储在连续的空间中，在deque中通过指针加量方式访问元素可能会导致非法的操作

   vector使用使用动态数组，该数组通常需要动态增长；deque中的元素可能分散在不同的存储块中，在deque中保存一些必要的信息，通常用来在常数范围内直接访问deque中的任何一个元素，所以deque的内部实现vector复杂，但是这些额外信息使得dque在某些情况下增长更加的高效，特别是在序列比较大，重新配成本比较高的情况下。
   除了在频繁在头部或尾部进行插入和删除操作外，deque比list和forward_list的性能更差。

4. deque内部工作原理：

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。为了管理这些连续空间，deque 容器用数组存储着各个连续空间的首地址。也就是说，数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间。

通过建立数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque的头部或尾部。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”的假象，落在了deque的迭代器身上

由于 deque 容器底层将序列中的元素分别存储到了不同段的连续空间中，因此要想实现迭代器的功能，必须先解决如下 2 个问题：

①迭代器在遍历 deque 容器时，必须能够确认各个连续空间在数组中的位置；
②迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中。

迭代器内部包含 4 个指针，它们各自的作用为：