Chapter3 栈、队列和数组
3.1 栈 (LIFO)
3.1.1 栈的基本概念
-
特点：栈（Stack）是只允许在一端进行插入或删除操作的线性表。其操作的特性是后进先出（Last In First Out）
栈顶（Top）线性表允许进行插入删除的那一端
栈低（Bottom）固定的，不允许进行插入和删除的另一端
-
基本操作
InitStack(&S)：初始化一个空栈S。StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回falsePush(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并且用x返回。GetTop(S,&X)：读栈顶元素，但不出栈，若栈S非空，则用x返回栈顶元素DestroyStack(&S)：销毁栈，并且释放栈S占用的存储空间 -
卡特兰数公式求出栈数：当n个不同元素进栈时，出栈元素不同排列的个数位 1/(n+1)C(n,n+2) 。可采用数学归纳法证明
3.1.2 栈的顺序存储结构
栈是一种操作受限的线性表，与线性表类似的，也有对应两种存储方式
-
顺序栈的实现
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示栈顶元素的位置。
//栈的顺序存储类型描述 #define MAXSIZE 50 //定义栈中元素的最大个数 typedef struct{ ElemType data[MAXSIZE]; //存放栈中元素 int top; //栈顶指针 }SqStack;进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶
出栈操作：栈非空时，先取栈顶元素，再将栈顶指针减1
-
顺序栈的基本操作
//-------------------栈顶top = -1 //-------------------此时top指向栈顶元素 //初始化 void InitStack(SqStack &S){ S.top=-1; //初始化栈顶指针 } //判栈空 bool StackEmpty(SqStack S){ if(S.top==-1) //栈空 return true; else //不空 return false; } //进栈 bool Push(SqStack &S,ElemType x){ if(S.top==MAXSIZE-1) //栈满，报错 return false; S.data[++S.top]=x; //指针先加，再入栈 return true; } //出栈 bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) //栈空，报错 return false; x=S.data[S.top--]; //先出栈，指针再减 return true; } //读栈顶元素 bool GetTop(SqStack S,ElemType &x){ if(S.top==-1) //栈空，报错 return false; x=S.data[S.top]; //x记录栈顶元素 return true; }//-------------------栈顶top = 0 //-------------------此时top指向栈顶元素之上的空位 //初始化 void InitStack(SqStack &S){ S.top=0; //初始化栈顶指针 } //判栈空 bool StackEmpty(SqStack S){ if(S.top==0) //栈空 return true; else //不空 return false; } //进栈 bool Push(SqStack &S,ElemType x){ if(S.top==MAXSIZE) //栈满，报错 return false; //!!!!!!!!!! 先入栈，指针再加 !!!!!!!!!! S.data[S.top++]=x; return true; } //出栈 bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) //栈空，报错 return false; //!!!!!!!!!! 指针先减，再出栈 !!!!!!!!!! x=S.data[--S.top]; return true; } //读栈顶元素 bool GetTop(SqStack S,ElemType &x){ if(S.top==0) //栈空，报错 return false; x=S.data[S.top-1]; //x记录栈顶元素 return true; } -
共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MAXSIZE时1号栈为空。仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。
3.1.3 栈的链式存储结构
采用链式存储的栈称为链栈，其优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况，通常用单链表实现，并规定所有操作都是在单链表的表头进行。
```c
//栈的链式存储类型
typedef struct LinkNode{
ElemType data; //数据域
struct LinkNode *next; //指针域
}LiStack;
```
3.2 队列（FIFO）
3.2.1 队列的基本概念
-
定义：队列（Queue）也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。其操作的特性是先进先出（Frist In Last Out）
队头（Front）允许删除的一端，又称队首
队尾（Rear）允许插入的一端
-
基本操作
InitQueue(&Q)：初始化队列，构造一个空队列QQueueEmpty(Q)：判断队列空，若队列Q为空返回true，否则返回falseEnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并且用x返回GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x
3.2.2 队列的顺序存储结构
-
队列的顺序存储：分配一块连续的存储单元存放队列中的元，并且附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（即将可以存放的空位）
#define MAXSIZE 50 //定义队列中元素的最大个数 typedef struct{ ElemType data[MAXSIZE]; //用数组存放队列元素 int front,rear; //队头指针和队尾指针 }SqQueue;初始时：Q.front=Q.rear=0
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1
出队操作：队不空时，先取队头元素，再将队头指针加1
Note
非循环队列存在“上溢出”。并非真正溢出，此时Q.rear==MAXSIZE，但Q.front!=0。原因是非循环队列的rear达到MAXSIZE后，无法再移动，要解决这个问题，我们引入循环队列。
-
循环队列：为了解决顺序队列“上溢出”的问题，引入循环队列，即吧存储队列元素的表从逻辑上视为一个环，称为循环队列。
Note
循环队列如何判空和判满呢？
判空条件显然是Q.front==Q.rear。但若入队速度大于出队速度，那么队尾指针很快就会赶上队首指针，此时队满也有Q.front==Q.rear。由此判空和判满条件就产生了冲突。
为了解决这个冲突，有三种处理方式（1牺牲一个存储单元、2队列数据类型中增加size数据、3队列数据中增加tag数据）牺牲一个存储单元是最普遍的做法
（牺牲一个单元来区分队空和队满，入队时少用一个队列单元）
队满条件：(Q.rear+1)%MAXSIZE==Q.front
队空条件：Q.front==Q.rear
队列中元的个数：(Q.rear-Q.front+MAXSIZE)%MAXSIZE
-
循环队列的操作
//初始化 void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; } //判队空 bool isEmpty(SqQueue Q){ if(Q.rear==Q.front) return true; else return false; } //入队 bool EnQueue(SqQueue &Q,ElemType x){ if((Q.rear+1)%MAXSIZE==Q.front) return false; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; return true; } //出队 bool DeQueue(SqQueue &Q,ElemType &x){ if(Q.rear==Q.front) return false; x=Q.data[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return true; }
3.2.3 队列的链式存储结构
-
队列的链式存储：实际上是一个同时拥有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个节点。
//队列的链式存储类型可描述为 typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue;注：不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计为一个带头结点的单链表，这样插入和删除操作就统一了
假如程序中要使用多个队列，多个栈的情形，最好使用链式队列，这样就不会出现存储分配不合理和“溢出问题”
-
链式队列的基本操作
//初始化 void InitQueue(LinkQueue &Q){ //初始化带头结点的队列 Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //建立头结点 Q.front->next=NULL; //初始为空 } //判队空 bool IsEmpty(LinkQueue Q){ if(Q,front==Q.rear) return true; else return false; } //入队 void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点 s->data=x; s->next=NULL; Q.rear->next=s; //插入链尾 Q.rear=s; //修改尾指针 } //出队 bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==Q.rear) return false; //空队 LinkNode *p=Q.front->next; x=p=>data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; //若原队列中只有一个结点，删除后变空 free(p); return true; }3.2.4 双端队列
双端队列是指允许两端都可以进行插入和删除操作的线性表
输出受限的双端队列：两端都可以插入，但只有一端可以删除
输入受限的双端队列：两端都可以删除，但只有一端可以插入
3.3 栈和队列的应用
要熟练掌握栈和队列，必须学习栈和队列的应用。
3.3.1 栈在括号匹配中的应用
-
算法思想
1初始设置一个空栈，顺序读入括号
2若是左括号，则作为一个新的更急迫的期待压入栈中，使原有的栈中所有未消解的期待和急迫降一级
3若是右括号，则或使置于栈顶的最急迫期待得以消解，或是不合法的情况（括号序列不匹配，退出程序）
算法结束时，栈应当为空，否则括号序列不匹配
3.3.2 栈在表达式求值中的应用
-
算术表达式（根据表达式树转换）
前缀表达式（NLR）：-+A*B-CD/EF
中缀表达式（LNR）：A+B*(C-D)-E/F
后缀表达式（LRN）：ABCD-*+EF/-
中缀表达式需要带括号，故不容易被计算机解析，但由于符合人的思维习惯，运用在许多编程语言中。前、后缀表达式更容易被计算机处理。所以一般需要将代码的中缀表达转为前、后缀表达式。
在计算机中，中缀表达式转后缀表达式需要借助一个栈，用于保存暂时还不能确定运算顺序的运算符。
3.3.3 栈在递归中的应用
-
递归：递归是一种重要的程序设计方法。若一个函数、过程或数据结构的定义中应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
它通常把一个大型的复杂问题层层转化为规模较小的问题来求解，只需要少量的代码就可以描述出解题过程所需的多次重复计算，但是通常情况下，它的效率并不太高
//斐波那契数列递归实现 int F(int n){ if(n==0) return 0; //边界条件 else if(n==1) return 1; //边界条件 else return F(n-1)+F(n-2); //递归表达式 }注意递归模型不能是循环定义的，必须满足两个条件：1递归表达式 2边界条件
在递归调用过程中，系统为每一层的返回点、局部变量、传入参数等开辟了递归工作栈来进行数据存储。若想具体了解递归如何实现，可以参阅编译原理教材的相关内容。
3.3.4 队列在层次遍历中的应用
-
队列实现层序遍历
1 根结点入队
2 若队空（所有结点处理完毕），则遍历结束，否则重复3操作
3队列中第一个结点出队，并且访问。若其有左孩子，则左孩子入队；若其有右孩子，则右孩子入队，返回2。
3.3.5 队列在计算机系统中的应用
队列在计算机系统的应用非常广泛，以下仅从两个方面进行阐述：
1 解决主机与外部设备速度不匹配的问题
-
缓冲区的逻辑结构
以主机与打印机之间速度不匹配的问题为例。主机输出数据给打印机，输出数据的速度比打印机数据的速度要快得多，因为速度不匹配，若直接把输出的数据送给打印机，显然是步行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并且打印，打印完成再请求数据。
2 解决由多用户引起的资源竞争问题
-
多队列 出队入队 操作
CPU的资源竞争就是一个典型的例子，在一个带有多终端的计算机系统上，有多个用需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新的队首请求的用户使用。
3.4 数组和特殊矩阵
矩阵在计算机图形学、工程计算中占有举足轻重的地位。数据结构不研究矩阵及其运算，而是然后将矩阵更有效地存储在内存中（如何用最小的内存空间来存储同样的数据），并且方便地提取矩阵元素。
3.4.1 数组的定义
数组是由n(n>=1)个同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标
数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素是定长数组的线性表，依此类推。
3.4.2 数组的存储结构
一个数组的所有元素在内存中占用一段连续的存储空间。以一维数组A[0...n-1]为例
LOC(a_i) = LOC(a_0)+i*L (0 <= i < n) ，L为每个数组元素所占的存储单元
3.4.3 特殊矩阵的压缩存储
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性。
-
对称矩阵：n阶矩阵A中任意一个元素a_i,j = a_j,i，则为对称矩阵
对称矩阵的上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，会浪费几乎一半空间， 为此将n阶矩阵的A存放在一维数组中，按照上对角列优先存储
-
三角矩阵：
-
三对角矩阵