受限线性表

栈（Stack，后进先出，LIFO）

栈的定义

栈（Stack）：是只允许一端进行插入和删除操作的线性表。

栈顶（Top）：栈允许插入删除的一端。
栈底（Bottom）：栈中不允许插入删除的一端
特点：后进先出（Last In First Out，LIFO）。

栈的数学性质（了解）：$n$个不同元素进栈，出栈的不同排列数为$\frac{1}{n + 1}C_{2n}^{n}$。该公式又称卡特兰（Catalan）数。

栈的基本操作

InitStack(&Stack)：初始化一个空栈。

Push(&Stack, DataType)：进栈，若栈未满，将DataType加入栈中使之成为新栈顶。

Pop(&Stack, &DataType)：出栈，若栈非空，弹出栈顶元素并用DataType返回。

GetTop(Stack, &DataType)：读取栈顶元素，若栈非空，用DataType返回栈顶元素。

DestroyStack(&Stack)：销毁栈，释放栈占用的存储空间。
顺序栈

顺序栈的定义
顺序栈：采用顺序存储的栈称为顺序栈，顺序栈利用一组地址连续的存储单元存放栈的数据元素，同时附加一个top指针指示当前栈顶元素的位置。
顺序栈的存储类型描述
```C
define MaxSize 50

typedef struct DNode {
// 数据域
DataType data[MaxSize];
// 栈顶指针
int top;
} SequeenStack;

**栈顶指针**：Stack.top，初始时设置为Stack.top = -1；
**栈顶元素**：Stack.data[Stack.top]；
**进栈操作**：栈不满时，栈顶指针加1，送值到栈顶元素；
**出栈操作**：栈非空时，先去栈顶元素值，再将栈顶指针减1；
**栈空条件**：Stack.top == -1；
**栈满条件**：Stack.top == MaxSize - 1；
**栈长**：Stack.top + 1；
顺序栈的入栈操作受数组上界约束，当栈的最大使用空间不足时，有可能导致上溢。
> 注意：有的教辅资料初始时将Stack.top = 0，相当于规定top指针指向栈顶元素的下一个存储单元。在使用时需注意，栈和队列的判空、判满条件和具体实现会因实践给定条件而有所不同，在使用时需注意理解其思想，而不是盲目照搬代码。
#### 顺序栈的基本运算
> 以下示例代码皆为Stack.top = -1的C语言示例代码，若Srack.top = 0，则对应条件也会发生变化，请灵活应对。
##### 初始化
```C
/**
 * 初始化顺序栈
 * @param Stack 
 */
void InitStack(SequeenStack *Stack) {
    Stack->top = -1;
}

栈判空

/*
 * 顺序栈判空
 */
bool StackEmpty(SequeenStack Stack) {
    if (-1 == Stack.top) {
        // 栈空
        return true;
    } else {
        // 非空
        return false;
    }
}

进栈

/**
 * 进栈
 * @param Stack 
 * @param data 
 * @return 
 */
bool Push(SequeenStack *Stack, DataType data) {
    if (MaxSize - 1 == Stack->top) {
        // 栈满，报错
        return false;
    } else {
        Stack->data[++Stack->top] = data;
        return true;
    }
}

出栈

/**
 * 出栈
 * @param Stack 
 * @param data 
 * @return 
 */
bool Pop(SequeenStack *Stack, DataType *data) {
    if (-1 == Stack->top) {
        // 栈空，报错
        return false;
    } else {
        *data = Stack->data[Stack->top--];
        return true;
    }
}

读取栈顶元素

/**
 * 读取栈顶元素
 * @param Stack 
 * @param data 
 * @return 
 */
bool GetTop(SequeenStack Stack, DataType *data) {
    if (-1 == Stack.top) {
        // 栈空，报错
        return false;
    } else {
        *data = Stack.data[Stack.top--];
        return true;
    }
}

共享栈（顺序栈推广）

为有效利用数组空间，利用栈底位置相对不变的特点，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分布设置在共享空间的两端。
共享栈
0号栈空：top0 = -1；
1号栈空：top1 = -1；
栈满：top1 - top0 = 1；

链栈

链栈的定义

链栈：采用链式存储的栈称为链栈，通常采用单链表实现，规定所有的操作都是在单链表的表头进行的。

优点：
- 便于多个栈共享存储空间和提高效率；
- 不存在栈满上溢的情况。
  链栈的存储类型描述
```
typedef struct Node {
// 数据域
DataType data;
// 指针域
struct Node * next;
} LinkStack;
```
  链栈的操作和链表类似，入栈和出栈的操作都在表头进行，可参考单链表的实现学习其基本运算。
  队列（Queue，先进先出，FIFO）
  
  队列的定义
  队列（Queue）：简称队，只允许在表的一端进行插入，另一端进行删除的受限线性表。
  
  队头（Front）：允许删除出队的一端，又称队首。
  队尾（Rear）：允许插入入队的一端。
  特点：先进先出（First In First Out，FIFO）。
  可以类比排队来学习队列的思想。
  队列的基本操作
InitQueue(&Queue)：初始化一个空队列。
EnQueue(&Queue, DataType)：入队，若队列为空返回true，否则返回false。
DeQueue(&Queue, &DataType)：出队，若队列非空，删除队头元素，并用DataType返回。
GetHead(Queue, &DataType)：读取队头元素，若队列非空，则将队头元素用DataType读取返回。
顺序队列

顺序队列的定义
顺序队列：分配一块连续的存储单元存放队列中的元素，并附加两个指针，队头指针front指向队头元素和队尾指针rear指向队尾元素。
顺序队列的存储类型描述
```C
define MaxSize 50

typedef struct {
// 数据域
DataType data[MaxSize];
// 栈顶指针
int front, rear;
} SequeenQueue;

**初始状态（队空条件）**：Queue.front = Queue.rear = -1；
**入队操作**：队不满时，先将值放到队尾元素，再将队尾指针加1；
**出队操作**：队不空时，先取队头元素，再将队头指针加1；
在队列中，队空队列做出队操作会产生“下溢”；当队列满时，执行入队操作会产生“上溢”。但是，如果当前队尾指针等于数组的上界时（即Queue.rear = MaxSize - 1）时，即使队列不满，再做入队操作也会引起溢出，我们把这种现象称为“假上溢”，产生这种现象的原因是被删元素的空间在该元素被删除以后就使用不到了。
<div align="center">
    <img src="https://ucc.alicdn.com/images/user-upload-01/289e8c91352343cc86e4ebda775b5363.png" alt="顺序队列假溢出" />
</div>

### 循环队列
#### 循环队列的定义
**循环队列**：为了克服顺序队列假溢出的缺点，通常采用的方法是：设想队列是一个首尾相接的圆环，即Queue.data[0]接在Queue.data[MaxSize - 1]之后，我们将这种意义下的队列称为循环队列。可以利用取余运算（%）来实现顺序队列。
**初始时**：Queue.front = Queue.rear = MaxSize - 1；
**队首指针加1**：Queue.front = (Queue.front + 1） % MaxSize；
**队尾指针加1**：Queue.rear = (Queue.rear + 1） % MaxSize；
**队列长度**：(Queue.rear + MaxSize - Queue.front) % MaxSize；
#### 循环队列队空队满判断方式
在循环队列中，通过Queue.front = Queue.rear无法区分队空还是队满，为了区分队空还是队满，有三种处理方式：
- 牺牲一个存储单元来区分队空和队满，这是一种普遍的做法，约定以“队头指针在队尾指针的下一个位置作为队满的标志”
    - 队满条件：(Queue.rear + 1） % MaxSize = Queue,front；
    - 队空条件：Queue.front = Queue.rear；
    - 队列中元素的个数：(Queue.rear + MaxSize - Queue.front) % MaxSize；
- 增设表示元素个数的数据成员size
    - 队满条件：Queue.size = MaxSize；
    - 队空条件：Queue.size = 0；
- 增设tag数据成员
    - 队满条件：tag等于1时，若因插入导致Queue.front = Queue.rear，则为队满；
    - 队空条件：tag等于0时，若因删除导致Queue.front = Queue.rear，则为队空；
#### 循环队列的基本运算
##### 初始化
```C
/**
 * 初始化队列
 * @param Queue
 */
void InitQueue(SequeenQueue *Queue) {
    Queue->front = MaxSize - 1;
    Queue->rear = MaxSize - 1;
}

判断队空

/**
 * 判断队空
 * @param Queue
 * @return
 */
bool QueueEmpty(SequeenQueue *Queue) {
    if (Queue->rear == Queue->front) {
        return true;
    } else {
        return false;
    }
}

入队

/**
 * 入队
 * @param Queue
 * @param data
 * @return
 */
bool EnQueue(SequeenQueue *Queue, DataType data) {
    if (Queue->front == (Queue->rear + 1) % MaxSize) {
        // 队满上溢
        return false;
    } else {
        Queue->rear = (Queue->rear + 1) % MaxSize;
        Queue->data[Queue->rear] = data;
        return true;
    }
}

出队

/**
 * 出队
 * @param Queue
 * @param data
 * @return
 */
bool DeQueue(SequeenQueue *Queue, DataType *data) {
    if (Queue->front == Queue->rear) {
        // 队空
        return false;
    } else {
        Queue->front = (Queue->front + 1) % MaxSize;
        *data = Queue->data[Queue->front];
        return true;
    }
}

链队

链队的定义

链队：队列的链式表示称为链队列，链队列实践上时一个同时带有队头指针和队尾指针的单链表。队头指针指向头结点，队尾指针指向尾结点。

链队的存储类型描述

// 链式队列结点（单链表）
typedef struct Node {
    // 数据域
    DataType data;
    // 指针域
    struct Node * next;
} LinkNode;

// 链式队列
typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

链队的基本运算

初始化

/**
 * 初始化链队
 * @param Queue
 */
void InitQueue(LinkQueue *Queue) {
    // 申请头结点
    Queue->front = (LinkNode *) malloc(sizeof(LinkNode));
    Queue->front->next = NULL;
    // 尾指针也指向头结点
    Queue->rear = Queue->front;
}

队列判空

/**
 * 判队空
 * @param Queue
 * @return
 */
bool QueueEmpty(LinkQueue *Queue) {
    if (Queue->front == Queue->rear) {
        return true;
    } else {
        return false;
    }
}

入队

/**
 * 入队
 * @param Queue
 * @param data
 */
void EnQueue(LinkQueue *Queue, DataType data) {
    // 新结点插入尾端
    Queue->rear->next = (LinkNode *) malloc(sizeof(LinkNode));
    // 令尾指针指向新结点
    Queue->rear = Queue->rear->next;
    Queue->rear->data = data;
    Queue->rear->next = NULL;
}

出队

/**
 * 出队
 * @param Queue 
 * @param data 
 * @return 
 */
bool DeQueue(LinkQueue *Queue, DataType *data) {
    if (Queue->front == Queue->rear) {
        // 队空
        return false;
    } else {
        // 定义结点，指向被删除的头结点
        LinkNode  *p = Queue->front->next;
        *data = p->data;
        // 使头结点的next指针指向被删除结点的下一个指针，避免链表悬空
        Queue->front->next = p->next;
        if (Queue->rear == p) {
            // 若被删除结点是队尾指针，则链队列长度为1，删除结点后，链队列置空
            Queue->rear = Queue->front;
        }
        // 释放被删除指针的空间
        free(p);
        return true;
    }
}

双端队列

双端队列的定义

双端队列：双端队列是指两端都允许入队和出队操作的队列。队列的两端分别称为前端和后端。
输出受限的双端队列：允许在一端进行入队和出队操作，另一端只允许入队的双端队列。
输入受限的双端队列：允许在一端进行入队和出队操作，另一端只允许出队的双端队列。

线性表推广

数组和特殊矩阵

数组的定义

数组：数组是由$n(n \ge 1)$个相同类型的数据元素构成的有限序列，每个元素在$n$个线性关系中的序号称为该元素的下标（下标由0开始），下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表，元素由值与一对下标构成；二维数组也可看做由一维数组与一对下标元素定义的一维数组，这时每个数据元素受到两个下标关系约束，数据元素之间在每一个关系中仍具有线性结构，整体结构呈非线性。例如：二维数组：
$$ A_{m \times n} = \left[ \begin{array}{c} a_{00} & a_{01} & \cdots & a_{0, n - 1} \\ a_{10} & a_{11} & \cdots & a_{1, n - 1} \\ \vdots & \vdots & & \vdots \\ a_{m - 1, 0} & a_{m - 1, 1} & \cdots & a_{m - 1, n - 1} \end{array} \right] $$
又可以写成：
$$ A_{m \times n} = [[a_{00}, a_{01}, \cdots, a_{0, n - 1}], [a_{10}, a_{11}, \cdots, a_{1, n - 1}], \cdots, [a_{m - 1, 0}, a_{m - 1, 1}, \cdots, a_{m - 1, n - 1}]] $$
或：
$$ A_{m \times n} = [[a_{00}, a_{10}, \cdots, a_{m - 1, 0}], [a_{01}, a_{11}, \cdots, a_{m - 1, 1}], \cdots, [a_{0, n - 1}, a_{1, n - 1}, \cdots, a_{m - 1, n - 1}]] $$
可以发现，当数组维数为1时，数组是一种元素数目固定的线性表；当维数大于1时，数组可以看做是线性表的推广。推广可知，一个三维数组可以看成是其元素由二维数组来定义的特殊线性表；以此类推，n维数组是由n - 1维数组定义的，每个数组元素收到n个下标的约束。

数组的性质与运算

数组的性质

数据元素数目固定。一旦定义了数组结构，其元素数目不再发生变化。
数据元素具有相同的类型。
数据元素的下标关系具有上下界的约束，并且下标有序。
数组的运算
对于数组，通常只有两种运算：
给定一组下标，存取相应的数据元素。
给定一组下标，修改相应数据元素中的某个数据项的值。
数组的存储结构
大多数计算机语言都提供了数组数据类型，逻辑意义上的数组可采用计算机语言提供的数组数据类型或者顺序表来进行存储。
因为存储单元是一维结构，而数组是多维的结构，所以使用一组连续的存储单元存放数组就必然有个次序约定问题。二维数组的顺序存储可分为：以行为主序的优先存储和以列为主序的优先存储。由于多维数组的下标不止两个，因此存储时规定了以下标顺序为主序的优先存储和逆下标顺序为主序的优先存储。
一维数组
以一维数组$A[0, \cdots, n - 1]$为例，其存储结构关系式为：
$$ Loc(a_i) = Loc(a_0) + i \times L(0 \le i \le n) $$
其中，L是每个数组元素所占的存储单元。
多维数组
以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。

注意下列表达中，row, col, x, y, z皆表示对应维度的个数，例如row表示二维数组行有row个元素。
i, j, k表示在当前数组的位置，取值范围是由[0, 对应值-1]，数组每个维度皆由下标0开始

列如在$A_{row \times col}$的数组中，第$a_{i, j}$个元素，其前面已存放了$i$行共$i \times col$个元素，在下标为$i$行中其前面已存放$j$个元素，因此可推到二维数组的行优先存储结构关系式为：
$$ Loc(a_{i, j}) = Loc(a_{0, 0}) + [i \times col + j] \times L $$
同理可得，列优先存储结构关系式为：
$$ Loc(a_{i, j}) = Loc(a_{0, 0}) + [j \times row + i] \times L $$
推广到三维数组$A_{x \times y \times z}$，按行优先顺序存储结构关系式为：
$$ Loc(a_{i, j, k}) = Loc(a_{0, 0, 0}) + [i \times y \times z + j \times z + k] \times L $$
按列优先顺序存储结构关系式为：
$$ Loc(a_{i, j, k}) = Loc(a_{0, 0, 0}) + [k \times y \times x + j \times x + i] \times L $$

特殊矩阵的压缩存储

特殊矩阵：有许多相同矩阵元素或零元素的矩阵，并且这些矩阵元素或零元素的分布有一定规律性的矩阵。
压缩存储：对多个相同值只分配一个空间，对零元素不分配空间。

对称矩阵

对称矩阵：在n阶矩阵中，若A中的元素满足$a_{ij} = a_{ji}(0 \le i, j \le n - 1)$，则称A是对称矩阵。
由于对称矩阵的元素关于对角线对称，因此在存储时只需存储矩阵中上三角或下三角中的元素即可。

假如我们只存储下三角中的元素，按照行优先关系存储，则原矩阵$A_{row \times col}$中的元素$a_{ij}$与压缩后的矩阵$B[k]$有如下关系：第一行有1个元素，第二行有2个元素，$\cdots$，下标$i$行的上一行有$i$个元素（这里$i$为元素$a$的下标，从0开始计数，因为对称矩阵，下标为$i$行的上面的矩阵也是对称的，因为下标为从0开始计数，所以下标为$i$行实际上为第$i + 1$行，所以其上有$i$行，对应属于下三角的有$i$列，所以上一行的列数和行数相等为$i$，所以下标$i$行的上一行有$i$个元素），所以其前共有$\frac{(1 + i) \times i}{2}$个元素，在下标为$i$行前共有$j$列元素，所以下三角矩阵中，可得$A[k]$和$a_{i, j}$有对应关系如下：
$$ k = \frac{(1 + i) \times i}{2} + j, (i \ge j) $$
在上三角矩阵中，由于有$a_{ij} = a_{ji}$，所以
$$ k = \frac{(1 + j) \times j}{2} + i, (i < j) $$
在使用公式时，注意对应三角区域和排序方式。

三角矩阵

以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
上三角矩阵是指矩阵的下三角（不含对角线）中元素为常熟的n阶矩阵，下三角矩阵与之相反。

三角矩阵的常数区的值只需要一个存储单元即可表示，实际上只需要考虑非常数区的三角区内容的存储即可。类比对称矩阵，也只需考虑一个三角区的内容存储，所以三角矩阵的三角区可以参考对称矩阵的存储方法，然后再数组最后加一个元素表示常数区的值。因为三角区的元素总数为：$\frac{(1 + n) \times n}{2}$，其下标范围为$[0, \frac{(1 + n) \times n}{2} - 1]$，所以常数区元素对应下标为：$\frac{(1 + n) \times n}{2}$。即
$$ \begin{equation*} k = \begin{cases} \frac{(1 + i) \times i}{2} + j, (i \ge j)\\ \frac{(1 + n) \times n}{2}, (i < j) \end{cases} \end{equation*} $$
注意：该公式是以下三角矩阵和行优先推导出的公式

对角矩阵

对角矩阵：再对角矩阵中，所有非零元素都集中在以对角线为中心的带状区域中，所以又称带状矩阵。

最简单的对角矩阵为只在主对角线上含有非零元素的对角矩阵，简单的可以推导出其$k = i$。

次之则为三对角矩阵，三对角矩阵是首行和尾行只有2个元素，其余行皆有3个元素，在更好的推导三对角矩阵的存储关系式，我们在第一行的前面和最后一行的后面默认加一个元素，这样每行就都有三个元素。
下标为$i$的前面共有$i$行，有$i \times 3$个元素。
下标为$i$的一行，因为为对角矩阵，所以主对角线上列减行等于0，其左右两边的元素列减行表示其与主对角线元素的距离，在三对角矩阵中，让三个元素分别列减行则为：$-1, 0, 1$，其分别是下标为$i$行的第$1, 2, 3$个元素，所以给元素加2，使其列减行变换后的值为$0, 1, 2$（表示第$j$列前有几个非0元素，注意理解这里为什么是$0, 1, 2$而不是$1, 2, 3$），即$j - i + 1$。
将$i \times 3$与$j - i + 1$相加得$2i + j + 1$，得到变化后的三对角矩阵的关系式，因为在矩阵中，实际上第一行首行前面的元素是不存在的，所以数组需左移一位，所以三对角矩阵的存储关系式为：
$$ 2i + j $$
推广到$n(n > 1)$对角矩阵得：
$$ ni + j - i + \frac{n - 1}{2} - 1 $$

稀疏矩阵

之前的特殊矩阵中非零元素的分布都是有规律的，所以可以找到矩阵元素与一维数组下标之间的关系，还有一类矩阵，零元素较多，但没有分布没有规律，这类矩阵就是稀疏矩阵。

稀疏矩阵的定义

稀疏矩阵：矩阵中有非零元素和较多的零元素，但非零元素的分布没有任何规律的矩阵。
因为矩阵的非零元素没有规律，且非零元素远小于零元素的个数，所以用数组之间存储矩阵会浪费较多的空间，为了存储非零元素，可以通过其辅助信息，快速定位非零元素。一般使用三元组（行号，列号，值）来存储稀疏矩阵的值

稀疏矩阵结点类型描述

// 最大非零元素个数
#define NonZeroMaxSize

// 三元组结点
typedef struct {
    // 三元组结点对应稀疏矩阵的行号和列号
    int row, col;
    // 非零元素值
    DataType value;
} Node;

// 三元组表
typedef struct {
    // 三元组表行号，列号，和非零元素个数
    int row, col, nonZereNum;
    // 数据域
    Node data[NonZeroMaxSize];
} Spmatrix;

例如：下面的稀疏矩阵：
$$ M = \left[ \begin{array}{c} 4 & 0 & 0 & 0 \\ 0 & 0 & 6 & 0 \\ 0 & 9 & 0 & 0 \\ 0 & 23 & 0 & 0 \\ \end{array} \right] $$
可以表示为三元组：
| i | j | value|
| --- | --- | --- |
| 0 | 0 | 4 |
| 1 | 2 | 6 |
| 2 | 1 | 9 |
| 3 | 1 | 23 |

数据结构-栈、队列和数组

受限线性表

栈（Stack，后进先出，LIFO）

栈的定义

栈的基本操作

顺序栈

顺序栈的定义

顺序栈的存储类型描述

define MaxSize 50

栈判空

进栈

出栈

读取栈顶元素

共享栈（顺序栈推广）

链栈

链栈的定义

链栈的存储类型描述

队列（Queue，先进先出，FIFO）

队列的定义

队列的基本操作

顺序队列

顺序队列的定义

顺序队列的存储类型描述