当前位置： 首页 > article >正文

数据结构：栈（Stack）及其实现

article 2025/2/27 8:23:52

栈（Stack）是计算机科学中常用的一种数据结构，它遵循先进后出（Last In, First Out，LIFO）的原则。也就是说，栈中的元素只能从栈顶进行访问，最后放入栈中的元素最先被取出。栈在很多应用中非常重要，例如函数调用、表达式求值、深度优先搜索等。

本文将介绍栈的基本概念、实现逻辑，并通过C语言代码演示栈的常见操作。

1. 栈的基本概念

栈是一种线性数据结构，其主要操作包括：

  • 压栈（Push）：将一个元素压入栈顶。
  • 弹栈（Pop）：从栈顶移除一个元素。
  • 栈顶元素（Top/Peek）：获取栈顶的元素，但不移除它。
  • 栈空（IsEmpty）：检查栈是否为空。
  • 栈满（IsFull）：检查栈是否已满（对于固定大小的栈）。

栈的特点是只能从栈顶进行操作，所有元素的插入和删除都发生在栈顶。

2. 栈的实现逻辑

栈的实现可以基于数组或链表。这里我们采用数组实现栈，并且实现栈的常见操作。

  1. 栈的初始化：栈需要一个数组来存储元素，并且需要一个指针top来指示栈顶的位置。
  2. 压栈操作（Push）：将元素放入栈顶，top指针向上移动。
  3. 弹栈操作（Pop）：移除栈顶元素，top指针向下移动。
  4. 查看栈顶元素（Top/Peek）：返回top指针位置的元素。
  5. 检查栈空（IsEmpty）：判断top是否为-1，栈为空时top = -1。
  6. 检查栈满（IsFull）：判断top是否等于栈的最大容量减1。

3. C语言实现栈

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

#define MAX 5  // 栈的最大容量

// 栈结构体
typedef struct {
    int arr[MAX];  // 存储栈元素的数组
    int top;       // 栈顶指针
} Stack;

// 栈初始化函数
void initStack(Stack* stack) {
    stack->top = -1;  // 初始时栈为空，栈顶指针为-1
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;  // 如果栈顶指针为-1，说明栈为空
}

// 判断栈是否为满
int isFull(Stack* stack) {
    return stack->top == MAX - 1;  // 如果栈顶指针为MAX-1，说明栈已满
}

// 压栈操作
void push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("栈满，无法压栈！\n");
        return;
    }
    stack->arr[++(stack->top)] = value;  // 将元素放入栈顶，并更新栈顶指针
    printf("元素 %d 压栈成功！\n", value);
}

// 弹栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈空，无法弹栈！\n");
        return -1;
    }
    return stack->arr[(stack->top)--];  // 返回栈顶元素，并更新栈顶指针
}

// 获取栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈空，无法获取栈顶元素！\n");
        return -1;
    }
    return stack->arr[stack->top];  // 返回栈顶元素
}

// 打印栈的所有元素
void printStack(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈空，无法打印栈元素！\n");
        return;
    }
    printf("栈内元素：");
    for (int i = 0; i <= stack->top; i++) {
        printf("%d ", stack->arr[i]);
    }
    printf("\n");
}

int main() {
    Stack stack;
    initStack(&stack);  // 初始化栈

    // 压栈操作
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    push(&stack, 40);
    push(&stack, 50);
    
    // 打印栈元素
    printStack(&stack);

    // 再压栈时，栈满的情况
    push(&stack, 60);

    // 弹栈操作
    printf("弹栈元素: %d\n", pop(&stack));
    printf("弹栈元素: %d\n", pop(&stack));

    // 打印栈元素
    printStack(&stack);

    // 查看栈顶元素
    printf("栈顶元素: %d\n", peek(&stack));

    return 0;
}

4. 代码注释说明

  • 栈的结构体：Stack结构体包含了一个大小为MAX的数组arr来存储栈元素，以及一个top变量来记录栈顶的位置。top的初始值为-1，表示栈为空。

  • initStack函数：初始化栈，将top设为-1，表示栈为空。

  • isEmpty函数：判断栈是否为空。如果top为-1，返回1表示栈空；否则返回0。

  • isFull函数：判断栈是否为满。如果top等于MAX-1，说明栈已满，返回1表示栈满；否则返回0。

  • push函数：将元素压入栈顶，首先检查栈是否已满，如果未满，top指针加1，然后将元素放入栈顶。

  • pop函数：从栈顶移除元素，首先检查栈是否为空，如果栈不为空，返回栈顶元素并将top指针减1。

  • peek函数：查看栈顶元素，但不移除它。首先检查栈是否为空，如果不为空，返回栈顶元素。

  • printStack函数：打印栈中所有的元素。首先检查栈是否为空，如果栈不为空，则依次打印从栈底到栈顶的所有元素。

  • 5. 运行示例

    假设我们运行上述程序，输出结果如下：

元素 10 压栈成功！
元素 20 压栈成功！
元素 30 压栈成功！
元素 40 压栈成功！
元素 50 压栈成功！
栈内元素：10 20 30 40 50 
栈满，无法压栈！
弹栈元素: 50
弹栈元素: 40
栈内元素：10 20 30 
栈顶元素: 30
  • 初始时，栈为空，通过压栈操作逐步将元素10, 20, 30, 40, 50压入栈中。
  • 然后尝试压栈一个新的元素60，由于栈已满，无法压栈。
  • 接着，弹出栈顶元素50和40，并打印当前栈中的元素。
  • 最后，查看栈顶元素30。

6.栈在实际应用中的一些常见使用场景

6.1. 函数调用和递归

栈最常见的应用之一是函数调用，它在计算机的程序执行过程中被广泛使用。

实现过程：

当程序调用一个函数时，程序会将当前函数的执行状态（如局部变量、返回地址等）保存在栈中，这个过程叫做“入栈”。

  • 当一个函数调用另一个函数时，栈会继续“压入”当前函数的状态。
  • 当一个函数执行完毕，栈会“弹出”当前函数的状态，并恢复到上一个函数的执行状态。

这种机制是通过栈来实现的，也就是函数调用栈。当递归调用发生时，每次递归调用都将当前的执行环境推入栈中，直到递归结束并返回时，栈中的元素逐步弹出，恢复到原来的状态。

示例：

递归计算斐波那契数列时，栈用于存储每次递归调用的状态。

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

每次fibonacci函数调用时，程序都会把当前调用的返回地址和局部变量压入栈中。栈的大小随着递归深度的增加而增加，直到递归返回时，栈逐一弹出，恢复状态。

6.2. 表达式求值

栈是计算机中表达式求值的常用工具，特别是在处理后缀表达式（逆波兰表示法）和前缀表达式时。

后缀表达式（逆波兰表示法）：

例如，给定一个表达式3 4 + 5 *，可以通过栈来实现求值。

  • 遇到操作数（如3、4），将其压入栈。
  • 遇到操作符（如+、*），弹出栈顶的两个操作数，进行计算，然后将结果重新压入栈。
  • 最终栈中剩下的就是结果。

示例：

例如计算表达式3 4 + 5 *：

  • 第一步：遇到3和4，压栈，栈为[3, 4]。
  • 第二步：遇到+，弹出栈顶的两个数4和3，计算3 + 4 = 7，将结果压入栈，栈为[7]。
  • 第三步：遇到5，压栈，栈为[7, 5]。
  • 第四步：遇到*，弹出栈顶的两个数5和7，计算7 * 5 = 35，将结果压入栈，栈为[35]。

最终栈中的元素即为结果35。

6.3. 括号匹配

栈常用于括号匹配问题，特别是在编译器和解释器中，栈是检查是否存在匹配括号的一种有效方式。

实现过程：

通过栈可以有效地检查括号的匹配情况，例如：

  • 遇到一个左括号(时，将其压入栈中。
  • 遇到右括号)时，弹出栈顶元素，并确保栈中存在对应的左括号(。
  • 如果栈为空或者遇到不匹配的括号，则说明括号不匹配。

示例：

检查括号匹配的代码：

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

#define MAX 100

typedef struct {
    char items[MAX];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, char value) {
    stack->items[++(stack->top)] = value;
}

char pop(Stack* stack) {
    return stack->items[(stack->top)--];
}

bool isValid(char* s) {
    Stack stack;
    initStack(&stack);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            push(&stack, s[i]);
        } else if (s[i] == ')') {
            if (isEmpty(&stack)) {
                return false; // 没有匹配的左括号
            }
            pop(&stack); // 弹出栈顶左括号
        }
    }
    return isEmpty(&stack); // 如果栈为空，说明所有括号匹配
}

int main() {
    char s[] = "(())";
    if (isValid(s)) {
        printf("括号匹配!\n");
    } else {
        printf("括号不匹配!\n");
    }
    return 0;
}
6.4. 浏览器历史记录和撤销操作

栈还被广泛用于实现浏览器的历史记录和撤销操作，这是由于栈的后进先出（LIFO）特性。

浏览器历史记录：

浏览器通过栈来保存用户访问的网页，每访问一个新网页时，当前网页的URL会被压入栈中，用户点击"后退"按钮时，浏览器会从栈顶弹出上一个网页的URL，展示该页面。

撤销操作：

例如在文本编辑器中，栈用于保存操作记录（如文本插入、删除等），当用户点击"撤销"时，可以通过弹出栈顶的操作记录来撤销最近的操作。

6.5. 深度优先搜索（DFS）

栈是深度优先搜索（DFS）算法的基础。在图的遍历中，深度优先搜索使用栈来存储待访问的节点，直到访问完所有可能的节点。

实现过程：

  • 从某个节点开始，访问该节点并将其压入栈中。
  • 然后遍历该节点的所有未访问的邻居，将它们压入栈中。
  • 每次弹出栈顶节点，继续遍历该节点的邻居，直到栈为空为止。

这种方式常用于遍历无向图、有向图或解决迷宫问题等。

6.6. 逆序操作

栈可以用于实现逆序操作，例如将一个序列反转。

实现过程：

通过将序列中的元素压入栈中，然后再从栈中逐个弹出元素，这样就能得到一个逆序的序列。

示例：

反转字符串的代码：

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

#define MAX 100

typedef struct {
    char items[MAX];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

void push(Stack* stack, char value) {
    stack->items[++(stack->top)] = value;
}

char pop(Stack* stack) {
    return stack->items[(stack->top)--];
}

void reverseString(char* str) {
    Stack stack;
    initStack(&stack);
    int length = strlen(str);

    // 将字符串字符压入栈
    for (int i = 0; i < length; i++) {
        push(&stack, str[i]);
    }

    // 从栈中弹出字符，形成逆序字符串
    for (int i = 0; i < length; i++) {
        str[i] = pop(&stack);
    }
}

int main() {
    char str[] = "Hello, World!";
    reverseString(str);
    printf("逆序字符串: %s\n", str);
    return 0;
}

7. 总结

  • 栈是一种遵循LIFO（先进后出）原则的线性数据结构，它的常见应用包括递归函数调用、表达式求值、括号匹配等。本文通过C语言实现了一个基于数组的栈，演示了栈的基本操作：压栈、弹栈、查看栈顶元素、判断栈空和栈满，并附上了详细的注释。栈是一种非常简单但功能强大的数据结构，理解栈的基本操作和应用场景对于学习计算机科学非常重要。

  • 栈作为一种数据结构，在许多计算机科学和实际应用中都扮演着重要的角色。其最典型的应用包括：

  • 函数调用和递归。

  • 表达式求值。

  • 括号匹配。

  • 浏览器历史记录和撤销操作。

  • 深度优先搜索。

  • 逆序操作。

版权声明：本文为原创文章，转载请注明出处。


http://www.kler.cn/a/550850.html

相关文章：

  • 在 UniApp 项目中设置多语言
  • GO语言中的悲观锁与乐观锁
  • Python排序算法详解
  • 坐井说天阔---DeepSeek-R1
  • 设计模式2：单例模式
  • Docker 容器日志与监控
  • 【对比】Pandas 和 Polars 的区别
  • Unity截取RenderTexture某帧画面显示在Image上
  • Leetcode 算法题 88. 合并两个有序数组
  • 802.3 两种格式
  • Redis 10章——集群（cluster）
  • 服务器A到服务器B免密登录
  • 【拒绝算法PUA】LeetCode 1287. 有序数组中出现次数超过25%的元素
  • maven使用默认settings.xml配置时，Idea基于pom.xml更新依赖时报错，有些组件下载时连接超时
  • 解锁JavaScript新姿势：Set数据结构深度解析
  • Unity Shader示例 6: 卡渲基础 - 描边 + 着色
  • 【学术投稿-第四届智能电网和绿色能源国际学术会议（ICSGGE 2025)】CSS基本选择器详解：掌握基础，轻松布局网页
  • 深入剖析 Python 爬虫：淘宝商品详情数据抓取
  • 什么是RDD以及它在Spark中的作用
  • 地基Spring中bean生命周期和设计模式