[数据启示录 02] 堆栈

堆栈（stack）是一种基于后进先出（LIFO，Last In First Out）原则的数据结构。它模拟了现实生活中的堆栈，类似于一摞盘子或一堆书。

堆栈有两个基本操作：入栈（push）和出栈（pop）。

1. 入栈（push）：将新元素添加到堆栈的顶部。新元素成为当前堆栈的最上面一个元素。
2. 出栈（pop）：从堆栈的顶部移除最上面的元素，并返回该元素的值。

除了这两个基本操作外，堆栈还可以支持其他常用操作，例如：

• 栈顶（top）：获取堆栈的顶部元素，但不移除它。
• 判空（isEmpty）：检查堆栈是否为空。
• 获取大小（size）：获取堆栈中元素的数量。

实际上，堆栈可以通过数组或链表来实现。

使用数组实现的堆栈称为顺序堆栈（array-based stack）。在顺序堆栈中，数组的末尾被用作栈顶，每次入栈操作都会将元素放置在数组末尾，而出栈操作则会从数组末尾移除元素。

使用链表实现的堆栈称为链式堆栈（linked stack）。在链式堆栈中，每个节点包含一个元素和一个指向下一个节点的引用。入栈操作将在链表头部插入新节点，而出栈操作则会移除链表头部的节点。

堆栈在计算机科学中有广泛的应用。例如，在编程中，堆栈常用于函数调用的过程中，每当一个函数被调用时，其相关信息（如参数、局部变量等）都会被压入堆栈中，当函数执行完毕后，这些信息又会被弹出堆栈。这种方式使得程序可以追踪函数的嵌套调用，并正确恢复执行状态。

堆栈还被用于解决许多其他问题，如括号匹配、表达式求值、深度优先搜索算法、回溯算法等。其简单性和高效性使得堆栈成为一种重要的数据结构。

堆栈的抽象数据描述

堆栈（stack）是一种抽象数据类型（ADT），用于描述具有后进先出（LIFO，Last In First Out）特性的数据结构。它定义了以下操作：

1. 初始化（Initialize）：创建一个空的堆栈。
2. 入栈（Push）：将一个新元素添加到堆栈的顶部。
3. 出栈（Pop）：从堆栈的顶部移除最上面的元素，并返回该元素的值。
4. 栈顶（Top）：获取堆栈的顶部元素，但不移除它。
5. 判空（IsEmpty）：检查堆栈是否为空。
6. 获取大小（Size）：获取堆栈中元素的数量。

这些操作定义了堆栈的基本行为和特点。使用这些操作，可以实现各种具体的堆栈实现，如基于数组或链表的实现。

[例] 如果三个字符按ABC顺序压入堆栈

• ABC的所有排列都可能

是出栈的序列吗？

• 可以产生CAB这样的序

列吗？

在递归的过程中，我们维护一个栈和一个指向原始字符序列的指针。如果当前栈顶元素与指针指向的元素相同，则可以将其出栈；否则，需要将指针指向的元素入栈。当原始字符序列中的所有元素都已经被入栈后，我们可以逐步将栈中的元素出栈，从而得到一种可能的出栈序列。

使用上述方法，我们可以得到所有可能的出栈序列。如果其中包含了以CAB为开头的序列，那么就说明CAB是一种可能的出栈序列。否则，就不能产生CAB这样的序列。

总结：按照ABC的顺序依次压入堆栈，其所有可能的出栈序列有6种，分别是ABC、ACB、BAC、BCA、CBA和CAB。因此，CAB是一种可能的出栈序列。

栈的顺序存储实现

#define MAXSIZE 100 // 定义栈的最大容量
typedef struct {
    ElementType data[MAXSIZE]; // 用数组存储栈元素
    int top; // 栈顶指针，指向当前栈顶元素的位置
} Stack;
// 初始化栈
void InitStack(Stack *S) {
    S->top = -1; // 初始化栈顶指针为-1，表示空栈
}
// 判断栈是否为空
int IsEmpty(Stack *S) {
    return (S->top == -1);
}
// 判断栈是否已满
int IsFull(Stack *S) {
    return (S->top == MAXSIZE - 1);
}
// 入栈操作
void Push(Stack *S, ElementType item) {
    if (IsFull(S)) {
        printf("Stack is full. Cannot push element %d.\n", item);
    } else {
        S->data[++(S->top)] = item;
    }
}
// 出栈操作
ElementType Pop(Stack *S) {
    if (IsEmpty(S)) {
        printf("Stack is empty. Cannot pop element.\n");
        return ERROR; // ERROR可以是一个预定义的错误值
    } else {
        return S->data[(S->top)--];
    }
}
// 获取栈顶元素
ElementType GetTop(Stack *S) {
    if (IsEmpty(S)) {
        printf("Stack is empty. No top element.\n");
        return ERROR;
    } else {
        return S->data[S->top];
    }
}

堆栈的链式存储实现

typedef struct StackNode {
    ElementType data; // 数据域
    struct StackNode *next; // 指针域，指向下一个节点
} StackNode;
typedef struct {
    StackNode *top; // 栈顶指针，指向当前栈顶元素
} LinkedStack;
// 初始化栈
void InitStack(LinkedStack *S) {
    S->top = NULL; // 初始化栈顶指针为空，表示空栈
}
// 判断栈是否为空
int IsEmpty(LinkedStack *S) {
    return (S->top == NULL);
}
// 入栈操作
void Push(LinkedStack *S, ElementType item) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode)); // 创建新节点
    newNode->data = item; // 设置新节点的数据域为要入栈的元素
    newNode->next = S->top; // 将新节点插入到栈顶
    S->top = newNode; // 更新栈顶指针
}
// 出栈操作
ElementType Pop(LinkedStack *S) {
    if (IsEmpty(S)) {
        printf("Stack is empty. Cannot pop element.\n");
        return ERROR; // ERROR可以是一个预定义的错误值
    } else {
        StackNode *temp = S->top; // 保存当前栈顶节点
        ElementType item = temp->data; // 获取栈顶元素的值
        S->top = temp->next; // 更新栈顶指针
        free(temp); // 释放原栈顶节点
        return item;
    }
}
// 获取栈顶元素
ElementType GetTop(LinkedStack *S) {
    if (IsEmpty(S)) {
        printf("Stack is empty. No top element.\n");
        return ERROR;
    } else {
        return S->top->data;
    }
}

堆栈应用：表达式求值

当涉及到表达式求值时，我们可以考虑使用堆栈的应用。以下是一个更复杂的例子来演示如何使用堆栈进行中缀表达式的求值。

假设我们要求解的表达式为中缀表达式：(3 + 4) * 5 - 6 / 2

1. 创建一个空栈和运算符优先级字典。
2. 从左到右遍历中缀表达式中的每个元素。
3. 如果当前元素是数字，则将其转换为整数并直接入栈。
4. 如果当前元素是运算符，进行以下操作：

• 如果栈为空或者栈顶元素是左括号"("，则将当前运算符入栈。
• 如果栈不为空，并且当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符入栈。
• 如果栈不为空，并且当前运算符的优先级小于等于栈顶运算符的优先级，则弹出栈顶运算符并进行计算，并将计算结果入栈。重复此步骤直到满足条件，然后将当前运算符入栈。
• 如果当前元素是右括号")“，则弹出栈顶运算符并进行计算，直到遇到左括号”(“。左括号”("从栈中弹出，但不进行计算。

5. 当遍历完中缀表达式后，将栈中剩余的运算符依次弹出并进行计算。
6. 栈中仅剩下一个元素，即为表达式的计算结果。

以下是对中缀表达式(3 + 4) * 5 - 6 / 2求值的具体步骤：

1. 创建一个空栈和运算符优先级字典（加法和减法优先级为1，乘法和除法优先级为2）。
2. 遍历到"("，将其入栈。
3. 遍历到3，将其转换为整数并入栈。
4. 遍历到"+“，栈顶是”(“，将”+"入栈。
5. 遍历到4，将其转换为整数并入栈。
6. 遍历到")“，弹出栈顶运算符”+"并进行计算，得到3+4=7，并将计算结果7入栈。
7. 遍历到"“，栈顶元素是7，优先级大于”“，将”*"入栈。
8. 遍历到5，将其转换为整数并入栈。
9. 遍历到"-“，栈顶元素是”“，优先级小于等于”-“，弹出栈顶运算符”"并进行计算，得到7*5=35，并将计算结果35入栈。
10. 遍历到6，将其转换为整数并入栈。
11. 遍历到"/“，栈顶元素是6，优先级小于等于”/“，弹出栈顶运算符”/"并进行计算，得到6/2=3，并将计算结果3入栈。
12. 遍历完中缀表达式后，栈中仅剩下一个元素35-3，即为表达式的计算结果。

因此，中缀表达式(3 + 4) * 5 - 6 / 2的值为32。

中缀表达式如何转换为后缀表达式

将中缀表达式转换为后缀表达式的一种常用方法是使用栈。

以下是转换过程的步骤：

1. 创建一个空栈和一个空列表，用于存储后缀表达式。
2. 从左到右遍历中缀表达式中的每个元素。
3. 如果当前元素是数字或字母，则直接添加到后缀表达式列表的末尾。
4. 如果当前元素是左括号"("，则将其入栈。
5. 如果当前元素是右括号")“，则将栈中的元素弹出并添加到后缀表达式列表，直到遇到左括号”("。然后将左括号从栈中弹出，但不将其添加到后缀表达式列表中。
6. 如果当前元素是运算符（如"+", “-”, “*”, "/"等），则进行以下操作：

• 如果栈为空，则将当前运算符入栈。
• 如果栈不为空，并且栈顶元素是左括号"("，则将当前运算符入栈。
• 如果栈不为空，并且当前运算符的优先级小于等于栈顶运算符的优先级，则将栈顶运算符弹出并添加到后缀表达式列表，重复此步骤直到满足条件，然后将当前运算符入栈。
• 如果栈不为空，并且当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符入栈。

7. 当遍历完中缀表达式后，将栈中剩余的运算符依次弹出并添加到后缀表达式列表。
8. 后缀表达式列表即为转换后的后缀表达式。

以下是一个示例：

中缀表达式：2 + 3 * 4

转换过程：

1. 遍历到2，直接添加到后缀表达式列表。
2. 遍历到+，栈为空，将其入栈。
3. 遍历到3，直接添加到后缀表达式列表。
4. 遍历到*，栈不为空，栈顶是+，将*入栈。
5. 遍历到4，直接添加到后缀表达式列表。
6. 遍历完中缀表达式，将栈中剩余的运算符+和*依次弹出并添加到后缀表达式列表。

转换后的后缀表达式：2 3 4 * +

因此，中缀表达式2 + 3 * 4可以转换为后缀表达式2 3 4 * +。