02 堆栈

02-堆栈

是一种线性结构，一种特殊的线性表。

定义

堆栈（Stack）：具有一定操作约束的线性表

• 只在栈顶（Top）做插入、删除
• 插入数据：入栈（Push）
• 删除数据：出栈（Pop）
• 后入先出：Last In First Out (LIFO)

ADT 描述

类型名称：堆栈（Stack）

数据对象集：一个有 0 个或多个元素的有穷线性表。

操作集：长度为 MaxSize 的堆栈 \(\text{S} \in \text{Stack}\)，堆栈元素 \(\text{item} \in \text{ElementType}\)

1. Stack CreateStack(int MaxSize)：生成空堆栈，其最大长度为 MaxSize
2. int IsFull(Stack S, int MaxSize)：判断堆栈 S 是否已满
3. void Push(Stack S, ElementType item)：将元素 item 压入堆栈
4. int IsEmpty(Stack S)：判断堆栈 S 是否为空
5. ElementType Pop(Stack S)：删除并返回栈顶元素

顺序存储

用一个一维数组和一个记录栈顶元素位置的变量组成、

#include <iostream>

const int kMaxSize = 100; // 栈的最大容量

using Stack = struct SNode*;
using ElementType = double;

struct SNode {
    ElementType data[kMaxSize]; // 储存的数据
    int top;                    // 栈顶指针
};

/* 判断栈是否为空 */
bool isEmpty(Stack S) { return S->top == -1; }

/* 判断栈是否为满 */
bool isFull(Stack S) { return S->top == kMaxSize - 1; }

/* 入栈 */
bool push(ElementType X, Stack S) {
    if (isFull(S)) { /* 栈满 */
        std::cout << "the stack is full\n";
        return false;
    }
    S->data[++S->top] = X; // 入栈
    return true;
}

/* 出栈 */
ElementType pop(Stack S) {
    if (isEmpty(S)) { /* 栈空 */
        std::cout << "the stack is empty\n";
        return NAN;
    }
    ElementType X = S->data[S->top--]; // 出栈
    return X;
}

链式存储

实际上是一个单链表，叫做链栈。插入和删除操作只能在链栈栈顶进行。

栈顶指针 Top 应该在链表的头。

#include <iostream>

using Stack = struct SNode*;
using ElementType = double;

struct SNode {
    ElementType data; // 指向动态分配的数组
    SNode* next;      // 栈顶指针
};

/*
 * S作为头结点，数据域不存储内容，只有指针域使用，指向的是栈顶元素。
 * 栈空则指针域为 nullptr 即 S->next == nullptr
 */

/* 构建头结点并返回指针 */
Stack createStack() {
    Stack S = new SNode;
    S->next = nullptr;
    return S;
}

/* 判断栈是否为空 */
bool isEmpty(Stack S) { return S->next == nullptr; }

/* 入栈 */
void push(ElementType X, Stack S) {
    SNode* newNode = new SNode;
    newNode->data = X;
    newNode->next = S->next;
    S->next = newNode;
}

/* 出栈 */
ElementType pop(Stack S) {
    if (isEmpty(S)) { /* 栈空 */
        std::cout << "the stack is empty\n";
        return NAN;
    }
    SNode* del = S->next;      // 要删除的结点
    ElementType X = del->data; // 取出栈顶元素
    S->next = del->next;       // 修改栈顶指针
    delete del;                // 释放结点空间
    return X;
}

堆栈应用：表达式求值问题

计算机求值的时候，会通过处理后缀表达式来进行求值。

• 中缀表达式：2 + 9 / 3 - 5
• 后缀表达式/逆波兰式(Reverse Polish Notation, RPN)：2 9 3 / + 5 -

计算方法：从左到右读入后缀表达式各项，包含运算符与运算数

1. 运算数：入栈
2. 运算符：从堆栈中弹出适当数量运算数，计算结果并将结果入栈
3. 最后，栈顶上的元素就是表达式的结果值

中缀表达式转后缀表达式

2 + 9 / 3 - 5 => 2 9 3 / + 5 -

观察到：

1. 运算数相对顺序不变
2. 运算符号顺序发生改变，优先级高的符号在左边，运算级相同的运算从左至右排列

所以有基本策略：

1. 运算数：直接输出
2. 左括号：压入堆栈
3. 右括号：将栈顶的运算符依次弹出并输出，直到遇到左括号（出栈但不输出）
4. 运算符：
   1. 优先级大于栈顶运算符时，将其压栈
   2. 优先级小于等于栈顶运算符时，依次弹出栈顶运算符，直到该运算符大于新的运算符优先级为止，然后将该运算符压栈
5. 各对象处理完毕，则将栈中剩余运算符一并输出

列举其他应用

• 函数调用及递归实现
• 深度优先搜索
• 回溯算法
• ……