栈

栈($Stack$)是只允许在一端进行插入或删除操作的线性表。栈的操作特性为后进先出($LIFO$)。

栈顶：线性表允许进行插入删除的那一端。

栈底：固定的，不允许进行插入和删除的另一端。

空栈：不含任何元素的空表。

栈的数学性质：$n$个不同元素进栈，出栈元素不同排列的个数为$\Large\frac{1}{n+1}C^{~n}_{2n}$。上述公式称为卡特兰($Catalan$)数。

栈的基本操作：

• $InitStack~(\&S)$：初始化一个空栈$S$，分配内存空间。

• $DestroyStack~(\&S)$：销毁栈，并释放栈$S$占用的存储空间。

   

• $Push~(\&S,x)$：进栈，若栈$S$未满，则将$x$加入使之成为新栈顶。

• $Pop~(\&S,\&x)$：出栈，若栈$S$非空，则弹出栈顶元素，并用$x$返回。

   

• $GetTop~(S,\&x)$：读栈顶元素，若栈$S$非空，则用$x$返回栈顶元素。

• $StackEmpty~(S)$：判断一个栈是否为空，若栈$S$为空则返回$true$，否则返回$false$。

  在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数。

栈的顺序存储结构

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针($top$)指示当前栈顶元素的位置。栈的空间不可变。

#define MaxSize 50                // 定义栈中元素的最大个数
typedef struct{
    Elemtype data[MaxSize];        // 存放栈中元素
    int top;                    // 栈顶指针,初始时为 -1
} SqStack;

栈顶元素：$S.data[S.top]$。

进栈操作：栈不满时，栈顶指针先加$1$，再送值到栈顶元素。$S.data[++S.top]=x$

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减$1$。$x=S.data[S.top--]$

栈空条件：$S.top==-1$；栈满条件：$S.top==MaxSize-1$；栈长：$S.top+1$。

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

若栈顶指针初始化为$S.top=0$，则进栈操作为$S.data[S.top++]=x$，出栈操作为$x=S.data[--S.top]$。

共享栈：利用栈底位置相对不变的特性，为了更有效地利用存储空间，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。其存取数据的时间复杂度均为$O(1)$，所以对存取效率没有什么影响。判断栈满条件为：$top_0+1==top_1$。优点：节省存储空间，降低发生上溢的可能。

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，$Lhead$指向栈顶元素。

typedef struct Linknode{
    ElemType data;            // 数据域
    struct Linknode *next;    // 指针域
} *Listack;                    // 栈类型定义

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。对于带头结点和不带头结点的链栈，具体的实现会有所不同。

队列

队列($Queue$)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。操作的特性是先进先出($FIFO$)。

队头($Front$)：允许删除的一端，又称队首。

队尾($Rear$)：允许插入的一端。

空队列：不含任何元素的空表。

队列的基本操作：

• $InitQueue~(\&Q)$：初始化队列，构造一个空队列$Q$。

• $DestroyQueue~(\&Q)$：销毁队列，并释放队列$Q$占用的存储空间。

   

• $EnQueue~(\&Q,x)$：入队，若队列$Q$未满，将$x$加入，使之成为新的队尾。

• $DeQueue~(\&Q,\&x)$：出队，若队列$Q$非空，删除队头元素，并用$x$返回。

   

• $QueueEmpty~(Q)$：判队列空，若队列$Q$为空返回$true$，否则返回$false$。

• $GetHead~(Q,\&x)$：读队头元素，若队列$Q$非空，则将队头元素赋值给$x$。

队列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针$front$指向队头元素，队尾指针$rear$指向队尾元素的下一个位置。

不同教材对$front$和$rear$的定义可能不同，例如，可以让$rear$指向队尾元素、$front$指向队头元素。对于不同的定义，出队入队的操作是不同的。

#define MaxSize 50                // 定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];        // 存放队列元素
    int front,rear;                // 队头队尾指针
} SqQueue;

初始状态(队空条件)：$Q.front==Q.rear==0$。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加$1$。

出队操作：队不空时，先取队头元素值，再将队头指针加$1$。

会出现假溢出的现象，需要使用循环队列。

将顺序队列想象成为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针$Q.front=MaxSize-1$后，再前进一个位置就自动到$0$，这可以利用除法取余运算(%)来实现。

初始时：$Q.front=Q.rear=0$。

队首指针进$1$：$Q.front=(Q.front+1)\%MaxSize$。

队尾指针进$1$：$Q.rear=(Q.rear+1)\%MaxSize$。

队列长度：$(Q.rear+MaxSize-Q.front)\%MaxSize$。

出队入队时：指针都按顺时针方向进$1$。

为了区分是队空还是队满的情况，有三种处理方式：

• 牺牲一个单元来区分队空和队满，入队时少用一个队列单元。约定以“队头指针在队尾指针的下一位置作为队满的标志”。

  队空的条件：$Q.front==Q.rear$。

  队满的条件：$(Q.rear+1)\%MaxSize==Q.front$。

• 类型中增设表示元素个数的数据成员。

  队空的条件：$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{                    // 链式队列节点
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct{                    // 链式队列
    LinkNode *front,*rear;        // 队列的队头和队尾指针
} LinkQueue;

当$Q.front==NULL$且$Q.rear==NULL$时，链式队列为空。

使用带头结点的链式队列，判空条件为$Q.front==Q.rear$。

出队时，首先判断队是否为空，若不空，则取出队头元素，将其从链表中摘除，并让$Q.front$指向下一个结点(若该结点为最后一个结点，则置$Q.front$和$Q.rear$都为$NULL$)。

入队时，建立一个新结点，将新结点插入到链表的尾部，并改让$Q.rear$指向这个新插入的结点(若原队列为空队，则令$Q.front$也指向该结点)。

不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出"的问题。

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。

栈和队列的应用

栈在括号匹配中的应用

1. 初始设置一个空栈，顺序读入括号。

2. 若是右括号，查看栈顶元素是否为与之匹配的左括号：

   • 如果匹配，则将栈顶元素出栈，读入下一个括号；
   • 如果不匹配，则是不合法的情况，退出程序。

3. 若是左括号，将括号压入栈顶。

4. 括号输入完毕后，若栈不为空，则括号序列不匹配。

栈在表达式求值中的应用

中缀表达式：运算符在操作数中间。

后缀表达式(逆波兰式)：运算符在操作数后面。

前缀表达式(波兰式)：运算符在操作数前面。

一个中缀表达式可以对应多个后缀、前缀表达式。

中缀转后缀的手算步骤：

1. 确定中缀表达式中各个运算符的运算顺序。(运算顺序不唯一，因此对应的后缀表达式也不唯一)

   为了使手算步骤和机算步骤相同，规定：只要左边的运算符能先计算，就优先算左边的。(可保证运算顺序唯一)

2. 选择下一个运算符，按照「左操作数，右操作数，运算符」的方式组合成一个新的操作数。(看成一个整体加入后续的转换步骤中)

3. 如果还有运算符没被处理，就继续步骤$2$。

中缀转后缀的机算步骤：

1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

2. 从左到右处理各个元素，直到末尾。可能遇到三种情况：

   • 遇到操作数：直接加入后缀表达式。

   • 遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。

     “(”和“)”不加入后缀表达式。

   • 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。

3. 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算(手算)：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。

两个操作数的左右顺序不能交换。

后缀表达式的计算(机算)：

1. 从左往右扫描下一个元素，直到处理完所有元素。

2. 若扫描到操作数则压入栈，并回到步骤1；否则执行步骤3。

3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1。

   先出栈的是“右操作数”。

4. 若表达式合法，则最后栈中只会留下一个元素，就是最终结果。否则表达式不合法。

中缀转前缀的手算步骤：

1. 确定中缀表达式中各个运算符的运算顺序。(运算顺序不唯一，因此对应的后缀表达式也不唯一)

   为了使手算步骤和机算步骤相同，规定：只要右边的运算符能先计算，就优先算右边的。(可保证运算顺序唯一)

2. 选择下一个运算符，按照「运算符，左操作数，右操作数」的方式组合成一个新的操作数。(看成一个整体加入后续的转换步骤中)

3. 如果还有运算符没被处理，就继续步骤$2$。

前缀表达式的计算：

1. 从右往左扫描下一个元素，直到处理完所有元素。

2. 若扫描到操作数则压入栈，并回到步骤1；否则执行步骤3。

3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1。

   先出栈的是“左操作数”。

中缀表达式的计算：

1. 初始化两个栈，操作数栈和运算符栈。

2. 从左到右扫描各个元素，直到末尾。可能遇到三种情况：

   • 遇到操作数：压入操作数栈。

   • 遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并计算，直到弹出“(”为止。

   • 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并计算，若碰到“(”或栈空则停止。之后再把当前运算符入栈。

     每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈。先弹出的操作数是右操作数。

3. 按上述方法处理完所有字符后，将运算符栈中剩余运算符依次弹出，并计算。

4. 最后操作数栈中只剩下一个操作数，即为最终结果。

栈在递归中的应用

若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。太多层递归可能会导致栈溢出。递归模型不能是循环定义的，其必须满足下面的两个条件：

• 递归表达式(递归体)。
• 边界条件(递归出口)。

在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储。可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。

队列的应用

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。

队列在计算机系统中的应用非常广泛，以下仅从两个方面来简述队列在计算机系统中的作用：

• 解决主机与外部设备之间速度不匹配的问题。如数据缓冲区中所存储的数据就是一个队列。(先进先出)
• 解决由多用户引起的资源竞争问题。如按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把资源分配给队首请求的用户使用。

特殊矩阵的压缩存储

数组是由$n(n\geq1)$个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在$n$个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。数组一旦被定义，其维数和维界就不再改变。一个数组的所有元素在内存中占用一段连续的存储空间。

一维数组$A[0...n-1]$的存储结构关系式为$\large LOC(a_i)=LOC(a_0)+i\times L\quad(0\leq i\leq n)$。$L$是每个数组元素所占的存储单元。

对于多维数组，有两种映射方法：

• 按行优先：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组的行下标与列下标的范围分别为$[0,h_1]$与$[0,h_2]$，则存储结构关系式为$\large LOC(a_{i.j})=LOC(a_{0,0})+[i\times(h_2+1)+j]\times L$。
• 按列优先：存储结构关系式为$\large LOC(a_{i.j})=LOC(a_{0,0})+[j\times(h_1+1)+i]\times L$。

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

对称矩阵：若对一个$n$阶方阵$A[1...n][1...n]$中的任意一个元素$a_{i,j}$，都有$a_{i,j}=a_{j,i}~(1\leq i,j\leq n)$，则称其为对称矩阵。对于一个$n$阶方阵，其中的元素可以划分为$3$个部分，即上三角区、主对角线和下三角区。上三角区的所有元素和下三角区的对应元素相同，将对称矩阵$A[1...n][1...n]$存放在一维数组$B[n(n+1)/2]$中，即元素$a_{i,j}$存放在$b_k$中。只存放下三角部分(含主对角)的元素。元素下标之间的对应关系如下：

三角矩阵：(矩阵行列号从$1$开始，数组的下标从$0$开始)

• 下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵$A[1...n][1...n]$压缩存储在$B[n(n+1)/2+1]$中。元素下标之间的对应关系如下：

• 上三角矩阵中，下三角区的所有元素均为同一常量。将上三角矩阵$A[1...n][1...n]$压缩存储在$B[n(n+1)/2+1]$中。元素下标之间的对应关系如下：

三对角矩阵：对角矩阵也称带状矩阵。对于$n$阶方阵$A$中的任一元素$a_{ij}$，当$|i-j|>1$时，有$a_{ij}=0(1\leq i,j\leq n)$，则称为三对角矩阵。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的$3$条对角线的区域，其他区域的元素都为零。三对角矩阵$A$也可以采用压缩存储，将$3$条对角线上的元素按行优先方式存放在一维数组$B$中，且$a_{1,1}$存放于$B[0]$中。元素下标之间的对应关系如下：

稀疏矩阵：矩阵中非零元素的个数$t$，相对矩阵元素的个数$s$来说非常少，即$s\gg t$的矩阵称为稀疏矩阵。将非零元素及其相应的行和列构成一个三元组(行标，列标，值)，然后按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。