1. 线性表

1.1 顺序表

存在两种存储方式，定长和不定长。定长顺序表类似普通数组，不定长顺序表允许长度动态扩充。

1.2 链表

单链表进行插入删除操作需要考虑到操作节点是否是链表的头结点，因为对头结点进行操作时， 需要修改链表指针的指向，对其进行专门处理。

单链表插入新节点的两种方法：前插法和后插法。前插法使得每次插入新结点在表的前端进行，后插法在表的后端进行，并推荐设置一个尾指针。

链表的变形：循环链表，双向链表。

可以用数组构成一个静态链表，数组中每个元素附加一个链接指针，指向下一个元素的数组下标。

1.3 线性表的C++，Java 实现

template < class T, size_t N > class array;std::arraytemplate < class T, class Alloc = allocator
     
       > class vector;std::vectortemplate < class T, class Alloc = allocator
      
        > class list;std::listtemplate < class T, class Alloc = allocator
       
         > class forward_list;std::forward_list
       
      
     

std::array 类似于用户自定义数组，实例化类模板时需要传入数组长度N，允许通过[ ] 访问

std::vector 可变长数组

std::list 双链表实现，std::forward_list 单链表实现

 

2. 栈(Stack)

栈保证了表中数据的后进先出(LIFO)。如果采用链式栈，可以在表头部进行插入删除操作。

栈的应用：(1) 括号匹配；(2) 表达式计算

 C++中的栈

template 
     
       > class stack;std::stack
     

 

3. 队列(Queue)

队列保证了线性表插入删除操作的先进先出(FIFO)

template 
     
       > class queue;std::queue
     

优先级队列(priority queue)

template 
     
      ,class Compare = less
      
        > class priority_queue; std::priority_queue
      
     

双端队列(deque)

在线性表的两端均可进行插入删除操作

template < class T, class Alloc = allocator
     
       > class deque;std::deque