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

数据结构（5）——栈

article 2026/2/11 21:47:50

前言

栈是一种常见的数据结构，其主要作用是存储和管理数据。栈遵循先进后出（FILO）的原则，即最后入栈的元素最先出栈。栈通常用于临时存储数据、函数调用和表达式求值等场景。

一、栈的概念及其结构

栈，是一种特殊的线性表，其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一段叫做栈顶，而另一端就叫栈尾。栈中保持着先进后出，后进先出（Last IN First Out）的原则。

可以理解为往一个盒子里放东西先放的东西放在最底下，后来放的东西在最上面，拿的时候也就是先拿最上面的东西。

往里放的操作就是进栈，而往外取的操作就是出栈（弹栈）。

入栈顺序是1，2，3，4，出栈顺序也可以是1, 2, 3, 4，因为没有规定什么时候出栈，这样就是边进边出。很有意思。

二、栈的实现

2.1说明

栈的实现可以用数组实现，也可以用链表实现，但数组其实是最香的，数组从左到右往栈顶走，唯一的弊端就是有时候会要开辟空间申请内存。用链表的话，就用单链表，因为头插效率很高，所以单链表左端为栈顶，右端为栈低。

另外，栈也分动态的栈或者静态的栈，一般动态的栈用的比较多，而且比较方便。接下来我们来实现一个栈，用一个动态数组实现，其实栈的实现比较简单。

我们要实现的内容如下：

//定义结构体
typedef struct Stack
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//压栈
void STPush(ST* ps, STDataType x);
//弹栈
void STPop(ST* ps);
//栈的元素个数
int STSize(ST* ps);
//检验栈是否为空
bool STEmpty(ST* ps);
//访问栈顶元素
STDataType STTop(ST* ps);

2.2动态栈结构体定义

//动态栈
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;//下标int capacity;
}ST;

动态栈的结构体定义就是以上，一个块内有一个数据域，然后定义一个下标，用来实现后续的操作，还有当前数组的容量，后续可以对其实现更新。数据类型用typedef来定义。

2.3初始化

栈的初始化就是对结构体成员进行初始化，首先要检查结构体所创建的示例有没有，然后这个实例可以用来存储结构体中定义的各个成员变量的值。

//初始化
void STInit(ST* ps)
{assert(ps);ps->a =(STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("ps->a malloc is error::");return;}ps->capacity = 4;//空间为4ps->top = 0;//如果赋值为0的话，这里top就是是下一个要放的数据的下标,也就是栈顶元素的下一个位置//ps->top = -1;//如果赋值为-1，那么就是栈顶元素的位置
}

因为我们要用一个动态数组实现，所以这里用malloc函数来申请4个空间大小的数据位置，对其进行检查，之后定义容量为4，这里top是下标，如果为0，那么就是栈顶下一个元素的位置，这里可能有点小难理解，我们可以想象现在栈里面啥都没有，而我们要放数据，数据放在哪里呢，第一个肯定是放在下标为0的位置，所以当top为0的时候，就是下一个数据要放的位置的下标，而如果我们要放在-1的位置，那么就是当前位置（栈顶元素的位置）。

2.4销毁

销毁栈，因为我们这里栈是用数组来实现的，所以当我们要销毁栈的时候，相当于把数组销毁，也就是结构体成员a。

//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

注意这里销毁可以给a赋为空，其它的成员函数赋值为0。

2.5进（压）栈

进栈当然是含有两个参数，一个是栈的实例，另一个是要进入的数据。这里要注意的地方就是空间的大小，如果空间被占满了，就实现扩容。

//压栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("tmp realloc is error::");return;}else ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}

代码中扩容使用realloc进行扩容，每一次是上一次容量的2倍，然后把数据存到下标为top的位置，top往后加加。

2.6检验栈是否为空

我们写这个函数的目的是为了规范，把每一个功能都可以用函数来实现，一目了然。

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

检验是否为空就是检查ps->top是否为0，如果为0的话，代表当前存的下一个数据的位置下标为0，就相当于里面并没有压入数据，真为1，假为0。

2.7弹（出）栈

出栈好出啊，就相当于把top--就可以了。当然这里用assert检验一下栈是否有实例和栈是否为空。

//弹栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}

2.8栈的元素个数

返回栈的元素个数也十分的简单，我们知道，top代表的是下一个数据的下标，而我们起始的位置为0，所以虽然top后来又++了，但正好是栈中元素的数量。所以直接返回top就可以。

//栈的元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

2.9访问栈顶元素

我们知道栈只能先进后出，后进先出，所以访问元素只能在栈顶访问，通过弹栈+访问就可以实现对栈中每一个数据的访问。

//访问栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

当然，这里还是要对栈进行检验，是否为空，实例是否存在，然后返回对应栈顶下标的元素。由于top是代表下一个元素的下标，所以栈顶元素的真正下标为当前top-1。

三、运行

这里我们写一个main函数来验证一下我们之前的函数。

#include"Stack.h"int main()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);STPush(&st, 6);//不能直接打印printf("数量：%d \n", STSize(&st));printf("栈：：");while (!STEmpty(&st)){printf("%d ",STTop(&st));STPop(&st);}STDestroy(&st);return 0;
}

如果不运行，阅读上面的代码就是，依次进栈1,2,3,4,5,6，然后打印出栈中元素的个数，打印不能直接打印，应该先访问当前栈顶元素，之后再弹栈，这样栈顶就会往下走一个，反复就可以实现访问栈中每一个元素的目的，应该是6,5,4,3,2,1，最后调用了销毁函数，结束返回0。

我们可以运行一下，运行结果：

总结

这篇文章很详细地介绍了栈的概念、结构以及实现，同时提供了栈的各种操作函数的代码实现。通过这些函数，可以实现栈的初始化、销毁、压栈、弹栈、获取栈元素个数、检验栈是否为空以及访问栈顶元素等功能。文章中的代码示例也展示了如何使用这些函数来对一个栈进行操作，包括进栈、出栈、获取栈中元素个数以及访问栈顶元素等操作。

总体而言，这篇文章对栈的基本概念和实现进行了很好的介绍，对于想要了解栈及其实现细节的读者来说，是一份很有帮助的参考材料。

目录

前言