文章目录
栈
定义
栈是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。后进先出的线性表，last in first out（LIFO）
抽象数据类型
栈本身是线性表，在笔记一中，已经写过关于线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。
但是由于栈的特殊性，所以插入push和删除pop操作会有一点点变化。
栈的顺序存储结构及实现
进栈操作
两栈共享空间
栈的顺序存储有一个很大的缺陷，就是必须事先确定数组存储空间大小，解决办法是用同一个数组来存储两个相同类型的栈。
数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。
栈的链式存储结构及实现
通常对于链栈来说，是不需要头结点的。
对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。
进栈操作
假设元素值为e的新结点是s，top为栈顶指针。
出栈操作
假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。
如果栈的使用过程中元素变化比较多，最好是用链栈，如果变化在可控范围内，建议使用顺序栈会更好一些。
队列的定义
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。先进先出的线性表，FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列的抽象数据类型
队列也是线性表，所以队列有线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。
循环队列
循环队列的定义：
解决假溢出的办法就是头尾相接的循环。队列的这种头尾相接的顺序存储结构称为循环队列。
front指针指向队头元素，rear指针指向队尾元素的下一个位置。当front等于rear时，此队列不是还剩一个元素，而是空队列。
通用的计算队列长度公式为：
(rear - front + QueueSize)%QueueSize
队列的链式存储结构及实现
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，把它简称为链队列。
入队操作
出队操作
串
串的定义
字符串，是由零个或多个字符组成的有限序列。
串的比较
串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
串的存储结构
串的顺序存储结构
用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，一般是用定长数组来定义。