数据结构-栈

介绍

栈（Stack）是一种非常基础和常用的数据结构，它是一个只能在一端进行插入（称为“入栈”或“压栈”，通常记作 push 操作）和删除（称为“出栈”或“弹栈”，通常记作 pop 操作）的线性表。这种特殊的操作规则使得栈具有“后进先出”（Last In First Out, LIFO）的特点。

栈的基本操作包括：

1. 初始化：创建一个空栈。
2. 判断栈是否为空：检查栈中是否没有元素。
3. 判满（如果适用的话）：检查栈是否已达到其最大容量。
4. 取栈顶元素：返回栈顶的元素但不删除它。这有时被称为“查看栈顶”或“peek”操作。
5. 入栈（压栈）：将元素添加到栈顶。
6. 出栈（弹栈）：移除并返回栈顶的元素。

实现举例

使用C语言数组或指针来实现栈。例如，用数组实现的顺序栈可以这样表示：

#define MAX_SIZE 100

typedef int StackElement;

struct Stack {
    StackElement data[MAX_SIZE];
    int top;
};

void initStack(struct Stack *s) {
    s->top = -1; // 初始化为-1表示栈是空的
}

int isEmpty(struct Stack *s) {
    return (s->top == -1);
}

int isFull(struct Stack *s) {
    return (s->top == MAX_SIZE - 1);
}

void push(struct Stack *s, StackElement item) {
    if (!isFull(s)) {
        s->data[++(s->top)] = item; // 入栈操作
    } else {
        printf("Stack overflow\n");
    }
}

StackElement pop(struct Stack *s) {
    if (!isEmpty(s)) {
        return s->data[(s->top)--]; // 出栈操作
    } else {
        printf("Stack underflow\n");
        return 0; // 或者返回其他默认值
    }
}

StackElement peek(struct Stack *s) {
    if (!isEmpty(s)) {
        return s->data[s->top]; // 查看栈顶元素
    } else {
        printf("Stack is empty\n");
        return 0; // 或者返回其他默认值
    }
}

实例栈的简单使用：

#include <stdio.h>

int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Top element is: %d\n", peek(&s)); // 输出 30

    printf("Popped element: %d\n", pop(&s)); // 输出 30，并从栈中移除
    printf("New top element is: %d\n", peek(&s)); // 输出 20

    return 0;
}

总结

栈的常见的应用场景

1.函数调用栈：
在程序执行过程中，每个线程都有一个由操作系统维护的内存区域（称为堆栈），用于存放函数调用时的局部变量和返回地址。每当函数被调用时，它的参数、局部变量和返回地址会被压入栈中；当函*数执行完毕返回时，这些信息会被从栈中弹出。
2.表达式求值：
编译器和解释器在处理数学或逻辑表达式时，通常使用两个栈来实现操作数和运算符的计算顺序。一个栈用于存储操作数，另一个栈用于存储运算符。这种技术可以确保正确的运算优先级。
3.深度优先搜索（DFS）：
在图论和树的遍历算法中，栈常被用来实现深度优先搜索。通过不断地将当前节点的相邻节点压入栈中，然后访问栈顶的节点并重复这个过程，可以确保所有能到达的节点都被访问到。
4.括号匹配：
在解析文本中的括号序列（如编程语言中的代码块或字符串中的 HTML 标签）时，可以使用栈来检查括号是否正确配对。每遇到左括号就将其压入栈中，每遇到右括号就检查栈顶的左括号是否与之匹配，若匹配则弹出栈顶元素，否则表示不匹配。
5.回溯算法：
栈常常用于回溯算法中，例如八皇后问题、迷宫寻路等。每次探索一条路径时，都将当前状态压入栈中，以便在该路径走不通时能够回到之前的某个状态继续探索其他可能的路径。
6.浏览器的历史记录：
浏览器通常使用栈来存储用户浏览过的页面历史，后访问的页面压入栈顶，当用户点击“后退”按钮时，可以从栈顶弹出最近访问的页面。
7.计算机图形学：
栈在计算机图形学中有多种应用，例如保存视口变换的状态、实现剪裁算法等。
8.undo/redo 功能：
在许多应用程序（如文字处理器、图像编辑器等）中，undo 和 redo 功能是基于栈实现的。每个修改操作都会压入栈中，当用户需要撤销时，只需弹出最近的操作并恢复之前的状态即可。
9.自动机和词法分析器：
栈在构建有限自动机和词法分析器中也有重要应用，它们帮助识别输入串中的模式和构建语法树。