数据结构入门：基于数组的栈结构实现详解

人理解迭代，神理解递归。

---

引言： 当熟练驾驭了结构复杂、指针纵横的双链表后，是否意味着需要更复杂的数据结构来挑战自己？恰恰相反。接下来登场的「栈」，它摒弃了链表的灵活多变，只在一端固守'后进先出'的准则。看似简单的约束，实则培养精准操作与算法思维的绝佳'内功心法'，更是平稳过渡到「队列」的坚实桥梁。

---

一、栈的概念和结构

1.1 栈的定义

--栈：一种特殊的线性表，只允许在固定的一端进行插入和删除操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素**遵守'后进先出'**的原则。

其中，插入、删除分别称为：

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈，出数据也在栈顶。

可以将栈的结构形象的看成水杯，在进行接水（进栈）在杯顶（栈顶），进行倒水也是（出栈）在杯顶（栈顶）。

1.2 栈的基本结构

问题？--栈的底层实现是数组（顺序表）呢？还是链表呢？

一般栈的实现，数组、链表都可以。但是对结构、复杂度的考虑：选择数组——将数组的尾部作为栈顶，数组首部作为栈底，而且尾部操作时间复杂度都是 O(1)。

--链表其实也可以实现，只不过是在头部进行操作，且时间复杂度：O(1)

--那为什么数组实现更好呢？

时间一样，那就看空间复杂度——

• 实现顺序表时，每次申请空间（比如 int）虽然是呈 2 倍增加，但是申请的是 4 个字节的倍数。
• 但链表则是每插入一个数据要申请一个节点大小的空间，空间较数组而言有点大。

// Stack.h //定义栈的结构
typedef int STDataType;
typedef struct Stack {
    STDataType* arr;
    int top; //指向栈顶的位置---刚好就是栈中有效数据个数
    int capacity;//栈的空间大小
}ST;

--为什么底层实现与顺序表相同，不用 size 表示有效数据个数？

用 top 更能形象的表示这里栈顶，根据下标，则有效数据个数在 top-1 位。

---

二、栈的初始化、销毁

2.1 初始化

在正式使用栈时，对栈结构进行初始化：

// Stack.c
#include"Stack.h"
//初始化
void STInit(ST* ps) {
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

--因为要改变栈的结构（在定义结构时并没有进行任何赋值操作），所以要进行传址调用，用二级指针接收。

--初始时，指针指向空（还没有开辟空间），其余指向 0（栈顶、空间根据下标在 0 的位置）。

// test.c
#include"Stack.h"
void test01() {
    ST st;
    STInit(&st);//改变结构
}
int main() {
    test01();
    return 0;
}

--定义变量不是指针变量？

这就是与链表的区别——栈底层是数组，其存储数据的空间是连续的，因此不需要额外定义指针变量指向空间；而链表节点的空间不一定连续，就需要通过指针进行地址链接。

传地址，形参的改变影响实参。

2.2 销毁

销毁操作与初始化相同，只不过多加一步-->判空，如果数组 arr 为空，代表没有进行开辟空间。

// Stack.h
#include"Stack.h"
//销毁
void STDestroy(ST* ps) {
    if (ps->arr)//为空，没进行初始化
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

--销毁就是将后续进行的入栈（放入数据）等操作重置：将空间释放，指针重新指向空，其余置零。

---

三、栈基本功能实现

对于各种功能的实现，其算法原理与顺序表相关算法大同小异。

3.1 入栈（在栈顶放入数据）

// Stack.c
#include"Stack.h"
//入栈——栈顶
void STPush(ST* ps, STDataType x) {
    assert(ps); 
    //判断空间是否足够
    if (ps->top == ps->capacity) {
        //增容
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        //临时变量，防止扩容失败
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    //空间足够
    ps->arr[ps->top++] = x;
}

--空间的判断：与顺序表一致，当 top = capacity 时，代表后面没有位置了，采用 *2 倍扩容。

--断言 ps：传的结构体变量指向这块结构体空间，不能传空地址。

// test.c
#include"Stack.h"
void test01() {
    ST st;
    STInit(&st);//改变结构
    STPush(&st, 1);
    STPush(&st, 2);
    STPush(&st, 3);
    STPush(&st, 4);
}
int main() {
    test01();
    return 0;
}

3.1.1 定义判空（准备工作）

在实现出栈之前，我们先要实现一个判空操作的接口。

//栈是否为空
bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}

top 当处于下标 0 的位置，代表没有数据，栈为空。

3.2 出栈（栈顶）

出栈与实现顺序表的删除算法一样，只用将栈顶缩减，后续的入栈就会将旧数据覆盖。

// Stack.c
#include"Stack.h"
//出栈--栈顶
void STPop(ST* ps) {
    assert(!STEmpty(ps));
    ps->top--;//栈顶缩减一位
}

3.3 取栈顶元素

说是栈顶元素，看上面的图示，其实就是下标 top - 1 位的元素。

// Stack.c
#include"Stack.h"
//取栈顶元素
STDataType STTop(ST* ps) {
    assert(!STEmpty(ps));
    return ps->arr[ps->top - 1];//返回栈顶元素，实际是下标 top-1 位
}

// test.c
#include"Stack.h"
void test1() {
    ST ps;
    STInit(&ps); 
    //入栈
    STPush(&ps, 1);
    STPush(&ps, 2);
    STPush(&ps, 3);
    STPush(&ps, 4);
    while (!STEmpty(&ps)) {
        //取栈顶元素，打印
        STDataType top = STTop(&ps);
        printf("%d ", top);
        //出栈
        STPop(&ps);
    }
    printf("\n");
}
int main() {
    test1();
}

代码中的循环就相当于循环出栈顺带将栈顶元素打印出来。

--根据图示，就体现了'先进后出'或'后进先出'的原则。

3.4 获取有效数据个数

获取有效数据个数，只需要在入栈操作完成后，返回 top 值就行了。

// Stack.c
#include"Stack.h"
//获取栈中有效元素个数
int STSize(ST* ps) {
    assert(ps);
    return ps->top;
}

---

四、实现栈的完整代码

至此，栈的实现已经全部完成，部分实现的思路与顺序表大差不差。

4.1 Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//定义栈的结构
typedef int STDataType;
typedef struct Stack {
    STDataType* arr;
    int top; //指向栈顶的位置---刚好就是栈中有效数据个数
    int capacity;//栈的空间大小
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈--栈顶
void STPop(ST* ps);
//判空
bool STEmpty(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);

4.2 Stack.c

#include"Stack.h"
//初始化
void STInit(ST* ps) {
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}
//销毁
void STDestroy(ST* ps) {
    if (ps->arr)//为空，没进行初始化
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}
//入栈--栈顶
void STPush(ST* ps, STDataType x) {
    assert(ps); 
    //判断空间是否足够
    if (ps->top == ps->capacity) {
        //增容
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    //空间足够
    ps->arr[ps->top++] = x;
}
//栈是否为空
bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}
//出栈--栈顶
void STPop(ST* ps) {
    assert(!STEmpty(ps));
    ps->top--;//栈顶缩减一位
}
//取栈顶元素
STDataType  {
    assert(!STEmpty(ps));
     ps->arr[ps->top - ];
}

  {
    assert(ps);
     ps->top;
}

4.3 test.c

#include"Stack.h"
void test1() {
    ST ps;
    STInit(&ps); 
    //入栈
    STPush(&ps, 1);
    STPush(&ps, 2);
    STPush(&ps, 3);
    STPush(&ps, 4);
    //打印有效数据个数
    printf(":%d\n", STSize(&ps));
    while (!STEmpty(&ps)) {
        //取栈顶元素，打印
        STDataType top = STTop(&ps);
        printf("%d ", top);
        //出栈
        STPop(&ps);
    }
    printf("\n");
}
int main() {
    test1();
}

---

结语： 至此，我们对「栈」的探索已告一段落。它用'后进先出'的简单规则，为我们展示了数据结构中'约束'的魅力。从双链表的灵活到栈的专一，我们不仅学会了一种新结构，更学会了一种聚焦核心问题的思维。当栈的操作已内化于心，我们便做好了准备，去迎接下一个遵循'先进先出'规则的伙伴——队列。届时，一个更宏大的数据结构世界将在我们面前展开。