线性结构

数组（Array）是一种线性表数据结构。它用一组连续的内存空 间，来存储一组具有相同类型的数据, 并且不支持动态扩容。

数组的大小与数组的元素个数以及数组的元素类型有关。 数组能通过下标随机访问元 素，读取和修改效率很高。 数组名表示的是首个数组元 素的地址，也可以对数组名加上 一个位移n得到第n个元素的地址。

数组在插入和删除的动作中，由于涉及数据搬移，因此时间 复杂度是O(n) ，十分低效。

v.push_back(x)：将元素x插入到vector末尾

v.pop_back()：将vector末尾的元素删除 v.clear() 将所有元素删除

v[下标]、v.at(下标) ：访问指定下标的元素

v[pos] = x：修改指定下标pos的元素为x

v.size()：v中的元素个数、v.resize(n) 将v的大小变为n

v.erase(pos)：删除指定迭代器位置的元素

v.insert(pos, x)：在指定迭代器位置前插入元素x

v.front()：返回v的第一个元素、 v.back()：返回v的最后一个元素

v.empty()：v是否为空容器，若空则返回true

链表是由一系列结点组成的线性结构。每个结点包括两部分： 一个存储数据元素的数据域，另一个是存储下一个结点地址的指针 域。数组的线性顺序是由数组下标决定的，而链表的线性是由各个 节点里的指针决定的。因此链表在内存上不需要连续，也不需要提 前预估链表的元素个数。

链表插入，删除速度较快，而查找操作较慢

ls.push_front(x)、ls.push_back(x); 向ls开头/结尾添加x。

ls.front()、ls.back(); 返回ls开头/结尾元素。

ls.pop_front()、 ls.pop_back(); 删除ls开头/结尾元素。

ls.size()：v中的元素个数、 ls.resize(n) 将ls的大小变为n

ls.clear() 清空链表、ls.empty()：v是否为空容器，若空则返回true

ls.insert(pos, x)：在指定迭代器位置pos前插入元素x STL中的链表容器

pos = ls.erase(pos)：删除指定迭代器位置的元素，并返回下一个元素的迭代器

ls.sort([cmp]); 对list进行排序，默认为升序排序，可传入排序规则cmp函数

ls.reverse(); 反转列表元素顺序、 ls.unique(); 删除连续的重复元素

队列是限定在一端进行插入，另一端进行删除的特殊线性 表。就像排队买东西，排在前面的人买完东西后离开队伍（删 除），而后来的人总是排在队伍末尾（插入）。 通常把队列的插入和删除分别称为入队和出队。允许出队 的一端称为队首，允许入队的一端称为队尾。

q.push(x); 将x入队到队尾。

q.pop(); 将队首元素出队。

q.front()、q.back(); 返回队首/队尾元素。

q.size(); 返回队列的元素个数

q.empty(); q是否为空容器，若空则返回true

q1.swap(q2); 交换q1与q2，等效写法为：swap(q1, q2);

q1 = q2; 将q2的内容赋值给q1。

栈是只能在某一端插入和删除 的特殊线性表。 用桶堆积物品，先堆进来的压 在底下，随后一件一件往上堆。取走 时。只能从上面一件一件取。堆和取 都在顶部进行，底部一般是不动的。

stk.push(x); 将x入栈至栈顶。

stk.pop();将栈顶元素出栈。

stk.top();返回栈顶元素。

stk.size();返回栈的元素个数。

stk.empty(); stk是否为空容器，若空则返回true。 stk1.swap(stk2); 交换stk1与stk2，等效写法为：swap(stk1, stk2); stk1 = stk2; 将stk2的内容赋值给stk1。

字符串：字符串是由数字、字母、下划线等组成的一串字符，它 是有顺序性的（从左到右）。 字符串是一种特殊的线性表，通常用字符数组存储。

字符串输入输出：cin >> s; getline(cin, s); cout << s;

字符串遍历：for (int i = 0; s != s.size(); ++i) 、for (char c : s)

字符串字符修改：s[i] = 'x';

字符串拼接：s = s1 + s2;

字符串插入：s1.insert(2, s2);

字符串删除：s.erase(2, 1);