目录
- 栈
- 顺序栈
- 共享栈
- 链栈
- 顺序栈
- 队列
- 顺序队列
- 循环队列
- 链队列
- 双端队列
- 顺序队列
栈和队列
我们以下的使用的栈或队列都是作为一个工具来解决其他问题的，我们可以把栈或队列的声明和操作写的很简单，而不必分函数写出。
- 顺序栈
- 声明一个栈并初始化：
ElemType stack[maxSize]; //存放栈中的元素
int top = -1; //栈顶指针（指向栈顶元素）
1. 元素**进栈**：
stack[++top] = x;
1. 元素**出栈**：
x = stack[top--];
1. 判断**栈空**:
top == -1; //栈空
top > -1; //栈非空
- 顺序队列
- 声明一个队列并初始化：
ElemType queue[maxSize]; //存放队列中元素
int front = -1, rear = -1; //队头（指向队头元素的前一个位置），队尾（指向队尾元素）
1. 元素**入队**：
queue[++rear] = x;
1. 元素**出队**：
x = queue[++front];
1. 判断**队空**:
front == rear; //队空
front < rear; //队非空
- 使用“栈”遍历：是用来从最近访问的一个结点开始，访问其他结点
- 使用“队列”遍历：是用来按照访问的顺序开始，访问其他结点
栈
卡特兰(Catalan)数：\({{1}\over{n+1}}C_{2n}^{n}\)
应用：对于n个不同元素进栈，出栈序列的个数为\({{1}\over{n+1}}C_{2n}^{n}\)
- 栈的应用：括号匹配、表达式求值（后缀表达式）、递归、迷宫求解等。
- 中缀表达式转换为前缀或后缀表达式：（手工做法）
- 按照运算符的优先级对所有的运算单位加括号。
- 转换为前缀或后缀表达式
- 前缀：把运算符号移动到对应的括号前面
- 后缀：把运算符号移动到对应的括号后面
- 在中缀表达式转化为相应的后缀表达式，需要根据操作符 的优先级来进行栈的变化：
栈外优先级icp(in coming priority, icp)：表示当前扫描到的运算符ch的优先级；
栈内优先级isp(in stack priority, isp)：为该运算符进栈后的优先级。这个优先级其实也很简单，就是一般的运算优先级，有括号先算括号、先乘除后加减、同级运算从左往右依次运算。
操作符 # ( *,/ +,- ) 栈外优先级icp 0 6 4 2 1 栈内优先级isp 0 1 5 3 6 - icp>isp：进栈，读下一个字符
icp=isp：pop，不输出（#,(,)）
icp<isp：出栈并输出如a+b-a*((c+d)/e-f)+g转换为ab+acd+e/f-*-g
+-*((+（按优先级进入的）
+号遇到-号之后运算了，后面的不能算得看下一个，遇到)能算了。所以栈中存的暂时还不能确定运算次序的操作符最多则5个。
- icp>isp：进栈，读下一个字符
- 中缀表达式转换为后缀表达式：（程序做法）
- 从左向右开始扫描中缀表达式
- 遇到数字时，加入后缀表达式
- 遇到运算符时：按照运算符的优先级进行操作
- 若当前扫描元素优先级>栈顶元素，那么当前扫描元素就入栈，先处理当前扫描元素，再处理栈顶元素
- 若当前扫描元素优先级<栈顶元素，那么栈顶元素就出栈，先处理栈顶元素，再处理当前扫描元素
- 若当前扫描元素优先级=栈顶元素，那么pop，不输出
- 若为'(‘，入栈
- 若为’)’，则依次把栈中的运算符出栈，并加入后缀表达式，直到出现'(‘，从栈中删除'(‘；
- 若为除括号外的其他运算符，当其优先级高于除'(‘以外的栈顶运算符时，直接入栈；
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
- 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
待处理序列 当前扫描元素 后缀表达式 栈 动作 - 依次扫描，扫描元素优先级高的入栈；扫描元素优先级低，先让优先级较高的栈顶元素处理
- 以元素。。开头的序列个数是，把该元素出栈，再将剩下的元素一个个插到现有栈中元素之间，即可算出个数。
顺序栈
- 基本概念：
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指向当前栈顶的位置。 - 存储结构：
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //存放栈中元素
int top; //栈顶指针
}SqStack; //Sequence Stack
- 基本操作：
- 栈顶指针：S.top，初始时设置S.top=-1；（即 指向了栈顶元素）
- 栈顶元素：S.data[S.top]；
- 进栈操作：栈不满是，栈顶指针先加1，再送值到栈顶元素；
- 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1；
- 栈空条件：S.top == -1；
- 栈满条件：S.top == MaxSize-1；
- 栈长：S.top+1
共享栈
- 基本概念：
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数据空间，将两个站的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。 - 基本操作：
- 栈空条件：
- 0号栈：top0=-1
- 1号栈：top1=MaxSize
- 栈满条件：top1 – top0 = 1(即 当两个栈顶指针相邻时栈满)
- 进栈操作：
- 0号栈：top0先加1再赋值
- 1号栈：top1先减1再赋值
- 出栈操作：栈非空时，
- 0号栈：先取栈顶元素值，再将top0减1；
- 1号栈：先取栈顶元素值，再将top1加1
- 栈空条件：
链栈
在表头入栈出栈
- 基本概念：
采用链式存储的栈称为链栈，通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。 - 存储结构：
typedef struct LinkNode {
ElemType data; //数据域
struct LinkNode *next; //指针域
}*LiStack; //List Stack
- 操作：
//插入x结点
x->next = top;
top = x;
- 优点：
便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。便于结点的插入与删除。
队列
- 队列的应用：层次遍历、解决主机与外部设备之间速度不匹配的问题、解决由多用户引起的资源竞争的问题、页面替换算法等。
顺序队列
- 基本概念：
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指向队头元素和队尾元素的位置。（这里队头指针指向队头元素的前一个位置，队尾指针指向队尾元素）（避免队空与队列中只有一个元素时无法区分） - 存储结构：
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //存放队列元素
int front, rear; //队头指针和队尾指针
}SqQueue; //Sequence Queue
- 基本操作：
- 初始状态；Q.front = -1; Q.rear = -1；
- 队空条件：Q.front == Q.rear； (因为队头指针指向队头元素的前一个位置，所以当与队尾指针相等时，队空)
- 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1；
- 出队操作：队不空时，先取队头元素值，再将队头指针加1；
- 队满条件：无法判断队满，当rear > maxsize-1，front > -1时，其实队中依然有空位（front之前还有空位）可以存放元素，只是由于被指针欺骗了，这种现象称为“假溢出”。
循环队列
- 基本概念：
将顺序队列臆造为一个环状的空间，即吧存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，利用取余运算(%)。 - 基本操作：
- 初始时：Q.front = Q.rear = 0；
- 入队操作：Q.rear = (Q.rear+1)%MaxSize； (在队尾排队)
- 出队操作：Q.front = (Q.front+1)%MaxSize； (在队头出队)
- 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。
- 出队入队时：指针都按顺时针方向进1
但是无法区分队空与队满（都为Q.front == Q.rear）
为了区分队空队满的情况，有三种处理方式：
- 牺牲一个单元来区分队空队满，入队时少用一个队列单元。约定以“队头指针在队尾指针的下一位置作为队满的标志”
- 队满条件：(Q.rear+1)%MaxSize == Q.front；
- 队空条件：Q.front == Q.rear；
- 队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize。
- 类型中增设表示元素个数的数据成员。
- 队空条件：Q.size == 0；
- 队满条件：Q.size == MaxSize。
这两种情况都有Q.front == Q.rear。
- 类型中增设tag数据成员，以区分是队满还是队空。
- 队空条件：tag == 0时，若因删除导致Q.front == Q.rear，则为队空；
- 队满条件：tag == 1时，若因插入导致Q.front == Q.rear，则为队满。
链队列
头出尾进
- 基本概念：
队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表(通常设计成带头结点的单链表，方便操作)。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序队列不同）。 - 存储结构：
typedef struct LinkNode{//链式队列结点
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct { //链式队列
LinkNode *front, *rear; //队列的队头和队尾指针
}LinkQueue;
- 基本操作：
- 初始化：Q.front = Q.rear = 头结点；
- 队空条件：Q.front == NULL且Q.rear == NULL;
- 入队操作：尾插法；
- 出队操作：删除头。
- 适用性：
链队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。
另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链队列，这样就不会出现存储分配不合理和“溢出”的问题。
双端队列
受限的唯一一端，最好放在左边，无论是输出还是输出，好看一些。
- 基本概念：
双端队列是指允许两端都可以进行入队和出队操作的队列。 - 受限的双端队列：
- 输出受限：只有一端能输出，两端都能输入
- 输入受限：只有一端能输入，两端都能输出
- 技巧：
- 对于这种受限的双端队列，左右仅此一个的操作，为解题关键。
- 输入受限：只有一端能进行输入操作，输入操作唯一
∵入队序列唯一
∴看能否出成选项当中的序列 - 输出受限：只有一端能进行输出操作，输出操作唯一
∵出队序列唯一
∴看能否入成这种队列