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

【数据结构】栈

article 2025/1/13 17:28:03

文章目录

  • 😺前言
  • 栈初始化
  • 栈顶入栈
  • 栈顶出栈
  • 栈体判空
  • 栈的数据个数
  • 获取栈顶元素
  • 栈的销毁
  • 整体代码
  • 😼写在最后

😺前言

  • 👻前面我们学习了链表，总算是跨过一个台阶了，本章带大家轻松一波，领悟一下栈的魅力。
  • 🤡栈是一种较为简单的数据结构，它的主要性质，就是数据后进先出(LIFO)，我们可以利用这一性质，在做某些算法题时，以此为切入点。因此，栈还是挺不错的。

栈初始化

  • 栈的性质是后进先出(不能任意插入删除)，并且只能访问栈顶元素，因此，对数据的入栈和出栈是特别方便的。

在这里插入图片描述

  • 根据栈的这样一个后进先出的性质，我们该如何选择它的底层结构呢？是顺序表的数组还是链表呢？由此我们分析一下。

  • 如果是数组，很容易想到，完全符合对栈的性质的操作，如果是入栈，直接在数组最后一个位置插入即可，空间不够扩容就好，如果是出栈，直接将统计栈顶的变量减一即可，想要获取栈顶的数据，那不也很简单嘛。由此看来，数组还真是不错呢。

  • 如果是链表，入栈只要将数据头插即可，出栈就是头删，获取栈顶数据就是头节点的数据，这样看来，链表也挺不错呢。那么到底是选数组还是链表呢？

我们来看一下数据对比：
在这里插入图片描述

  • 可以看到，对于栈的性质，该表的前面五个特点都没有明显的优与劣，但是最后一个缓存利用率却能分出高下，很明显，实现一个栈，使用数组会更好。（对于什么是缓存利用率，这里就不讲解了，大家自行查找资料噢）

  • 选取了实现栈的底层结构，接下来就是对栈的初始化操作了。

  • 首先需要三个文件（与前面的单链表一样哈哈哈）stack.h，stack.c，test.c，stack.h用来存放一些所需头文件，函数声明以及栈的结构体。stack.c用来实现函数接口，test.c用来测试。

  • 所需头文件：

#include <stdio.h>
// assert断言
#include <assert.h>
// 判空需用到
#include <stdbool.h>
// 动态空间需用
#include <stdlib.h>
  • 接下来就对控制栈的结构体进行创建：
typedef int STDataType;
typedef struct stack
{
	// 底层数组
	STDataType* a;
	// 容量
	int capacity;
	// 标识栈顶
	int top;
}stack;
  • 接下来是函数声明：
// 初始化
void STInit(stack* pt);
// 入栈
void STPush(stack* pt, STDataType x);
// 出栈
void STPop(stack* pt);
// 判空
bool STEmpty(stack* pt);
// 取栈顶元素
STDataType STTop(stack* pt);
// 栈的元素个数
int STSize(stack* pt);
// 销毁栈
void STDestroy(stack* pt);

怎么样，是不是看了函数接口就很简单呢，只有这些接口噢。

栈的初始化：

  • 对于栈的初始化，我们可以直接将top和capacity置为0，指向存放数据的数组的指针置为NULL。如下：
void STInit(stack* pt)
{
	// 这里断言一下pt是为了防止传递一个NULL指针，正确的应该传递一个结构体的地址
	assert(pt);
	pt->a = NULL;
	pt->capacity = 0;
	pt->top = 0;
}

  • 关于top实际上还可以初始化为-1。但-1与0实际差别不大，只是获取栈顶元素，判空和数据入栈这些代码会有所不同。如果top初始化为-1，那么top就是栈顶元素，如果top初始化为0，top就是栈顶元素的下一个位置。所以我们在实现的时候，要注意这个top。

  • 而本章采用的top为0，也就是top是栈顶元素的下一个位置。

  • top = 0 ，实际上也间接体现了此时栈的数据个数。

栈顶入栈

  • 栈顶入栈就是在数组的最后一个位置添加一个数据即可，操作简单，不过这里要考虑一个扩容的问题。

  • 如果此时空间容量不够(判断条件：top == capacity)，就需要扩容，这里使用realloc扩容，如果开始没有空间，该函数的功能就跟malloc一样。

  • 插入只要在top位置插入即可，最后top要加加一下噢。

下面是相关函数接口的代码实现：

void STPush(stack* pt, STDataType x)
{
	// 防止传递一个NULL
	assert(pt);
	// 检查容量看是否已满，满了就需要扩容
	if (pt->top == pt->capacity)
	{
		int newcapacity = pt->capacity == 0 ? 4 : pt->capacity * 2;
		STDataType* tmp = realloc(pt->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pt->a = tmp;
		pt->capacity = newcapacity;
	}
	// 在top位置放新的的数据，同时top要加一
	pt->a[pt->top++] = x;
}

栈顶出栈

  • 栈顶出栈就是抹去数组最后一个数据，只要top自减一即可。

  • 注意，当栈为空的时候，就不能出栈了，如何判断是否为空？在下面呢，别急哈哈哈。

下面是相关函数接口的代码实现：

void STPop(stack* pt)
{
	// 如果为空就不能删了。判空在后面写到。
	assert(pt && !STEmpty(pt));
	// top减一即可
	pt->top--;
}

栈体判空

  • 栈体判空，只需要判断一下top是否为0即可。如果是0，说明此时栈为空，返回true；如果不等于0，说明此时栈不为空，返回false。

下面是相关函数接口的代码实现：

bool STEmpty(stack* pt)
{
	assert(pt);

	return pt->top == 0;
}

栈的数据个数

  • 前面说了，top就相当于是数据的个数，所以这里直接返回top的值即可。

下面是相关函数接口的代码实现：

int STSize(stack* pt)
{
	assert(pt);
	return pt->top;
}

获取栈顶元素

  • 由于top是最后一个元素的下一个位置，因此获取栈顶元素时，它的位置为top - 1。

下面是相关函数接口的代码实现：

STDataType STTop(stack* pt)
{
	assert(pt && !STEmpty(pt));
	return pt->a[pt->top - 1];
}

栈的销毁

  • 有空间的开辟，那就要有空间的释放，这里称为销毁。

  • 销毁也很简单，只需要将指向栈空间的那个指针free即可。

  • 当然，最后可以将top置为0，capacity也置为0。

下面是相关函数接口的代码实现：

void STDestroy(stack* pt)
{
	assert(pt);

	free(pt->a);
	pt->capacity = 0;
	pt->top = 0;
}

整体代码

stack.h

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int STDataType;
typedef struct stack
{
	STDataType* a;
	int capacity;
	int top;
}stack;

// 初始化
void STInit(stack* pt);
// 入栈
void STPush(stack* pt, STDataType x);
// 出栈
void STPop(stack* pt);
// 判空
bool STEmpty(stack* pt);
// 取栈顶元素
STDataType STTop(stack* pt);
// 栈的元素个数
int STSize(stack* pt);
// 销毁栈
void STDestroy(stack* pt);

stack.c

#include "stack.h"

void STInit(stack* pt)
{
	assert(pt);
	pt->a = NULL;
	pt->capacity = 0;
	pt->top = 0;
}

void STPush(stack* pt, STDataType x)
{
	assert(pt);
	if (pt->top == pt->capacity)
	{
		int newcapacity = pt->capacity == 0 ? 4 : pt->capacity * 2;
		STDataType* tmp = realloc(pt->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pt->a = tmp;
		pt->capacity = newcapacity;
	}
	pt->a[pt->top++] = x;
}
void STPop(stack* pt)
{
	assert(pt && !STEmpty(pt));
	pt->top--;
}

bool STEmpty(stack* pt)
{
	assert(pt);

	return pt->top == 0;
}
STDataType STTop(stack* pt)
{
	assert(pt && !STEmpty(pt));
	return pt->a[pt->top - 1];
}

int STSize(stack* pt)
{
	assert(pt);
	return pt->top;
}

void STDestroy(stack* pt)
{
	assert(pt);

	free(pt->a);
	pt->capacity = 0;
	pt->top = 0;
}

test.c

#include "stack.h"

void test()
{
	stack st;
	STInit(&st);

	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");

	STPush(&st, 5);
	STPush(&st, 55);
	STPush(&st, 555);
	STPush(&st, 5555);
	STPush(&st, 55555);
	STPush(&st, 555555);

	printf("%d\n", STTop(&st));

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");

	STDestroy(&st);
}

int main()
{
	test();

	return 0;
}

😼写在最后

💝到这里，一个简简单单的栈就完成了，是不是很简单呢？不过也别得意哈，后面难的数据结构还没来呢，栈就是让你处于一个平静期，为后来的难度做准备呢哈哈哈哈哈。
❤️‍🔥后续将会持续输出有关数据结构的文章，你们的支持就是我写作的最大动力！

感谢阅读本小白的博客，错误的地方请严厉指出噢~


http://www.kler.cn/a/1059.html

相关文章：

  • 计算机网络 （33）传输控制协议TCP概述
  • 数据分析思维（十一）：应用篇——用数据分析解决问题
  • 笔记本电脑 选购 回收 特权模式使用 指南
  • 6.business english--updates
  • 【Oracle篇】深入了解执行计划中的访问路径(含表级别、B树索引、位图索引、簇表四大类访问路径)
  • DeepSeek：性能强劲的开源模型
  • 嵌入式宏定义中do...while(0)的意义
  • 【蓝桥杯专题】 贪心（C++ | 洛谷 | acwing | 蓝桥）
  • 爆g肝整理，jmeter性能测试（动态性能场景）资深测试怎么做的......
  • elasticsearch的入门使用02
  • 提升Python代码性能的六个技巧
  • 项目管理之项目的进度与挣值计算问题
  • 持续集成 在 Linux 上搭建 Jenkins，自动构建接口测试
  • 【数据结构】栈的实现
  • android逆向攻防01-http抓包
  • 你是真的“C”——实用memory类库函数的详细实现和使用
  • 全新升级，EasyV 3D高德地图组件全新上线
  • storybook添加全局样式与sass全局变量设置
  • Android 马甲包 google市场混淆技术方案
  • 圣帕特里克 VoxEdit 大赛
  • CGAL 点云上采样
  • 关于我拒绝了腾讯测试开发岗offer这件事
  • 【Java】你真的懂封装吗？一文读懂封装-----建议收藏
  • [网络原理] 网络中的基本概念
  • 数据结构与算法——栈和队列＜也不过如此＞
  • 考虑充电负荷空间可调度特性的分布式电源与电动汽车充电站联合配置方法（Matlab代码实现）