数据结构之栈

栈 (Stack)

1. 概述

栈（Stack）是一种线性表，但限定在表的一端进行插入和删除操作的特殊线性表。按后进先出（Last In First Out, LIFO）的原则进行操作。栈的插入操作称为进栈（push），删除操作称为出栈（pop）。

2. 栈的定义

栈是一种只允许在一端进行插入和删除操作的线性表。这个端被称为栈顶（Top），相对的另一端为栈底（Bottom）。

3. 栈的基本操作

栈的基本操作包括初始化栈、判断栈空、判断栈满、进栈、出栈和取栈顶元素。

3.1 顺序栈

顺序栈是用一组地址连续的存储单元依次存放自栈底到栈顶的栈中元素。

定义顺序栈结构

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top;
} SeqStack;

初始化栈

void InitStack(SeqStack *S) {
    S->top = -1;
}

判断栈空

bool StackEmpty(SeqStack S) {
    return S.top == -1;
}

判断栈满

bool StackFull(SeqStack S) {
    return S.top == MAXSIZE - 1;
}

进栈

bool Push(SeqStack *S, int e) {
    if (S->top == MAXSIZE - 1) return false;
    S->data[++S->top] = e;
    return true;
}

出栈

bool Pop(SeqStack *S, int *e) {
    if (S->top == -1) return false;
    *e = S->data[S->top--];
    return true;
}

取栈顶元素

bool GetTop(SeqStack S, int *e) {
    if (S.top == -1) return false;
    *e = S.data[S.top];
    return true;
}

3.2 链栈

链栈是用链表来存储栈中的元素。

定义链栈节点结构

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode, *LinkStack;

初始化栈

void InitStack(LinkStack *S) {
    *S = NULL;
}

判断栈空

bool StackEmpty(LinkStack S) {
    return S == NULL;
}

进栈

bool Push(LinkStack *S, int e) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if (!p) return false;
    p->data = e;
    p->next = *S;
    *S = p;
    return true;
}

出栈

bool Pop(LinkStack *S, int *e) {
    if (*S == NULL) return false;
    StackNode *p = *S;
    *e = p->data;
    *S = p->next;
    free(p);
    return true;
}

取栈顶元素

bool GetTop(LinkStack S, int *e) {
    if (S == NULL) return false;
    *e = S->data;
    return true;
}

4. 栈的应用

栈在计算机科学中有广泛的应用，例如：

表达式求值：使用栈可以实现中缀表达式转换为后缀表达式，并求值。
括号匹配：使用栈可以检测表达式中的括号是否匹配。
函数调用：函数调用过程中使用栈保存返回地址和局部变量，实现递归调用。
深度优先搜索：在图的遍历中使用栈实现深度优先搜索。

5. 示例代码

下面是使用栈实现括号匹配的示例代码：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct StackNode {
    char data;
    struct StackNode *next;
} StackNode, *LinkStack;

void InitStack(LinkStack *S) {
    *S = NULL;
}

bool StackEmpty(LinkStack S) {
    return S == NULL;
}

bool Push(LinkStack *S, char e) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if (!p) return false;
    p->data = e;
    p->next = *S;
    *S = p;
    return true;
}

bool Pop(LinkStack *S, char *e) {
    if (*S == NULL) return false;
    StackNode *p = *S;
    *e = p->data;
    *S = p->next;
    free(p);
    return true;
}

bool GetTop(LinkStack S, char *e) {
    if (S == NULL) return false;
    *e = S->data;
    return true;
}

bool BracketMatch(char *exp) {
    LinkStack S;
    InitStack(&S);
    for (int i = 0; exp[i] != '\0'; i++) {
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            Push(&S, exp[i]);
        } else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
            if (StackEmpty(S)) return false;
            char topElem;
            Pop(&S, &topElem);
            if ((exp[i] == ')' && topElem != '(') ||
                (exp[i] == ']' && topElem != '[') ||
                (exp[i] == '}' && topElem != '{')) {
                return false;
            }
        }
    }
    return StackEmpty(S);
}

int main() {
    char *exp = "{[(2+3)*(4+5)]}";
    if (BracketMatch(exp)) {
        printf("The brackets match.\n");
    } else {
        printf("The brackets do not match.\n");
    }
    return 0;
}

上述代码实现了使用链栈进行括号匹配的功能。通过遍历表达式，将左括号入栈，遇到右括号时出栈，并检查是否匹配，最后检查栈是否为空来判断括号是否匹配。