数据结构第4问：什么是栈？

🕗 发布于 2025-08-01

栈的特点

“栈”这个名字来源于它的形象比喻和数据结构的特点。

栈（Stack）在英文中原意是“堆叠”或者“一摞东西堆起来”，就像我们生活中把盘子或书本一层一层叠放起来一样。这个比喻很形象地反映了栈的数据操作规则：

后进先出（LIFO，last in first out） ：最后放上去的元素（最后入栈）会最先被取出（先出栈），就像你从一摞盘子中拿盘子时，最上面的盘子最容易取出。

因此，把这种后进先出操作的线性数据结构称为“栈”，就是基于这种“堆叠”的形象和操作方式的直观描述。

栈其实就是规定了只允许在一端进行插入或删除操作的线性表。其中：

栈顶（Top）：即线性表允许进行插入和删除操作的一端。
栈底（Bottom）：即不允许进行插入和删除操作的另一端。

栈的基本操作

InitStack(&S);// 初始化一个空栈S
StackEmpty(S);// 判断是否为空栈，是空栈则返回true，不是空栈返回false
Push(&S, x);// 入栈，若栈S未满，则将x加入使之成为新栈顶
Pop(&S, x);// 出栈，若栈S非空，则弹出栈顶元素，并用x返回
GetTop(S,&x);// 读栈顶元素，但不出栈，若栈S非空，则用x返回栈顶元素
DestroyStack(&S);// 销毁栈，并释放栈S占用的内存空间

栈的顺序存储结构

采用顺序存储结构的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设置一个标记（top指针）指示当前栈顶元素的位置。

静态分配内存空间的顺序栈实例

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

#define MaxSize 100

typedef struct
{
    int data[MaxSize];    // 栈元素存放空间
    int top;              // 栈顶指针
}stack;

// 初始化一个空栈S
bool initStack(stack *S)
{
    S->top = -1;    // 第一个栈元素是从0开始的，所以栈顶指针为-1
    return true;
}

// push，入栈，若栈S未满，则将x加入使之成为新栈顶
bool push(stack *S, int data)
{
    if(S->top < MaxSize - 1)
    {
        S->data[++S->top] = data;
        return true;
    }
    return false;
}

// pop，出栈，若栈S非空，则弹出栈顶元素，并用x返回
bool pop(stack *S, int *value)
{
    if (S->top == -1)  // 栈空
        return false;
    if (value != NULL)
        *value = S->data[S->top--];
    return true;
}

// 读栈顶元素，但不出栈，若栈S非空，则用x返回栈顶元素
bool GetTop(stack S,int *value)
{
    if (S.top == -1)  // 栈空判断
        return false;
    if (value != NULL)
        *value = S.data[S.top];
    return true;
}

// 销毁栈，并释放栈S占用的内存空间
bool DestroyStack(stack *S)
{
    S->top = -1;
    return true;
}

// 判断栈空或非空，是空栈则返回true，不是空栈返回false
bool StackEmpty(stack *S)
{
    if(S->top == -1)
        return true;
    else
        return false;
}

栈的链式存储结构

用链式存储结构的栈叫链栈，优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。通常使用单链表来实现，并且规定所有操作在表头进行。链栈有两种区分：有带节点的和不带头节点的。

动态分配内存空间且不带头节点的链栈实例

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

// 链式结构的栈
typedef struct Linknode
{
    int data;
    struct Linknode *next;
} linkstack;

// 无头节点的链栈初始化
bool init_linkstack_no_head(linkstack **L)
{
    *L = NULL;
    return true;
}

// 入栈，适合无头节点的链栈
bool push_node_no_head(linkstack **L, int data)
{
    linkstack *new_node = malloc(sizeof(linkstack));
    new_node->data = data;
    new_node->next = *L;
    *L = new_node;
    return true;
}

// 出栈，适合无头节点的链栈
bool pop_node_no_head(linkstack **L, int *data)
{
    if (*L == NULL)
        return false; // 空栈，无法弹出
    linkstack *node;
    node = *L;
    *data = (*L)->data;
    (*L) = (*L)->next;
    free(node);
    return true;
}

// 读栈顶元素，但不出栈，若栈S非空，则用data返回栈顶元素
bool GetTop_node(linkstack *L, int *data)
{
    if (L == NULL)
        return false;
    *data = L->data;
    return true;
}

// 判断栈空或非空，是空栈则返回true，不是空栈返回false
bool judge_stack_empty(linkstack *L)
{
    if (L == NULL)
        return true;
    else
        return false;
}

// 销毁栈，并释放栈S占用的内存空间
bool destroy_stack_node(linkstack **L)
{
    if (*L == NULL)
        return false;
    linkstack *current;
    while (*L != NULL)
    {
        current = *L;    // 保存当前节点地址
        *L = (*L)->next; // 栈顶指向下一节点
        free(current);   // 释放当前节点
    }
    *L = NULL;
    return true;
}

动态分配内存空间且带头节点的链栈实例

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

// 有头节点的链栈初始化
bool init_linkstack_have_head(linkstack **L)
{
    *L = malloc(sizeof(linkstack));
    if (*L == NULL)
        return false;
    (*L)->next = NULL;
    return true;
}

// 入栈，适合有头节点的链栈
bool push_node_have_head(linkstack *L, int data)
{
    if (L == NULL)
        return false;
    linkstack *new_node = malloc(sizeof(linkstack));
    if (new_node == NULL)
        return false;
    new_node->data = data;
    new_node->next = L->next;
    L->next = new_node;
    return true;
}

// 出栈，适合有头节点的链栈
bool pop_node_have_head(linkstack *L, int *data)
{
    // 空栈或者栈内只有头节点
    if (L == NULL || L->next == NULL)
        return false; 
    // 创建临时变量存放要弹出的栈元素
    linkstack *node = L->next;
    *data = node->data;
    L->next = node->next;
    free(node);
    return true;
}

// 读栈顶元素，但不出栈，若栈S非空，则用data返回栈顶元素，适合有头节点的链栈
bool GetTop_node_have_head(linkstack *L, int *data)
{
    if (L == NULL || L->next == NULL)
        return false;
    *data = L->next->data;
    return true;
}

// 判断栈空或非空，是空栈则返回true，不是空栈返回false，适合有头节点的链栈
bool judge_stack_empty_have_head(linkstack *L)
{
    if (L == NULL || L->next == NULL)
        return true;
    else
        return false;
}


// 销毁栈，并释放栈S占用的内存空间，适合有头节点的链栈
bool destroy_stack_node_have_head(linkstack **L)
{
    // 头指针的指针本身不存在 或 头指针指向空，没有头节点
    // L 本身是一个二级指针，存放了头指针的地址
    // *L 是头指针，即指向链栈第一个节点的指针
    if (L == NULL || *L == NULL)
        return false;
    linkstack *current;
    while (*L != NULL)
    {
        current = *L;    // 保存当前节点地址
        *L = (*L)->next; // 栈顶指向下一节点
        free(current);   // 释放当前节点
    }
    *L = NULL;
    return true;
}

原文地址：https://blog.csdn.net/qq_43940175/article/details/149816232

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Kotlin 实现 MVVM 架构设计总结
下一篇：Java高级工程师面试模拟：高并发秒杀系统设计与实现

【大学院-筆記試験練習：线性代数和数据结构（７）】
为了升到自己目标的大学院，所作的努力和学习，这里是线性代数和数据结构部分。训练成长。！！
阅读更多2026-01-14
鸿蒙应用的性能优化与用户体验提升实战：智能待办的极致优化
本文介绍了鸿蒙应用性能优化与用户体验提升的实战方案，以《全生态智能待办》为例，详细阐述了性能分析工具使用和优化方法。文章首先概述了学习目标，包括掌握性能分析工具、落地优化方案等。随后重点介绍了三种性能
阅读更多2026-01-14
驾驭 CPU 与编译器：Apache Doris 实现极致性能的底层逻辑
Apache Doris 的演进给我们提供了一个生动的答案——它不仅跟随硬件与编译器的发展而演进，更主动地通过向量化、模板化、指令级并行与精细的用户态调度模式，将每一代 CPU 的潜力推向理论极限。
阅读更多2026-01-14
[小技巧24]MySQL 命令行提示符(Prompt)自定义：从入门到精通
MySQL 命令行提示符自定义：从入门到精通
阅读更多2026-01-14
易语言开发从入门到精通：答疑解惑·踩坑避坑·优化提升·常用资源
本文是《易语言开发从入门到精通》的查漏补缺与进阶实战辅助章节，聚焦解决开发中的高频问题与优化提升。主要内容包括：高频问题解答：覆盖中文编程语法、事件驱动机制、数据存储、跨语言通讯等100个核心疑问，
阅读更多2026-01-14
XGSLab | 接地系统和电磁分析软件视频教程
XGSLab接地系统和电磁分析软件视频教程学习
阅读更多2026-01-14
51 单片机入门详解：从基础概念到实战开发
51 单片机作为嵌入式开发的入门利器，其核心在于理解 “硬件与软件的结合”—— 从基础的概念辨析，到硬件引脚的控制，再到程序的编写、编译、下载和调试，每一个步骤都需要我们动手实践、不断总结。本文从基础
阅读更多2026-01-14
java学习--ArrayList
ArrayList是Java中基于动态数组的List实现，支持快速随机访问(O(1))但增删效率较低(O(n))。核心特性包括：动态扩容（默认1.5倍）、允许null值和重复元素、有序存储。常用操作包
阅读更多2026-01-14
【QT】环境搭建收尾：认识Qt Creator
🎬 艾莉丝的简介：从开始菜单或者快捷方式打开QtCreator集成开发环境，启动之后看到类似下面的界面：①：菜单栏。菜单栏一共有8个菜单选项，包含了常用的功能菜单：②：模式选择：③：构建套件选择器。
阅读更多2026-01-14
代码随想录算法训练营DAY13第六章二叉树part01
【代码】代码随想录算法训练营DAY13第六章二叉树part01。
阅读更多2026-01-14