[数据结构 -- C语言] 栈(Stack)

这篇具有很好参考价值的文章主要介绍了[数据结构 -- C语言] 栈(Stack)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1、栈

1.1 栈的概念及结构

2、栈的实现

2.1 接口

3、接口的实现

3.1 初始化

3.2 入栈/压栈

3.3 出栈

3.4 获取栈顶元素

3.5 获取栈中有效元素个数

3.6.1 bool 类型接口

3.6.2 int 类型接口

3.7 销毁栈

4、完整代码

5、功能测试


1、栈

1.1 栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。
栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

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

[数据结构 -- C语言] 栈(Stack)

我们以生活中的事物来理解一下栈:糖葫芦

串糖葫芦的时候是最后一颗糖葫芦先串进去,但是我们吃的第一个却是最后一颗被串上去的。

[数据结构 -- C语言] 栈(Stack)

2、栈的实现

栈的实现一般可以使用 数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。 我们本篇文章就是使用数组来实现栈。

2.1 接口

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

3、接口的实现

3.1 初始化

我们的栈开始是空的,因此容量与栈顶赋值为 0。

我们也可以将栈顶赋值为-1,入栈的时候先让栈顶指针++,再将元素入栈,这样栈顶指针正好指向的就是栈顶元素。但是我们这里还是将栈顶指针赋值为 0 了,这样在获取栈中有效元素的时候就不用再操作了,为后面提供了便利。

void StackInit(Stack* ps)
{
	assert(ps);

	ps->a = NULL;
	//ps->top = -1;//top 指栈顶数据
	ps->top = 0;//top 指栈顶数据的下一个位置
	ps->capacity = 0;
}

3.2 入栈/压栈

在入栈前我们要先判断栈是否满了,如果满了我们就给栈先进性扩容。我们这里没有开始先malloc空间,而是第一次就使用了 realloc,这里有一个技巧,那就是用三目操作符先看容量是否为 0 ,如果是 0 ,那么就意味着是第一次开空间,就给 newcapacity 赋值为 4,不为 0就说明是扩容,那就将新的容量扩容为之前的 2 倍。

判满后我们就入栈,这里其实就是给数组里面放元素进去,给栈顶位置放一个元素进去后让 ps->top++,往后走一步。

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = data;
	ps->top++;
}

3.3 出栈

出栈很简单,让 ps->top--就好了,下次入栈的元素就会将之前的元素覆盖掉。

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

3.4 获取栈顶元素

获取栈顶元素前需要判空,如果是空的话就不存在栈顶指针。栈顶元素就是下标为 top-1 的元素,所以返回 ps->[ps->top-1] 就是栈顶元素。

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];
}

3.5 获取栈中有效元素个数

因为下标 top 是栈顶元素的下一个位置,所以返回 top 就是栈中的有效元素个数。

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

3.6.1 bool 类型接口

int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

3.6.2 int 类型接口

这里我们约定好为空返回 非0,不为空返回 0。

int StackEmpty(Stack* ps)
{
	assert(ps);

	if (0 == ps->top)
		return 1;
	else
		return 0;
}

3.7 销毁栈

释放数组并置空,将容量与栈顶赋值为 0。

void StackDestroy(Stack* ps)
{
	assert(ps);

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

4、完整代码

完整代码在代码仓库,入口:C语言: C语言学习的代码,多复习 - Gitee.com

5、功能测试

[数据结构 -- C语言] 栈(Stack)

[数据结构 -- C语言] 栈(Stack)文章来源地址https://www.toymoban.com/news/detail-448386.html

到了这里,关于[数据结构 -- C语言] 栈(Stack)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空,如果为空返回非零结果,如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈(后进先出,先进后出) : 一种 特殊

    2024年02月01日
    浏览(41)
  • 【数据结构 C语言版】第四篇 栈、堆栈、Stack(超级详细版)

    写在前面 更新情况记录: 最近更新时间 更新次数 2022/10/18 1 参考博客与书籍以及链接: (非常感谢这些博主们的文章,将我的一些疑问得到解决。) 参考博客链接或书籍名称 《数据结构》陈越 代码随想录 总目录:目前数据结构文章太少,没有写。 正文 如果你c语言还有困

    2023年04月09日
    浏览(34)
  • 【数据结构】栈(Stack)实现详解

    🚩 纸上得来终觉浅, 绝知此事要躬行。 🌟主页:June-Frost 🚀专栏:数据结构 🔥该文章主要了解实现栈的相关操作。  栈是一种特殊的线性表,其只允许在 固定的一端 进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底 。栈中的数据元

    2024年02月08日
    浏览(41)
  • 【数据结构】栈(Stack)的实现 -- 详解

    1、概念 栈 :一种特殊的线性表,其只允许在表尾进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底 。栈中的数据元素遵守后进先出 LIFO(Last In First Out)的原则。 压栈 :栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶 。 出栈 :栈

    2024年02月14日
    浏览(44)
  • 【数据结构】 栈(Stack)与栈的模拟实现

    🎈栈:一种特殊的线性表,其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为 栈顶 ,另一端称为 栈底 。 栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则 压栈 :栈的插入操作叫做进栈/压栈/入栈, 入数据在栈顶 。 出栈 :栈的

    2024年02月11日
    浏览(49)
  • 数据结构 C语言 树形结构 简单目录管理系统

    在图书、操作系统文件夹、学生等管理系统中,目录管理是必要环节,如何高效搜寻与低复杂度存储是实现这一环节的关键性问题。本课程设计需完成一种基于多叉树结构简单目录管理系统,该系统能以交互式界面进行创建目录、删除目录、查找目录、修改目录、层次遍历目

    2024年02月04日
    浏览(47)
  • 数据结构 C语言 树形结构 简单目录管理系统

    在图书、操作系统文件夹、学生等管理系统中,目录管理是必要环节,如何高效搜寻与低复杂度存储是实现这一环节的关键性问题。本课程设计需完成一种基于多叉树结构简单目录管理系统,该系统能以交互式界面进行创建目录、删除目录、查找目录、修改目录、层次遍历目

    2024年02月07日
    浏览(48)
  • 一起学数据结构(3)——万字解析:链表的概念及单链表的实现

    上篇文章介绍了数据结构的一些基本概念,以及顺序表的概念和实现,本文来介绍链表的概念和单链表的实现,在此之前,首先来回顾以下顺序表的特点: 1. 顺序表是一组地址连续的存储单元依次存储的线性表的数据结构,逻辑上:顺序表中相邻的数据元素,其物理次序也是

    2024年02月13日
    浏览(54)
  • 【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号

    🌱 栈 是一种特殊的线性表, 只能在一端进行操作 🌱 往栈中 添加 元素的操作,一般叫做 push ( 入栈 ) 🌱 从栈中 移除 元素的操作,一般叫做 pop ,出栈(只能移除栈顶元素),也叫做: 弹出栈顶元素 🌱 后进先出 的原则, L ast I n F irst O ut, LIFO 注意:这里的 栈 与内

    2024年02月13日
    浏览(39)
  • 【数据结构】手撕排序(排序的概念及意义、直接插入和希尔排序的实现及分析)

    目录 一、排序的概念及其运用  1.1排序的概念  1.2排序运用 1.3 常见的排序算法  二、插入排序 2.1基本思想:  2.2直接插入排序:  2.3步骤: 2.4直接插入排序的实现 三、希尔排序( 缩小增量排序 )  3.1希尔排序的发展历史 3.2 希尔排序的思路 ​编辑 gap = 3的思路讲解 3.3 如何

    2024年02月03日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包