C++ STL学习笔记之队列、栈、双向链表
2020 年 07 月 09 日 363 1391 字 暂无评论

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 容器中,在已经定位到要增删元素的位置的情况下,增删元素能在常数时间内完成。如下图所示,在 aiai+1 之间插入一个元素,只需要修改 aiai+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中重复的元素

版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/105/



评论已关闭