数据结构中栈的全面实现揭秘

3天前发布 gsjqwyl

5 0 0

数据结构里栈的完整实现深度剖析

栈的完整实现

GitHub地址
前言
栈的定义
相关术语介绍
压栈
出栈
栈的定义以及相关的接口
各个接口的实现
初始化
销毁
判断栈是否为空
入栈
出栈
获取栈顶元素
获取栈中的有效元素个数
所有代码一览
功能测试
结语

栈的完整实现

GitHub地址

有梦想的电信狗

前言

在计算机科学领域，栈是极为基础且关键的数据结构。无论是函数调用时的栈、表达式求值场景，还是浏览器历史记录的管理，都能看到栈的应用。掌握栈的实现原理及应用场景，是程序员进阶的重要环节。本文将通过C语言实现一个完整的动态顺序栈，深入剖析栈的初始化、压栈、出栈等核心操作。无论你是刚接触数据结构的新手，还是想巩固底层实现的老手，本文都会为你提供清晰的实现思路与可复用的工业级代码模板。

栈的定义

栈是一种特殊的线性表，它仅允许在固定一端进行插入和删除元素操作。其中，进行数据插入和删除的那一端称为栈顶，另一端称为栈底。压栈是将元素插入栈的操作，也叫进栈或入栈，插入的数据在栈顶；出栈是从栈中删除元素的操作，删除的数据同样在栈顶。栈里的数据元素遵循后进先出（LIFO）原则。如图所示：
在这里插入图片描述
栈本质是特殊线性表，本篇用C语言以顺序表形式实现栈。

栈的定义以及相关的接口

#define INIT_CAPACITY 4
typedef int StackDataType;      //括号匹配需要把 int 换成char

typedef struct Stack {
    StackDataType* base;
    int top;    //top表示栈顶元素的下一个位置
    int capacity;
}Stack;

//初始化与销毁
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);

//入栈与出栈
void StackPush(Stack* ps, StackDataType ele);
void StackPop(Stack* ps);

StackDataType StackTop(Stack* ps);  //获取栈顶元素
bool StackEmpty(Stack* ps);     //判断是否为空

int StackSize(Stack* ps);   //获取栈中有效元素个数

需注意，此栈实现中，top代表栈中最后一个元素的后一个位置，栈空时top为0，top值即栈中数据个数。结构体中top是栈顶元素下标的后一个位置，base是动态申请空间首地址，capacity是栈能容纳的最大元素个数，下文阐述各接口实现。

各个接口的实现

初始化

//初始化
void StackInit(Stack* ps) {
    assert(ps);
    ps->base = (StackDataType*)malloc(sizeof(StackDataType) * INIT_CAPACITY);
    if (ps->base == NULL) {
        perror("malloc failed\n");
        return;
    }
    ps->capacity = INIT_CAPACITY;
    ps->top = 0;    //top是栈顶元素的下一个位置
}

assert(ps)防止接收空指针，确保栈存在。
开辟连续空间存栈数据，确保申请成功，初始容量为INIT_CAPACITY，初始化top为0表示栈空。

销毁

void StackDestroy(Stack* ps) {
    assert(ps);

    free(ps->base);
    ps->base = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

assert(ps)断言栈存在。
释放申请的数组空间，置base为NULL，设置capacity和top为0，安全销毁栈。

判断栈是否为空

//判断是否为空
bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->top == 0;
}

栈空时top为0，直接判断top是否为0。

入栈

//入栈
void StackPush(Stack* ps, StackDataType ele) {
    assert(ps);
    if (ps->top == ps->capacity) {  //如果满了,就扩容
        StackDataType* newSpace = (StackDataType*)realloc(ps->base, sizeof(StackDataType)*ps->capacity * 2);
        if (newSpace == NULL) {
            perror("realloc failed");
            return;
        }
        ps->base = newSpace;
        ps->capacity *= 2;
    }
    //放数据
    ps->base[ps->top++] = ele;
}

assert(ps)确保栈存在，栈满时扩容，扩容后存入数据。

出栈

void StackPop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));    //不能一直出栈，检查栈是否为空

    ps->top--;
}

assert(ps)和assert(!StackEmpty(ps))确保栈存在且非空，出栈只需top--。

获取栈顶元素

//获取栈顶元素
StackDataType StackTop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->base[ps->top-1];
}

assert(ps)和assert(!StackEmpty(ps))确保栈存在且非空，栈顶元素下标为top-1。

获取栈中的有效元素个数

int StackSize(Stack* ps) {
    assert(ps);
    return ps->top;
}

栈中元素个数为top值，直接返回top。

所有代码一览

#define INIT_CAPACITY 4
typedef int StackDataType;      //括号匹配需要把 int 换成char
typedef struct Stack {
    StackDataType* base;
    int top;    //top表示栈顶元素的下一个位置
    int capacity;
}Stack;

//初始化与销毁
void StackInit(Stack* ps) {
    assert(ps);
    ps->base = (StackDataType*)malloc(sizeof(StackDataType) * INIT_CAPACITY);
    if (ps->base == NULL) {
        perror("malloc failed");
        return;
    }
    ps->capacity = INIT_CAPACITY;
    ps->top = 0;    //top是栈顶元素的下一个位置
}
void StackDestroy(Stack* ps) {
    assert(ps);

    free(ps->base);
    ps->base = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

//入栈与出栈
void StackPush(Stack* ps, StackDataType ele) {
    assert(ps);
    if (ps->top == ps->capacity) {  //如果满了,就扩容
        StackDataType* newSpace = (StackDataType*)realloc(ps->base, sizeof(StackDataType)*ps->capacity * 2);
        if (newSpace == NULL) {
            perror("realloc failed");
            return;
        }
        ps->base = newSpace;
        ps->capacity *= 2;
    }
    //放数据
    ps->base[ps->top++] = ele;
}
void StackPop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));    //不能一直出栈，检查栈是否为空

    ps->top--;
}

//获取栈顶元素
StackDataType StackTop(Stack* ps) {
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->base[ps->top-1];
}

//判断是否为空
bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->top == 0;
}

//获取栈中有效元素个数
int StackSize(Stack* ps) {
    assert(ps);
    return ps->top;
}

功能测试

可对上述栈进行功能测试，测试代码如下：

#include "Stack.h"

void StackTest() {
    Stack st;
    StackInit(&st); //初始化
    StackPush(&st, 1);  //入栈
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    StackPush(&st, 5);

    //出栈
    while (!StackEmpty(&st)) {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    //销毁栈
    StackDestroy(&st);
}
int main() {

    StackTest();
    return 0;
}

栈无法遍历，通过不断获取栈顶元素并出栈实现遍历测试，代码符合后进先出特性。

结语

通过本文学习，实现了栈的核心功能。栈简洁高效，是解决“后进先出”类问题的利器。数据结构学习不仅要实现，更要理解设计思想并灵活应用。建议实践方向：1.将顺序栈改为链式栈实现；2.用栈实现表达式求值器；3.探索操作系统中栈的应用（如中断处理栈）。实践中遇问题可在评论区交流，思维碰撞促技术进步。若文章有帮助，欢迎点赞收藏；有疑问建议可留言，共同进步。分享结束，一键三连，好运相随！你的互动是对作者最大鼓励，征程未完，继续前行！

文章版权归作者所有，未经允许请勿转载。