栈——顺序栈和链式栈

不染尘.

1441人浏览 · 2025-10-18 23:56:05

不染尘. · 2025-10-18 23:56:05 发布

栈——顺序栈和链式栈

文章目录

栈——顺序栈和链式栈

一、前言

本篇将带来另一种结构——栈。栈不是凭空想出来的，它的底层还是表。栈是表的一种变体，是在表的基础上增加了只能在一头进和出的约束。真的是“约束”吗？但是它在解决某一类问题上却是比表还权威的存在。接下来，我将对栈进行一个深入解读~

二、栈的概述

2.1 定义

栈（Stack）是一种后进先出（Last In First Out, LIFO）的线性表，它限制仅能在表尾（称为栈顶）进行插入和删除操作。这个表尾被称为栈顶（top），与之相对的表头则称为栈底（bottom）。

栈的本质是表，所以栈的种种特征和表有很大的相似。包括存储位置，物理结构等。

如图：

鉴于栈的特殊逻辑，所以画的图和它的逻辑相匹配。但请记住，它的本质还是表~

在这里插入图片描述

2.2 分类

栈和表一样，分为顺序栈，链式栈等。

本篇仅对顺序栈和链式栈进行分析。

尽管顺序栈同样可以实现动态拓展（动态数组），但是鉴于链式结构的极致灵活性和稳定性能，这里的顺序栈不再有动态拓展的性能，仅是具有一定约束的普通数组~
链式栈则和链表差不多。

各种特质之间是相互制约，各有所长的。在实际的工程中，尽量做出更为合乎“中庸”之道的选择，以不至于。

2.3 优缺点辨析

特性维度	顺序栈	链式栈
容量管理	固定大小，需预先分配	动态调整，按需分配
空间效率	可能浪费或不足	无闲置空间，但有指针开销
操作速度	O(1)，缓存友好	O(1)，但常数时间可能稍高
实现复杂度	简单直观	相对复杂，需处理指针
内存开销	较低，仅存储元素	较高，每个元素需额外指针空间

2.4 应用

撤销操作/历史记录（ctrl + z undo）：将每次操作压入栈，撤销时从栈顶弹出以恢复状态。（链式栈）
浏览器前进/后退：一个栈存放已访问页面，另一个栈存放通过后退跳转的页面。（链式栈）
记录轨迹：如：寻障小车，走迷宫等。（链式栈）
深度优先搜索（ $D FS$ ）：存放当前探索路径节点，回溯时弹出栈顶节点。（顺序栈）

后面会详细讲解~
表达式求值：编译器在处理数学表达式时，通常会使用两个栈：一个称为“数栈”，用于存放数字；另一个称为符号栈，用于存放运算符。算法从左到右扫描表达式：
- 遇到数字则直接压入数栈。
- 遇到运算符时，会与符号栈栈顶的运算符比较优先级。如果当前运算符优先级低于或等于栈顶运算符，则从数栈弹出两个数字，从符号栈弹出一个运算符进行计算，将结果压回数栈，然后再将当前运算符入栈；如果优先级更高，则直接入栈。
- 当表达式扫描完毕，再按顺序将剩余符号弹出并计算，最终数栈中唯一的数字就是表达式的结果。这种方法巧妙地利用了栈处理了运算符的优先级（顺序栈）
括号匹配：检查一段代码或文本中的括号（如 (), [], {}）是否配对正确。算法流程是：遍历字符串，每当遇到一个左括号（如 (, [, {），就将其压入栈中；每当遇到一个右括号，则检查栈顶的左括号是否能与之配对。如果配对成功，则将栈顶的左括号弹出；如果配对失败或栈已空，则说明括号不匹配。当整个字符串遍历完成后，如果栈恰好为空，则说明所有括号都正确匹配。（顺序栈）

选择合适场景的栈结构是尤为重要的，这需要我们明确不同栈结构的特点。

尤其是两者在数量上的差异，顺序栈数量确定，链式栈常用于数量不确定的。

三、顺序栈

3.1 头结构

栈是固定大小的，满了之后就不能插入了（否则会把别人的空间改了），因此这里的头结构需要定义一个静态数组（而不再是指针）。
数组是固定内存，指针可以指向任何内存块，随时可以改变指向。
为了便于访问位置，需要定义一个变量。

// 定义栈的容量（方便修改）
#define MaxStackSize	5
typedef int Element;
// 定义头结构，这个空间放在哪里(存储空间)都可以
typedef struct
{
    Element data[MaxStackSize];
    int top;
} ArrayStack;

3.2 初始化和销毁

初始化和创建（自己申请）的区别？

创建：数据结构自己申请（malloc/new）。
初始化：数据结构的调用者（main函数等）。

如图：

在这里插入图片描述

代码：

// 初始化
void initArrayStack(ArrayStack *stack)
{
    // 元素清空
    memset(stack->data, 0, sizeof(stack->data));
    stack->top = 0;
}
// 销毁
void destroyArrayStack(ArrayStack *stack)
{
    
}

3.3 入栈（压栈）

入栈有很多方式。如下：指针指向待插入位置——空栈，指向待插入位置——满栈；递增递减永远指插入时的递增递减。照这样两两组合形成4种入栈方式。代码如下：

// 压栈
// 递增空栈
a1.data[a1.pos] = e;
a1.pos++;

// 递增满栈
a1.pos++;
a1.data[a1.pos] = e;

// 递减满栈
a1.pos--;
a1.data[a1.pos] = e;

// 递减空栈
a1.data[a1.pos] = e;
a1.pos--;

这里以递增空栈为例进行分析（可自行选择），但请注意入栈和出栈的配套形式！！！

如图：

在这里插入图片描述

代码：

// 入栈
int pushArrayStack(ArrayStack *stack, Element e)
{
    stack->data[stack->top] = e;
    ++stack->top;
}

3.4 出栈

和入栈对应的出栈操作代码如下4种：

// 出栈	一定注意要和压栈一一配对
// 递增空栈
a1.pos--;
x = a1.data[a1.pos];

// 递增满栈
x = a1.data[a1.pos];
a1.pos--;

// 递减满栈
e = a1.data[a1.pos];
a1.pos++;

// 递减空栈
a1.pos++;
e = a1.data[a1.pos];

这里对应入栈的递增空栈的操作。

代码实现如下：

出栈不需要把里面的元素像擦黑板一样清除~

为什么不清理，而是只是改变指针指向呢？
这涉及关注点分离的软件设计原则。在数据结构中，更关注逻辑结构。至于元素的事，是资源管理系统的职责，有的需要手动释放（free/delete），有的则是由程序自动垃圾回收。

// 出栈
int popArrayStack(ArrayStack *stack)
{
    --stack->top;
}
// 只是关注最上面（栈顶）出的元素，不关注操作
Element getTopArrayStack(const ArrayStack *stack)
{
    int pos = stack->top - 1;	// 注意：这里的top指向并没有变
    return stack->data[pos];
}

3.5 判断空栈/满栈

对空栈/满栈的判断决定了入栈/出栈的边界。

// 判断空栈
int isEmptyArrayStack(const ArrayStack *stack)
{
    return stack->top == 0;
}
// 判断满栈
int isFullArrayStack(const ArrayStack *stack)
{
    return stack->top == MaxStackSize;
}

四、链式栈

4.1 头结构

链式栈像链表一样，有分散的节点。这里封装一个结构体，存储top指针和节点数量。

还能用指针标记栈顶吗？答案是不能。因为在插入节点时，指针作为局部变量（传入的是地址的拷贝），它的修改是没有任何意义的，并没有改变原来指针的指向。

如果是封装结构体的话，这里可以虽然也是拷贝的地址，但是可以通过指针解引用修改其指向的数据。

如图：

在这里插入图片描述

代码：

// 定义节点结构
typedef struct _node
{
    Element data;
    struct _node *next;
} StackNode;
// 定义头结构
typedef struct
{
    StackNode *top;
    int count;
} LinkStack;

4.2 创建和销毁

这里还是将链式栈存储在堆上，以实现动态扩展。

如图：

在这里插入图片描述

代码：

// 链式栈的创建
LinkStack* createLinkStack()
{
    LinkStack *link_stack = malloc(sizeof(LinkStack));
    if (link_stack == NULL)
    {
        fprintf(stderr, "linkStack malloc failed!\n");
        return NULL;
    }
    link_stack->top = NULL;
    link_stack->count = 0;

    return link_stack;
}
// 销毁
void releaseLinkStack(LinkStack* stack)
{
    if (stack)
    {
        if (stack->top)
        {
            StackNode *tmp = stack->top;
            stack->top = tmp->next;
            free(tmp);
            --stack->count;
        }
        printf("stack count:%d", stack->count);
    }
}

4.3 入栈

如图：

在这里插入图片描述

代码：

int pushLinkStack(LinkStack* stack, Element e)
{
    StackNode *node = malloc(sizeof(StackNode));
    if (node == NULL)
    {
        fprintf(stderr, "Stack Node malloc failed!\n");
        return -1;
    }
    node->data = e;

    node->next = stack->top;
    stack->top = node;
    ++stack->count;
    return 0;
}

4.4 出栈

top指哪弹哪。（备份思想）

如图：

在这里插入图片描述

代码：

int popLinkStack(LinkStack* stack, Element* e)
{
    if (stack->top == NULL)
    {
        fprintf(stderr, "stack empty!\n");
        return -1;
    }
    *e = stack->top->data;      // 要把栈里面的值取出来，更新弹出的值
    StackNode *tmp = stack->top;
    stack->top = tmp->next;
    free(tmp);
    --stack->count;
    return 0;
}