用字符“画”线性容器，包括Vector, List, Stack, Queue。
Vector(向量)
Vector是可以动态修必储空间的数组，在程序上，是维护存储容量、元素数量、数组数据的过程。
template <typename T>
class Vector
{
int m_cap; /** 存储容量 */
int m_size; /** 元素数量 */
T* m_array; /** 存放数据的数组 */
};
如下图，Vector的容量是5，已经存了3个元素，数据分别是abc。
内存：[a][b][c][ ][ ]
下标： 0 1 2 3 4
对于Vector:
- 元素可以通过下标访问，速度快，时间复杂度为O(1)；
- 元素的删除和插入，需要移动数据，速度慢，时间复杂度为O(n)；
- 尾部删除和插入例外，时间复杂度为O(1)。
List(链表)
List的数据由一个个通过指针连接的节点构成，节点连接示意图如下。List需要维护各节点之间的连接关系，可以看到
- 节点的遍历需要从head或者tail开始，时间复杂度为O(n)；
- 节点的插入和删除，只是节点连接关系的修改，速度快，时间复杂度为O(1)。
head tail
节点：[a] -> [b]-> ... -> [c]
<- <- ... <-
节点的连接通过指针实现，代码如下：
template <typename T>
struct ListNode
{
T data;
ListNode<T>* prev;
ListNode<T>* next;
};
Stack(栈)
Stack是一种先进后出（FILO）的数据结构，可以通过Vector或List实现，Stack任何时候都只能访问和操作顶部top的数据，如下图所示。
[ ]
top -> [a]
[b]
[c]
Queue(队列)
Queue是一种先进先出（FIFO）的数据结构，可以通过Vector或List实现，Queue任何时候只能只访问和操作头尾head和尾部tail的数据，数据一般从tail进，从head出，如下图所示。
tail head
[a][b][c]...[e][f]
下一个入队的数据：放在a的左边
下一个出队的数据：f
附：代码实现
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [ yehuohan@gmail.com ]