01. queue队列

1.1 队列简介

• queue队列是一种容器适配器，专门用来满足先进先出的操作，也就是元素在容器的一端插入并从另一端提取。
• 头文件为#include<queue>

1.2 队列成员函数

• bool empty() const;返回队列是否为空
• size_type size() const;返回队列元素的数量
• reference& back();返回队列中最后一个元素也即最新的元素的引用；
• reference& front();返回队列中的下一个元素也即最旧的元素的引用；
• void push(const value_type& val);在队尾插入一个元素；
• void pop();弹出队列的下一个元素也即最旧的元素,队头元素。

1.3 应用例子

• 在之前的博客中有讲

http://zfhblog.com/index.php/archives/26/

02. deque双端队列

2.1双端队列简介

• deque是一种双向开口的连续线性空间。可以在头尾两端分别做元素的插入和删除操作，当然，vector也可以在头尾两端插入元素，但是在其头部操作效率奇差。

2.2 deque构造函数

• deque<T> deqT;//默认构造形式
• deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
• deque(n, elem);//构造函数将n个elem拷贝给本身。
• deque(const deque &deq);//拷贝构造函数。

2.3 deque成员函数

• assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
• assign(n, elem);//将n个elem拷贝赋值给本身。
• deque& operator=(const deque &deq); //重载等号操作符
• swap(deq);// 将deq与本身的元素互换
• deque.size();//返回容器中元素的个数
• deque.empty();//判断容器是否为空
• deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
• deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。
• push_back(elem);//在容器尾部添加一个数据
• push_front(elem);//在容器头部插入一个数据
• pop_back();//删除容器最后一个数据
• pop_front();//删除容器第一个数据
• at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
• operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
• front();//返回第一个数据。
• back();//返回最后一个数据
• insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
• insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
• insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
• clear();//移除容器的所有数据
• erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
• erase(pos);//删除pos位置的数据，返回下一个数据的位置。

03 priority_queue优先级队列

• 就是内部排好序的队列，直接用例子说明

#include <iostream>
#include <queue>

using namespace std;

int main()
{
        priority_queue<int> p1; //默认最大优先级队列
        priority_queue<int, vector<int>, less<int>>p2; //最大优先级队列
        priority_queue<int, vector<int>, greater<int>>p3; //最小优先级队列
        p1.push(33);
        p1.push(22);
        p1.push(55);
        p1.push(11);
        cout << "测试默认优先级队列" << endl;
        while (p1.size())
        {
                cout << p1.top() << endl;
                p1.pop();
        }
        p2.push(33);
        p2.push(22);
        p2.push(55);
        p2.push(11);
        cout << "测试最大优先级队列" << endl;
        while (p2.size())
        {
                cout << p2.top() << endl;
                p2.pop();
        }
        p3.push(33);
        p3.push(22);
        p3.push(55);
        p3.push(11);
        cout << "测试最小优先级队列" << endl;
        while (p3.size())
        {
                cout << p3.top() << endl;
                p3.pop();
        }
        return 0;
}

• 结果：

测试默认优先级队列
55
33
22
11
测试最大优先级队列
55
33
22
11
测试最小优先级队列
11
22
33
55

04. stack栈

4.1栈的简介

• 栈（stack）是限制插入和删除只能在一个位置上进行的线性表，该位置在表的末端，叫做栈顶。添加元素只能在尾节点后添加，删除元素只能删除尾节点，查看节点也只能查看尾节点。添加、删除、查看依次为入栈（push）、出栈（pop）、栈顶节点（top）。形象的说，栈是一个先进后出（LIFO）表，先进去的节点要等到后边进去的节点出来才能出来。
• 头文件#include<stack>

4.2 stack栈的构造函数

• stack采用模板类实现， stack对象的默认构造形式： stack <T> stkT;
• stack <int> stkInt; //一个存放int的stack容器。
• stack <float> stkFloat; //一个存放float的stack容器。
• stack <string> stkString; //一个存放string的stack容器。
• ... //尖括号内还可以设置指针类型或自定义类型。

4.3 stack栈的成员函数

• empty() 堆栈为空则返回真
• pop() 移除栈顶元素
• push() 在栈顶增加元素
• size() 返回栈中元素数目
• top() 返回栈顶元素

05. list列表

5.1 list简介

• list 也是顺序容器的一种。只是list 是一个双向链表。使用 list 需要包含头文件 list。双向链表的每个元素中都有一个指针指向后一个元素，也有一个指针指向前一个元素，如下图所示。

• 当然，list的用法和vector很类似，也拥有顺序容器中的常用方法，需要注意的是list不支持使用下标随机存取元素。
• 在 list 容器中，在已经定位到要增删元素的位置的情况下，增删元素能在常数时间内完成。如下图所示，在 ai 和 ai+1 之间插入一个元素，只需要修改 ai 和 ai+1 中的指针即可：

5.2 list构造函数

• list采用采用模板类实现,对象的默认构造形式：list<T> lstT; 如：
• list<int> lstInt; //定义一个存放int的list容器。
• list<float> lstFloat; //定义一个存放float的list容器。
• list<string> lstString; //定义一个存放string的list容器。
• ... //尖括号内还可以设置指针类型或自定义类型。

5.3 list成员函数

• assign() 给list赋值
• back() 返回最后一个元素
• begin() 返回指向第一个元素的迭代器
• clear() 删除所有元素
• empty() 如果list是空的则返回true
• end() 返回末尾的迭代器
• erase() 删除一个元素
• front() 返回第一个元素
• get_allocator() 返回list的配置器
• insert() 插入一个元素到list中
• max_size() 返回list能容纳的最大元素数量
• merge() 合并两个list
• pop_back() 删除最后一个元素
• pop_front() 删除第一个元素
• push_back() 在list的末尾添加一个元素
• push_front() 在list的头部添加一个元素
• rbegin() 返回指向第一个元素的逆向迭代器
• remove() 从list删除元素
• remove_if() 按指定条件删除元素
• rend() 指向list末尾的逆向迭代器
• resize() 改变list的大小
• reverse() 把list的元素倒转
• size() 返回list中的元素个数
• sort() 给list排序
• splice() 合并两个list
• swap() 交换两个list
• unique() 删除list中重复的元素