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是空的则返回trueend()
返回末尾的迭代器erase()
删除一个元素front()
返回第一个元素get_allocator()
返回list的配置器insert()
插入一个元素到list中max_size()
返回list能容纳的最大元素数量merge()
合并两个listpop_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()
合并两个listswap()
交换两个listunique()
删除list中重复的元素
评论已关闭