【数据结构】栈与队列

栈
- 顺序栈
  - 共享栈
- 链栈
队列

栈和队列

我们以下的使用的栈或队列都是作为一个工具来解决其他问题的，我们可以把栈或队列的声明和操作写的很简单，而不必分函数写出。

顺序栈

声明一个栈并初始化：

  ElemType stack[maxSize];    //存放栈中的元素
  int top = -1;   //栈顶指针（指向栈顶元素）

元素进栈：

  stack[++top] = x;

元素出栈：

  x = stack[top--];

判断栈空:

  top == -1;  //栈空
  top > -1;   //栈非空

顺序队列

声明一个队列并初始化：

  ElemType queue[maxSize];    //存放队列中元素
  int front = -1, rear = -1;  //队头（指向队头元素的前一个位置），队尾（指向队尾元素）

元素入队：

  queue[++rear] = x;

元素出队：

  x = queue[++front];

判断队空:

  front == rear;  //队空
  front < rear;   //队非空

使用“栈”遍历：是用来从最近访问的一个结点开始，访问其他结点
使用“队列”遍历：是用来按照访问的顺序开始，访问其他结点

栈

卡特兰(Catalan)数：({{1}over{n+1}}C_{2n}^{n})
应用：对于n个不同元素进栈，出栈序列的个数为({{1}over{n+1}}C_{2n}^{n})

栈的应用：括号匹配、表达式求值（后缀表达式）、递归、迷宫求解等。
中缀表达式转换为前缀或后缀表达式：（手工做法）
1. 按照运算符的优先级对所有的运算单位加括号。
2. 转换为前缀或后缀表达式
  - 前缀：把运算符号移动到对应的括号前面
  - 后缀：把运算符号移动到对应的括号后面
在中缀表达式转化为相应的后缀表达式，需要根据操作符的优先级来进行栈的变化：

栈外优先级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个。
中缀表达式转换为后缀表达式：（程序做法）
1. 从左向右开始扫描中缀表达式
2. 遇到数字时，加入后缀表达式
3. 遇到运算符时：按照运算符的优先级进行操作
  - 若当前扫描元素优先级>栈顶元素，那么当前扫描元素就入栈，先处理当前扫描元素，再处理栈顶元素
  - 若当前扫描元素优先级<栈顶元素，那么栈顶元素就出栈，先处理栈顶元素，再处理当前扫描元素
  - 若当前扫描元素优先级=栈顶元素，那么pop，不输出
  - 若为'('，入栈
  - 若为')'，则依次把栈中的运算符出栈，并加入后缀表达式，直到出现'('，从栈中删除'('；
  - 若为除括号外的其他运算符，当其优先级高于除'('以外的栈顶运算符时，直接入栈；
    否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
4. 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
待处理序列当前扫描元素后缀表达式栈动作
依次扫描，扫描元素优先级高的入栈；扫描元素优先级低，先让优先级较高的栈顶元素处理
以元素。。开头的序列个数是，把该元素出栈，再将剩下的元素一个个插到现有栈中元素之间，即可算出个数。

操作符	#	(	*,/	+,-	)
栈外优先级icp	0	6	4	2	1
栈内优先级isp	0	1	5	3	6

顺序栈

基本概念：
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(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）

为了区分队空队满的情况，有三种处理方式：
1. 牺牲一个单元来区分队空队满，入队时少用一个队列单元。约定以“队头指针在队尾指针的下一位置作为队满的标志”
  - 队满条件：(Q.rear+1)%MaxSize == Q.front；
  - 队空条件：Q.front == Q.rear；
  - 队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize。
2. 类型中增设表示元素个数的数据成员。
  - 队空条件：Q.size == 0；
  - 队满条件：Q.size == MaxSize。
    
    这两种情况都有Q.front == Q.rear。
3. 类型中增设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;
- 入队操作：尾插法；
- 出队操作：删除头。
适用性：
链队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。
另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链队列，这样就不会出现存储分配不合理和“溢出”的问题。

双端队列

受限的唯一一端，最好放在左边，无论是输出还是输出，好看一些。

基本概念：
双端队列是指允许两端都可以进行入队和出队操作的队列。
受限的双端队列：
- 输出受限：只有一端能输出，两端都能输入
- 输入受限：只有一端能输入，两端都能输出
技巧：
- 对于这种受限的双端队列，左右仅此一个的操作，为解题关键。
- 输入受限：只有一端能进行输入操作，输入操作唯一
  ∵入队序列唯一
  ∴看能否出成选项当中的序列
- 输出受限：只有一端能进行输出操作，输出操作唯一
  ∵出队序列唯一
  ∴看能否入成这种队列