数据结构：顺序栈与链栈的原理、实现及应用-EW帮帮网

数据结构详解：顺序栈与链栈的原理、实现及应用

1. 引言：栈的核心概念

栈（Stack）是一种重要的线性数据结构，它遵循后进先出（Last In First Out, LIFO）的原则。这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。栈的这种特性使其在多种计算场景中非常有用，例如函数调用、表达式求值和括号匹配等。
栈的基本操作包括：

Push（入栈）：在栈顶添加一个元素
Pop（出栈）：移除栈顶元素并返回其值
Peek/Top（查看栈顶）：返回栈顶元素但不移除它
isEmpty（判空）：检查栈是否为空
在这篇技术文章中，我们将详细探讨栈的两种主要实现方式：顺序栈（基于数组）和链栈（基于链表），分析它们的优缺点，并提供实际代码示例和应用场景。

2. 顺序栈：数组实现

2.1 顺序栈的结构与特点

顺序栈使用数组作为底层存储结构，这意味着它需要一块连续的内存空间。顺序栈通常包含两个主要部分：一个用于存储元素的数组和一个用于跟踪栈顶位置的整型变量（通常称为"top"或"栈顶指针"）。
顺序栈的主要特点：

内存连续，访问速度快
需要预先指定栈的最大容量
当栈满时无法再添加新元素（除非动态扩容）
操作时间复杂度为O(1)

2.2 顺序栈的实现代码（C语言）

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

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

typedef struct {
    int data[MAX_SIZE]; // 存储栈元素的数组
    int top;            // 栈顶指针
} SeqStack;

// 初始化栈
void InitStack(SeqStack *S) {
    S->top = -1; // 初始化为-1表示空栈
}

// 判断栈是否为空
int IsEmpty(SeqStack *S) {
    return (S->top == -1);
}

// 判断栈是否已满
int IsFull(SeqStack *S) {
    return (S->top == MAX_SIZE - 1);
}

// 入栈操作
int Push(SeqStack *S, int value) {
    if (IsFull(S)) {
        printf("Stack is full! Push operation failed.\n");
        return 0;
    }
    S->data[++(S->top)] = value; // 栈顶指针先加1，再将元素放入栈顶位置
    return 1;
}

// 出栈操作
int Pop(SeqStack *S, int *value) {
    if (IsEmpty(S)) {
        printf("Stack is empty! Pop operation failed.\n");
        return 0;
    }
    *value = S->data[(S->top)--]; // 先取出栈顶元素，再将栈顶指针减1
    return 1;
}

// 获取栈顶元素（但不删除）
int GetTop(SeqStack *S, int *value) {
    if (IsEmpty(S)) {
        printf("Stack is empty!\n");
        return 0;
    }
    *value = S->data[S->top];
    return 1;
}

// 打印栈中的所有元素
void PrintStack(SeqStack *S) {
    if (IsEmpty(S)) {
        printf("Stack is empty!\n");
        return;
    }
    
    printf("Stack elements (from bottom to top): ");
    for (int i = 0; i <= S->top; i++) {
        printf("%d ", S->data[i]);
    }
    printf("\n");
}

2.3 顺序栈的优缺点分析

优点：

访问速度快：由于内存连续，CPU缓存友好，访问效率高
实现简单：代码逻辑直接，易于理解和实现
内存开销小：只需要一个数组和一个整型变量，无需额外指针开销
缺点：
固定容量：需要预先定义栈的大小，可能导致空间浪费或栈溢出
扩容困难：当栈满时，扩容需要创建新数组并复制所有元素，时间复杂度为O(n)
不灵活：难以适应动态变化的数据规模

3. 链栈：链表实现

3.1 链栈的结构与特点

链栈使用链表作为底层存储结构，每个元素包含数据部分和指向下一个节点的指针。链栈通常将链表的头部作为栈顶，这样入栈和出栈操作可以直接在链表头部进行，时间复杂度为O(1)。
链栈的主要特点：

使用离散的内存空间，通过指针连接
无需预先指定容量，可以动态增长
只有当内存耗尽时才会出现"栈满"情况
每个元素需要额外空间存储指针

3.2 链栈的实现代码（C语言）

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

// 定义栈节点结构
typedef struct StackNode {
    int data;               // 数据域
    struct StackNode *next; // 指针域
} StackNode;

// 定义链栈结构
typedef struct {
    StackNode *top; // 栈顶指针
} LinkStack;

// 初始化栈
void InitLinkStack(LinkStack *S) {
    S->top = NULL;
}

// 判断栈是否为空
int IsEmpty(LinkStack *S) {
    return (S->top == NULL);
}

// 入栈操作
void Push(LinkStack *S, int value) {
    // 创建新节点
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed! Push operation failed.\n");
        return;
    }
    
    newNode->data = value;
    newNode->next = S->top; // 新节点指向原栈顶
    S->top = newNode;       // 更新栈顶指针为新节点
}

// 出栈操作
int Pop(LinkStack *S, int *value) {
    if (IsEmpty(S)) {
        printf("Stack is empty! Pop operation failed.\n");
        return 0;
    }
    
    StackNode *temp = S->top; // 临时保存栈顶节点
    *value = temp->data;
    S->top = S->top->next; // 更新栈顶指针为下一个节点
    free(temp);            // 释放原栈顶节点的内存
    return 1;
}

// 获取栈顶元素（但不删除）
int GetTop(LinkStack *S, int *value) {
    if (IsEmpty(S)) {
        printf("Stack is empty!\n");
        return 0;
    }
    
    *value = S->top->data;
    return 1;
}

// 打印栈中的所有元素
void PrintStack(LinkStack *S) {
    if (IsEmpty(S)) {
        printf("Stack is empty!\n");
        return;
    }
    
    printf("Stack elements (from top to bottom): ");
    StackNode *current = S->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 销毁栈，释放所有节点内存
void DestroyStack(LinkStack *S) {
    StackNode *current = S->top;
    while (current != NULL) {
        StackNode *temp = current;
        current = current->next;
        free(temp);
    }
    S->top = NULL;
}

3.3 链栈的优缺点分析

优点：

动态大小：无需预先指定栈的大小，可以随需求动态增长
内存高效：只分配实际需要的空间，没有容量浪费
灵活性：适合数据规模动态变化较大的场景
缺点：
额外内存开销：每个节点需要额外空间存储指针
访问速度稍慢：由于内存不连续，CPU缓存不友好
内存管理复杂：需要手动管理内存分配和释放，容易导致内存泄漏如果处理不当

4. 顺序栈与链栈的对比

为了更清晰地理解两种实现的差异，下表列出了顺序栈和链栈的主要特性对比：

特性	顺序栈	链栈
存储方式	连续的内存空间（数组）	离散的内存空间（链表）
容量	固定，需预先定义	动态增长，受限于可用内存
空间效率	可能有浪费（数组固定大小）	无浪费（按需分配）
时间效率	所有操作 O(1)	所有操作 O(1)
内存管理	简单，系统自动回收	需手动管理节点内存的申请和释放
适用场景	数据规模已知或变化不大的场景	数据规模动态变化较大的场景

选择建议：

如果数据规模已知且变化不大，或者对性能要求极高，优先选择顺序栈
如果数据规模变化较大或无法预估最大容量，优先选择链栈

5. 栈的应用实例

例题名称	核心知识点	难度
括号匹配	栈的基本操作、LIFO特性	⭐
表达式求值	栈管理运算符优先级、后缀表达式	⭐⭐
模拟浏览器前进后退	双栈协作、状态管理	⭐⭐
递归的非递归实现	栈模拟函数调用栈	⭐⭐
行编辑程序（含退格）	栈处理输入、删除逻辑	⭐⭐

📝 5.1 括号匹配问题

问题描述：检查一个字符串中的括号是否正确匹配，有效的字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。

解决思路：遍历字符串，遇到左括号就入栈；遇到右括号时，检查栈顶的左括号是否与之匹配。匹配则弹出栈顶，否则无效。最后栈应为空。

代码实现（C语言，顺序栈）：

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

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int top;
} SeqStack;

void initStack(SeqStack *s) { s->top = -1; }
bool isEmpty(SeqStack *s) { return s->top == -1; }
bool isFull(SeqStack *s) { return s->top == MAX_SIZE - 1; }

bool push(SeqStack *s, char c) {
    if (isFull(s)) return false;
    s->data[++(s->top)] = c;
    return true;
}

bool pop(SeqStack *s, char *c) {
    if (isEmpty(s)) return false;
    *c = s->data[(s->top)--];
    return true;
}

bool peek(SeqStack *s, char *c) {
    if (isEmpty(s)) return false;
    *c = s->data[s->top];
    return true;
}

bool isValid(char* s) {
    SeqStack stack;
    initStack(&stack);
    char topChar;

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            push(&stack, s[i]);
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if (!peek(&stack, &topChar)) return false; // 栈空，有右括号无左括号匹配

            if ((s[i] == ')' && topChar == '(') ||
                (s[i] == ']' && topChar == '[') ||
                (s[i] == '}' && topChar == '{')) {
                pop(&stack, &topChar);
            } else {
                return false; // 括号类型不匹配
            }
        }
    }
    return isEmpty(&stack); // 检查是否所有左括号都被匹配
}

int main() {
    char expr[] = "({[]})";
    printf("%s is %s\n", expr, isValid(expr) ? "valid" : "invalid");
    return 0;
}

🧮 5.2 表达式求值

问题描述：计算算术表达式的值，例如 4 + 2 * 3 - 10 / (7 - 5)。

解决思路：使用两个栈，一个存放操作数，一个存放运算符。根据运算符的优先级决定计算顺序。

代码概要（C语言）：

// 此处假设已定义顺序栈结构 SeqStack 及其基本操作

int getPriority(char op) {
    switch(op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

int calculate(int a, int b, char op) {
    switch(op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 注意除零错误
        default: return 0;
    }
}

int evalExpression(char* expr) {
    SeqStack opnd; // 操作数栈
    SeqStack optr; // 运算符栈
    initStack(&opnd);
    initStack(&optr);
    push(&optr, '#'); // 预设一个起始符

    int i = 0;
    char ch, topOp, arithmeticOp;
    int num, a, b;

    while (expr[i] != '\0' || !isEmpty(&optr)) {
        ch = expr[i];
        if (ch == ' ') { i++; continue; } // 跳过空格

        if (ch >= '0' && ch <= '9') { // 处理数字
            num = 0;
            while (expr[i] >= '0' && expr[i] <= '9') {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            push(&opnd, num);
        } else if (ch == '(') {
            push(&optr, '(');
            i++;
        } else if (ch == ')') {
            peek(&optr, &topOp);
            while (topOp != '(') {
                pop(&optr, &arithmeticOp);
                pop(&opnd, &b); pop(&opnd, &a);
                push(&opnd, calculate(a, b, arithmeticOp));
                peek(&optr, &topOp);
            }
            pop(&optr, &topOp); // 弹出左括号
            i++;
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            peek(&optr, &topOp);
            while (getPriority(topOp) >= getPriority(ch)) {
                pop(&optr, &arithmeticOp);
                pop(&opnd, &b); pop(&opnd, &a);
                push(&opnd, calculate(a, b, arithmeticOp));
                peek(&optr, &topOp);
            }
            push(&optr, ch);
            i++;
        } else {
            i++; // 处理其他字符或结束
        }
    }

    pop(&opnd, &num); // 最终结果
    return num;
}
// 主函数中测试
int main() {
    char expr[] = "4 + 2 * 3 - 10 / (7 - 5)";
    printf("Result of %s is %d\n", expr, evalExpression(expr));
    return 0;
}

🌐 5.3 模拟浏览器前进后退功能

问题描述：使用两个栈模拟浏览器的前进后退功能。

解决思路：使用两个栈，backStack 存放后退的页面，forwardStack 存放前进的页面。访问新页面时压入 backStack 并清空 forwardStack；后退时从 backStack 弹出并压入 forwardStack；前进时从 forwardStack 弹出并压入 backStack。

代码概要（C语言，链栈）：

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

typedef struct PageNode {
    char url[100];
    struct PageNode* next;
} PageNode;

typedef struct {
    PageNode* top;
} LinkStack;

void initStack(LinkStack* s) { s->top = NULL; }
bool isEmpty(LinkStack* s) { return s->top == NULL; }

void push(LinkStack* s, const char* url) {
    PageNode* newNode = (PageNode*)malloc(sizeof(PageNode));
    strcpy(newNode->url, url);
    newNode->next = s->top;
    s->top = newNode;
}

bool pop(LinkStack* s, char* url) {
    if (isEmpty(s)) return false;
    PageNode* temp = s->top;
    strcpy(url, temp->url);
    s->top = s->top->next;
    free(temp);
    return true;
}

bool peek(LinkStack* s, char* url) {
    if (isEmpty(s)) return false;
    strcpy(url, s->top->url);
    return true;
}

// 模拟浏览器
LinkStack backStack, forwardStack;
void initBrowser() {
    initStack(&backStack);
    initStack(&forwardStack);
}

void visitUrl(const char* url) {
    push(&backStack, url);
    // 访问新页面时清空前进栈
    char tempUrl[100];
    while (pop(&forwardStack, tempUrl)) { /* 只是清空 */ }
    printf("Visited: %s\n", url);
}

void goBack() {
    char currentUrl[100], backUrl[100];
    if (pop(&backStack, currentUrl) && peek(&backStack, backUrl)) {
        push(&forwardStack, currentUrl);
        printf("Back to: %s\n", backUrl);
    } else {
        printf("Cannot go back.\n");
    }
}

void goForward() {
    char forwardUrl[100];
    if (pop(&forwardStack, forwardUrl)) {
        push(&backStack, forwardUrl);
        printf("Forward to: %s\n", forwardUrl);
    } else {
        printf("Cannot go forward.\n");
    }
}

int main() {
    initBrowser();

    visitUrl("www.homepage.com");
    visitUrl("www.news.com");
    visitUrl("www.mail.com");

    goBack();   // 回到 www.news.com
    goBack();   // 回到 www.homepage.com

    goForward(); // 前进到 www.news.com

    visitUrl("www.search.com"); // 此时前进栈被清空

    return 0;
}

🔄 5.4 递归的非递归实现

问题描述：使用栈模拟递归过程，例如计算阶乘。

解决思路：递归的本质是函数调用栈，我们可以用显式栈来模拟。

代码实现（C语言，顺序栈实现阶乘）：

#include <stdio.h>

long factorialIterative(int n) {
    SeqStack stack; // 假设使用之前的顺序栈，存储类型为int
    initStack(&stack);
    long result = 1;

    if (n == 0 || n == 1) return 1;

    while (n > 1) {
        push(&stack, n);
        n--;
    }

    int current;
    while (!isEmpty(&stack)) {
        pop(&stack, &current);
        result *= current;
    }

    return result;
}

int main() {
    int n = 5;
    printf("Iterative %d! = %ld\n", n, factorialIterative(n));
    return 0;
}

⌨️ 5.5 行编辑程序

问题描述：输入若干串字符，遇到换行符 \n 则输出本行当前处理结果。输入以 # 结束。输入 @ 表示回退到本行行首，输入 `` 表示回退一格。

解决思路：使用栈存储当前行的字符。遇到普通字符入栈；遇到 `` 则出栈（相当于退格）；遇到 @ 则清空栈（相当于清空当前行）。

代码概要（C语言，顺序栈）：

#include <stdio.h>

void lineEditor() {
    SeqStack s;
    initStack(&s);
    char ch, temp;

    printf("Enter your text (end with #, use @ to clear line, use  to backspace):\n");

    while ((ch = getchar()) != '#') {
        if (ch == '\n') {
            // 输出当前行
            printf("\nLine output: ");
            // 逆序输出栈内容较为复杂，可以先用一个临时栈反转
            SeqStack tempStack;
            initStack(&tempStack);
            while (!isEmpty(&s)) {
                pop(&s, &temp);
                push(&tempStack, temp);
            }
            while (!isEmpty(&tempStack)) {
                pop(&tempStack, &temp);
                putchar(temp);
            }
            printf("\n");
            initStack(&s); // 清空栈准备下一行
        } else if (ch == '@') {
            initStack(&s); // 清空栈（回退到行首）
        } else if (ch == '') {
            pop(&s, &temp); // 出栈（回退一格）
        } else {
            if (!isFull(&s)) {
                push(&s, ch); // 普通字符入栈
            } else {
                printf("Stack is full!\n");
            }
        }
    }
}

int main() {
    lineEditor();
    return 0;
}

5.1 括号匹配问题

问题描述：给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串中的括号是否匹配正确。
解决方案：使用栈来检查括号匹配

遇到左括号时，将其压入栈中
遇到右括号时，检查栈顶的左括号是否与之匹配
最后检查栈是否为空
代码实现：

int isValid(char* s) {
    SeqStack stack;
    InitStack(&stack);
    int i = 0;
    char ch;

    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            Push(&stack, s[i]); // 遇到左括号，入栈
        } else {
            if (IsEmpty(&stack)) { // 遇到右括号但栈已空，不匹配
                return 0;
            }
            GetTop(&stack, &ch); // 获取栈顶元素
            if ((s[i] == ')' && ch == '(') ||
                (s[i] == ']' && ch == '[') ||
                (s[i] == '}' && ch == '{')) {
                Pop(&stack, &ch); // 匹配成功，弹出栈顶元素
            } else {
                return 0; // 不匹配
            }
        }
        i++;
    }
    return IsEmpty(&stack); // 最后栈空则有效，非空则无效
}

6. 总结与展望

通过本文的详细讲解，我们了解了：

栈是一种后进先出（LIFO）的线性数据结构
栈有两种主要实现方式：顺序栈（基于数组）和链栈（基于链表）
顺序栈和链栈各有优缺点，适用于不同场景
栈在计算机科学中有广泛的应用，如括号匹配、表达式求值和函数调用等

数据结构：顺序栈与链栈的原理、实现及应用