栈
栈：限定仅在表尾进行插入和删除操作的线性表。
栈又称为后进先出（Last In First Out）线性表，简称LIFO结构。
栈对线性表的插入和删除的位置进行了限制，但是并没有对何时插入与删除进行限制，在不是所有元素都进栈，并保证栈顶元素出栈的情况下，先进入的可以不必最后出。
栈的存储结构
顺序存储结构
对于顺序存储结构，可以通过数组来实现。一般将下标为0的一端作为栈底，这样当存入和删除元素时，数组变化最小。定义top变量指代栈顶元素在数组中的位置，但是top变量必须小于数组的长度。当栈存在一个元素时，top记为0，因此把空栈的top记为-1.
假设有5个元素下栈的几种可能情况。
push操作代码：
pop操作代码：
两栈共享空间
为了最大程度上利用数组的空间，可以通过将两个同类型的栈组合起来，一起共享数组空间。将两个栈底分别作为数组的起始端和末端。如图：
只要top1和top2两个栈顶指针不相遇，两个栈就可以一直使用。
当top1等于-1时，栈1为空；当top2等于n时，栈2为空。
当栈2为空，top1等于n-1时，栈1满栈；当top2等于0时，栈2满栈。
当两个指针之间相差1时，即 top1 + 1 == top2 时栈是满栈。
两栈共享空间的push操作代码：
注意，红色部分，++i 与 i++ 的区别。
pop操作代码：
使用这种数据结构，通常是两个栈的空间需求有相反关系时，即一个栈空间增加而另一个栈空间缩小。
链式存储结构
栈的链式存储结构，可以简称为链栈。
由于链表含有头指针的单链表头，因此可以通过单链表头作为栈顶。效果图如下：
对于空栈来说，由于空链表定义的头指针指向空，则链栈的空其实就是 top=NULL。
push操作代码：
pop操作：
通过链栈和顺序栈的比较可知：在栈的使用过程中，若使用的元素变化不可预测，时大时小，则最好使用链栈，若知道在可控的范围内，则使用顺序栈更好。
栈的作用
栈的引用，简化了程序设计的问题，划分了不同关注层次，使思考范围缩小，更聚焦当前要解决的问题。数组之类的，还需要分散精力去考虑数组下标增减等细节问题。
栈的应用
递归
定义：直接调用自己或通过一些列的调用语句间接地调用自己的函数，称作递归函数。
注意：递归的最大陷阱就是要防止进入无限递归因此在每个递归定义必须至少有一个条件，满足时递归不再进行。
运用递归能使程序的结构更清晰、更简洁、更容易理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量时间和内存。迭代则不需要反复调用函数和占用额外的内存。
栈和递归的关系：
在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，即恢复调用的状态。
四则运算表达式求值
后缀表达式规则：
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
$$
9+(3-1)×3+10÷2
$$
示例:
在平常的四则运算中的表达式叫做中缀表达式。中缀表达式转换为后缀表达式的规则：
从左到右遍历表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分，若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
想让计算机处理常用的中缀表达式，最重要的是以下两步：
- 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）
队列
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为对头。
队列的存储结构
循环队列
队列的顺序存储结构需要建立一个大于n的数组，但是由于队列的特殊性（先进先出）入队操作，只需在数组后加一个元素，不需要移动任何元素，此时复杂度为O(1)。但是，在出队操作时，需要删除数组第一个元素，则需要把所有元素都向前移动，此时的时间复杂度为O(n)。
为了避免出队列时，增加时间复杂度，引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，当front等于rear时，此队列是空队列。
假溢出：在入队时，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，而且队列的前端还有空闲，把这种现象称为假溢出。
为了解决假溢出的问题，引入了循环队列：把队列的头尾相接的顺序存储结构称为循环队列。
但此时的问题是：当front指针等于rear指针时，此时队列为空。但是此时，front指针等于rear指针，队列为满。
那么如何判断当front指针等于rear时，队列是空还是满呢？
- 设置一个标志变量flag，当front==rear，且flag = 0时队列为空，当flag=1时队列为满。
- 办法二，当队列为空时，条件就是front ==rear，当队列满时，修改其条件，保留一个元素空间。
上图即为方法二的满队情况。
在满队的情况下，rear有可能比front大也可能小。需要通过以下方法来判断队列满。
设队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize == front.
通用的队列长度计算公式：（rear-front + QueueSize）%QueueSize
循环队列的顺序存储结构代码如下：
循环队列的初始化代码如下：
循环队列求长度代码：
循环队列的入队操作：
循环队列的出队操作：
队列的链式存储结构
队列的链式存储结构，其实就是线性表的单链表，只是只能尾进头出，简称为链队列。将头指针指向链队列的头结点，队尾指针指向终端结点。
当队列为空时，头指针和尾指针都指向头结点。
入队操作：
出队操作：
在可以确定队列长度最大值的情况下，建议用循环队列，若无法预估计队列的长度时，则用链队列。