线性数据结构

• 1: 栈
• 2: 队列
• 3: 栈和队列的应用
• 4: 数组和特殊矩阵

# 栈、队列和数组

## 栈和队列基本概念

## 栈和队列的顺序存储结构

## 栈和队列的链式存储结构

## 多维数组的存储

## 特殊矩阵的压缩矩阵

## 栈、队列和数据的应用

1 - 栈

定义

栈是一个元素的集合，加入元素的操作叫做“压栈”（push），而移除元素的操作叫做“出栈”（pop）。它遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后被压入栈的元素是第一个被弹出的元素。

基本操作

• push(element): 将元素添加到栈的顶部。
• pop(): 移除并返回栈顶的元素。如果栈为空，这个操作可能会抛出一个错误或返回特定的值（例如 null 或 undefined），具体取决于实现。
• peek() 或 top(): 返回栈顶的元素但不移除它。这只是一个查看操作，栈的内容不会改变。如果栈为空，这个操作可能会抛出一个错误或返回特定的值。
• isEmpty(): 判断栈是否为空。如果栈为空，返回 true；否则返回 false。
• size() 或 length(): 返回栈中元素的数量。

实现

栈的实现方式有两种，顺序栈和链式栈。 顺序栈是在顺序表的基础上实现栈结构， 链式栈是在链表的基础上实现栈结构。

顺序栈

顺序栈是使用数组来实现的栈，利用数组的索引来模拟栈的操作。 与普通的线性表不同，栈的操作被限制在表的一端进行，这一端被称为栈顶 (Top)，另一端被称为栈底 (Bottom)。

顺序栈的关键在于栈顶指针，栈顶指针是一个整数变量，用于指示栈顶元素在数组中的位置。其值的变化直接反映了栈中元素的变化。 当栈空时，一般将栈顶指针设置为 1，当栈满时，栈顶指针指向数组中的最后一个元素。

当元素入栈时，将栈顶指针向后移动一个位置、然后放置新元素即可。当元素出栈时，需要将栈顶指针向前移动一个位置。 当然，入栈和出栈时需要保证数组不满或者不空。

• 栈的定义
• 初始化
• 入栈
• 出栈
• 获取栈顶元素
• 判断栈空

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构
typedef struct {
    int data[MAX_SIZE]; // 使用数组存储数据
    int top;            // 栈顶指针
} SeqStack;

// 初始化栈
SeqStack* initStack() {
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    // 栈顶指针初始化为 -1，表示栈为空
    stack->top = -1; 
    return stack;
}

// 入栈操作
bool push(SeqStack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return false;
    }
    // 先移动栈顶指针，再存放元素
    stack->data[++stack->top] = value;
    return true;
}

// 出栈操作
bool pop(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    // 先取出元素，再移动栈顶指针
    *value = stack->data[stack->top--];
    return true;
}

// 获取栈顶元素
bool peek(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top];
    return true;
}

// 判断栈是否为空
// 当栈中没有元素时，栈顶指针通常指向一个特殊的位置，例如 -1。
bool isEmpty(SeqStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
// 当栈顶指针指向数组中的最后一个元素时，说明栈已经满了
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

链式栈

栈的链式存储结构利用单链表来实现栈的功能。为了保证入栈（Push）和出栈（Pop）操作的时间复杂度为 O(1)，通常将链表的头部作为栈顶。

链式栈的栈顶指针指向链表的首部，如果栈为空的话，栈顶指针指向 NULL。

• 栈的定义
• 初始化
• 入栈
• 出栈
• 获取栈顶元素
• 判断栈空

// 定义链式栈的节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式栈的结构
typedef struct {
    Node* top;
} LinkedStack;

// 初始化栈
LinkedStack* initStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->top = NULL; // 栈顶指针初始化为 NULL，表示栈为空
    return stack;
}

// 入栈操作
void push(LinkedStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(!newNode) {
        printf("Failed to allocate memory for new node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    Node* temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    return true;
}

// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->top->data;
    return true;
}

// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->top == NULL;
}

2 - 队列

定义

队列是一种遵循先入先出 (FIFO, First In First Out) 原则的线性数据结构。元素在队尾添加，在队首删除。

基本操作

• enqueue(element): 将元素添加到队列的尾部。
• dequeue(): 从队列的头部移除并返回元素。如果队列为空，此操作可能会返回特定的值或引发错误。
• front() 或 peek(): 返回队首的元素但不移除它。
• isEmpty(): 判断队列是否为空。
• size(): 返回队列中元素的数量。

实现

顺序队列

顺序队列通常是指使用固定大小的数组来存储队列中的元素。在顺序队列中，通常有两个指标：一个是队头（front），另一个是队尾（rear）。当插入（入队）或删除（出队）元素时，这两个指标会移动。

顺序队列有一个明显的问题：随着时间的推移，队列中的元素可能向数组的末尾移动，即使队列并不满，也可能无法再插入新的元素，因为队尾已经达到了数组的末尾。这种现象称为"假溢出"。

循环队列

为了解决上述问题，可以使用循环队列（也称为环形队列）。循环队列是顺序队列的一个变种，它把数组视为一个循环的结构。当队尾指标达到数组的最后一个位置并且还需要进一步移动时，它会回到数组的起始位置。

需要注意的是，在循环队列中需要牺牲一个存储单元以区分队空和队满的情况。

• 当 front == rear 时，队列为空
• 当 (rear + 1) % size == front 时，队列为满

• 定义
• 入队
• 出队
• 首尾元素
• 判断队列空或满

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue* q) {
    q->front = q->rear = 0;
}

// 入队操作
bool enqueue(CircularQueue* q, int value) {
    if (isFull(q)) return false;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

// 出队操作
bool dequeue(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}

// 获取队首元素
bool front(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    return true;
}

// 获取队尾元素
bool rear(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE];
    return true;
}

// 判断队列是否为空
bool isEmpty(CircularQueue* q) {
    return q->front == q->rear;
}

// 判断队列是否满
bool isFull(CircularQueue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

链式队列

链式队列是使用链表结构来实现的队列。它充分利用了链表的动态性质，允许队列在运行时动态地增长或缩小。链式队列通常有两个指针：一个指向队头，另一个指向队尾。

链式队列通常使用一个简单的单链表来实现，但与普通的单链表不同的是，链式队列有两个指针：一个指向链表的头部（队头），另一个指向链表的尾部（队尾）。

• 定义
• 入队
• 出队
• 首尾元素
• 判断队列空

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front, *rear;
} LinkedQueue;

// 初始化队列
void initLinkedQueue(LinkedQueue* q) {
    q->front = q->rear = NULL;
}

// 入队操作
void enqueueLinked(LinkedQueue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if(isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队操作
bool dequeueLinked(LinkedQueue* q, int* value) {
    if (isEmpty(q)) return false;
    Node* temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;  // 当队列中最后一个元素被出队后
    free(temp);
    return true;
}

// 获取队首元素
bool front(LinkedQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->front->data;
    return true;
}

// 获取队尾元素
bool rear(LinkedQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->rear->data;
    return true;
}

// 判断队列是否为空
bool isEmpty(LinkedQueue* q) {
    return q->front == NULL && q->rear == NULL;
}

3 - 栈和队列的应用

表达式种类

前序表达式（Preorder，也叫做波兰表示法）、中序表达式（Infix）和后序表达式（Postorder, 也称为逆波兰表示法）都是二叉树的遍历策略，通常用于算术表达式的表示。不同的表示方法对操作符和操作数的顺序有不同的规定。

上图是表达式 (A + B) * C 对应的二叉树，前序、后序表达式分别是对这棵树的 前序遍历和后序遍历。

中序表达式求值

中序表达式求值涉及到两个主要的数据结构：操作符栈与操作数栈。其核心思路是逐个读取中序表达式的字符，根据字符的类型（操作数、操作符、括号）进行不同的处理，最终得到表达式的值。

1. 初始化两个栈：
   • 操作数栈：用来存储数字。
   • 操作符栈：用来存储操作符和左括号。
2. 逐个读取中序表达式的字符：
   • 如果是 操作数（数字），则直接压入操作数栈。
   • 如果是 左括号，则直接压入操作符栈。
   • 如果是 右括号，则：
     • 从操作符栈中弹出一个操作符。
     • 从操作数栈中弹出所需的操作数。
     • 执行该操作符对应的运算。
     • 将结果压入操作数栈。
     • 重复以上步骤，直到从操作符栈中弹出一个左括号。
   • 如果是操作符（如+、-、*、/等）：
     • 如果操作符栈为空，或栈顶是左括号，或当前操作符优先级高于栈顶操作符的优先级，则直接压入操作符栈。
     • 否则：
       • 从操作符栈中弹出一个操作符。
       • 从操作数栈中弹出所需的操作数。
       • 执行该操作符对应的运算。
       • 将结果压入操作数栈。
       • 重复以上步骤，直到满足上述的压栈条件。
3. 处理完所有字符后：
   • 如果操作符栈不为空，则：
     • 从操作符栈中弹出一个操作符。
     • 从操作数栈中弹出所需的操作数。
     • 执行该操作符对应的运算。
     • 将结果压入操作数栈。
     • 重复以上步骤，直到操作符栈为空。
4. 得到结果：
   • 此时，操作数栈中仅存一个数字，这就是整个中序表达式的值。

以表达式 3 + (5 * 2 - 8) 说明计算过程：

后序表达式求值

后序表达式求值主要依赖一个操作数栈。其核心思路是逐个读取后序表达式的元素，并根据元素的类型（操作数或操作符）进行处理。

1. 初始化一个操作数栈：
   • 用于存储后序表达式中的数字。
2. 逐个读取后序表达式的元素：
   • 如果是操作数，则直接压入操作数栈。
   • 如果是操作符（如+、-、*、/等）：
     • 从操作数栈中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
     • 根据操作符执行相应的运算。
     • 将计算结果压入操作数栈。
3. 完成后序表达式的读取：
   • 操作数栈中的顶部元素即为整个后序表达式的值。

以表达式 3 5 2 * 8 - + 说明计算过程：

中序转后序

将中缀表达式转换为后缀表达式的算法思想如下：

初始化一个操作符栈，从左向右开始扫描中缀表达式；

• 遇到数字时，加入后缀表达式；
• 遇到运算符时：
  • 若为 （，入栈；
  • 若为 ），则依次把栈中的运算符加入后缀表达式中，直到出现 （，从栈中删除 （；
  • 若为除括号外的其他运算符
    • 当其优先级高于除 （ 以外的栈顶运算符时，直接入栈；
    • 否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。

以中序表达式 a/b+(c*d-e*f)/g 为例，可以通过如下步骤将其转换为后续表达式：

入栈出栈序列

入栈出栈是常考的问题，这类问题的核心可以被总结为以下两种范式：

• 给定一个入栈序列，判断哪些出栈序列是不可能的？
• 给定一个入栈序列，其出栈序列序列有多少种？

这里给出这两个常见问题的解答。

不可能的出栈序列

给定一个入栈序列，其出栈序列可能有很多种，因为一个元素的出栈时间比较灵活，比如它可以一入栈马上出栈，也可以等一会再出栈。要辨别不可能的出栈系列，需要抓住关键规则：只有栈顶元素能够最先出栈。

也就是说，对于下图这种情况，A 被 B 压住了，在出栈序列中，A 一定在 B 的后面。如果某个出栈序列中 A 在 B 的前面，则这种出栈序列是不可能出现的。

卡特兰数

假设有 $n$ 个不同元素（例如 $1,2,\cdots,n$），按某种顺序依次入栈，并且可以在任意时刻出栈，每个元素恰好入栈一次且出栈一次，求所有可能的出栈序列数。

这个问题可以用卡特兰数计算，首先给出卡特兰数的公式：

$$C_{n} = \frac{1}{n+1}\begin{pmatrix}2n \\ n\end{pmatrix}$$

这也是上述问题的答案，接下来解释一下为什么是卡特兰数：

我们将入栈操作记作 +1，出栈操作记作 -1，整个过程中有 $n$ 次入栈，$n$ 次出栈，总共有 $2n$ 个操作。我们要保证以下条件：

在任何时刻，入栈次数不得超过出栈次数。

这种操作方式正好对应于卡特兰数的关键特征，所以 $n$ 个入栈元素对应可能的出栈序列总数就是 $C_{n}$。

除了入栈出栈序列之外，卡特兰数也常常出现在以下场景中，这些问题与入栈出栈序列是等价的：

• 二叉树的计数：给定 $n$ 个不同节点，构造不同形态的二叉树个数为 $C_{n}$。
• 括号匹配：$n$ 对括号的合法匹配序列数为 $C_{n}$。例如，$n=2$ 时，合法序列为 ()() 和 (())。

4 - 数组和特殊矩阵

多维数组的存储

如果数组的第一个元素位于内存地址 $A$，且每个元素占用 $B$ 个字节，行列总数分别为 $R$ 和 $C$，那么数组的 $(i, j)$ 元素（其中 $i$ 是行号，$j$ 是列号）的内存地址可以计算为 $A + (i \times C + j) * B$。

例子：

在 C 语言中定义定义如下多维数组

int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

这个数组的内存布局可以视为一个一维数组，如下所示：

  +---------+---------+---------+---------+---------+---------+
  | a[0][0] | a[0][1] | a[0][2] | a[1][0] | a[1][1] | a[1][2] |
  +---------+---------+---------+---------+---------+---------+
0x100      0x104    0x108     0x10C     0x110     0x114

特殊矩阵的压缩存储

对称矩阵

什么是对称矩阵：对于矩阵$A$中的任意一个元素$a_{i, j}$都有 $a_{i, j} = a_{j ,i}$，

所以为了节省存储空间，可以使用一位数组$B$进行存储

如何计算对称矩阵中元素的下标

$A$ 中的元素 $a_{i, j}$ 在数组 $B$ 的下标

$$k = 1 + 2 + \cdots + (i-1) + j - 1 = i(i-1)/2+j-1$$

元素为

三角矩阵

• 下三角矩阵 是一个方阵，其主对角线及其以下（右下部分）的所有元素都不为零，而主对角线以上的所有元素都为零。
• 上三角矩阵  是一个方阵，其主对角线及其以上（左上部分）的所有元素都不为零，而主对角线以下的所有元素都为常数。

以上三角矩阵 $A$ 为例，上半部分元素首先按序存储在一位数组 $B$ 中，在最后一个位置添加一个元素，用于存储下三角位置对应的元素

$A$ 中的元素 $a_{i, j}$ 在数组 $B$ 的下标

$$k = n + (n+1) _ \cdots + (n-i+2) + (j-i+1) - 1 = (i-1)(2n-i+2)/2 + (j-i)$$

元素为

稀疏矩阵

稀疏矩阵（Sparse Matrix）是指在矩阵中大部分元素为零的矩阵。与之相对的是稠密矩阵（Dense Matrix），即大部分元素非零。

$$ A_{6 \times 7} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 6 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 7 & 4 \end{bmatrix} $$

由于稀疏矩阵的非零元素远少于零元素，存储整个矩阵（包括所有零元素）会浪费大量空间。因此，稀疏矩阵通常使用特定的数据结构（三元组表 和 十字链表）来高效存储和操作，只保存非零元素及其位置信息。

三元组表

三元组表用三个一维数组分别存储非零元素的行号、列号和数值。当然了，这里也可以使用一个结构体数组，两者都是一样的。

比如对于上文提到的 $A_{6 \times 7}$ 稀疏矩阵，可以采用以下的三元组进行存储：

十字链表

十字链表的核心思想是通过两个方向的链表（行方向和列方向）来组织非零元素，使得按行或按列访问矩阵元素都较为高效。

下图给出了一个十字链表的存储示例：

每一个十字链表中的元素结点都需要存储以下信息：行号（i）、列号（j）、元素值（value）、指向同一行下一个非零元素的指针（right）、指向同一列下一个非零元素的指针（down）。

此外，还需要为每一行（rhead）和每一列（chead）设置一个头节点，用于快速定位该行或该列的第一个非零元素。

三对角矩阵

三对角矩阵是一种特殊的稀疏矩阵，它除了主对角线外，只在其上下相邻的两条对角线上有非零元素，其余元素均为零。

由于仅有三条对角线是非零的，我们可以只存储这三条线来节省空间（从 $n^2$ 降为 $3n-2$ 个数字）。

一种常用存储方式是使用三个长度为 n 的数组：

• a[2...n]：下对角线（从第 2 行开始有值）
• b[1...n]：主对角线
• c[1...n-1]：上对角线（到第 n-1 行）