广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言超详细讲解栈的实现及代码
  • 832

0
分享到

C语言超详细讲解栈的实现及代码

2024-04-02 19:04:59 832人浏览 独家记忆
摘要

目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码Stack.h 文件Stack.c 文件Test.c 文件前言 栈

前言

栈的概念

  • 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。有点类似于手枪弹夹，后压进去的子弹总是最先打出，除非枪坏了。
  • 压栈：栈的插入操作叫做进栈/压栈/入栈。（入数据在栈顶）
  • 出栈：栈的删除操作叫做出栈。（出数据也在栈顶）

注意：

1、函数调用也有栈，这两个栈有区别吗？

当然有区别。函数调用会调用栈帧，内存里头也有一个栈，程序运行起来时要执行函数，函数里头的局部变量、参数、返回值等等都要存在函数栈帧里头。

这两个栈没有任何关联，一个是数据结构中的栈。另一个是操作系统中内存划分的一个区域，叫做栈，用来函数调用时，建立栈帧。虽然本质上没有任何关联，但都符合后进先出的规则。

2、假设入栈顺序为：1 2 3 4，那么出栈顺序一定为：4 3 2 1 吗？

当然不是。虽说规则上明确后进先出，可这是相对而言的，如果说它每进一个再出一个，然后再继续压栈，那不同样符合后进先出的规则吗。就如同上例，你说它出栈顺序为1 2 3 4 都不足为奇，每进一个出一个再进，同样符合规则。类似的入栈两个再出再进再出也是可以的，好比如2 1 4 3。

栈的结构

栈的实现

创建栈结构

Stack.h 文件：

//创建栈结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //存储数据
	int top; //栈顶的位置
	int capacity; //容量
}ST;

初始化栈

思想：

初始化还是相对比较简单的，学了之前的顺序表，初始化栈就很轻松了

Stack.h 文件：

//初始化栈
void StackInit(ST* ps);

Stack.c 文件：

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

注意：

​​​这里初始化的时候将top置为0是有意图的。首先，由上文创建栈结构时已经标注了，top是用来记录栈顶的位置，既然是栈顶的位置，那当top初始化为0时，我们可以直接将数据放入栈中，随后top++，但是当top初始化为-1时，top首先要++才能放入数据，因为数据不可能在负数不属于栈的位置上放入。下图演示过程：

 本文以 top = 0 示例

销毁栈

思想：

动态开辟的内存空间一定要释放，free置空即可，并把其余数据置0。

Stack.h 文件：

//销毁栈
void StackDestory(ST* ps);

Stack.c 文件：

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

入栈

思路：

前文已经强调了top初始化为0，那么理应直接压入数据，并把top++，不过在这之前，得判断空间是否够，当top=capacity的时候，栈就满了，那么就需要realloc扩容。

Stack.h 文件：

//压栈
void StackPush(ST* ps, STDataType x);

Stack.c 文件：

//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果栈满了，考虑扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//将数据压进去
	ps->top++;//栈顶上移
}

出栈

思路：

在你出栈之前，要确保top不为空，而top不为空的条件就是top>0，所以还要断言top>0，随后，直接将栈顶位置下移--即可。跟顺序表的思想大同小异。

Stack.h 文件：

//出栈
void StackPop(ST* ps);

Stack.c 文件：

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

获取栈顶元素

思路：

首先要搞清楚谁才是栈顶元素，是top位置还是top-1位置？很显然是top-1的位置才是栈顶元素，因为在前文初始化的时候已经明确指出top为0，当时压栈时直接放入数据的，此时第一个数据下标为0，随后++top再压入其它数据，由此可见，栈顶元素即下标top-1的位置。

Stack.h 文件：

//访问栈顶数据
STDataType StackTop(ST* ps);

Stack.c 文件：

//访问栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}

获取栈中有效元素个数

思想：

上文讲到下标top-1才是栈顶元素，那么是不是说总共就是top-1个元素呢？当然不是，这里跟数组下标一样的思想，元素个数应该就是top个，直接返回即可。

Stack.h 文件：

//有效元素个数
int StackSize(ST* ps);

Stack.c 文件：

//有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

检测栈是否为空

思路：

当top的值为0时即为空，return直接返回即可

Stack.h 文件：

//判空
bool StackEmpty(ST* ps);

Stack.c 文件：

//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top为0，那么就为真，即返回
}

Test.c 文件：

void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	StackDestory(&st);
}

效果如下：

总代码

Stack.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //存储数据
	int top; //栈顶的位置
	int capacity; //容量
}ST;
 
//初始化栈
void StackInit(ST* ps);
 
//销毁栈
void StackDestory(ST* ps);
 
//压栈
void StackPush(ST* ps, STDataType x);
 
//出栈
void StackPop(ST* ps);
 
//判空
bool StackEmpty(ST* ps);
 
//访问栈顶数据
STDataType StackTop(ST* ps);
 
//有效元素个数
int StackSize(ST* ps);

Stack.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
 
//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
 
//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果栈满了，考虑扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//将数据压进去
	ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
 
//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top为0，那么就为真，即返回
}
 
//访问栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
 
//有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	StackDestory(&st);
}
int main()
{
	TestStack();
	return 0;
}

到此这篇关于C语言超详细讲解栈的实现及代码的文章就介绍到这了,更多相关C语言 栈的实现内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言超详细讲解栈的实现及代码

本文链接: https://www.lsjlt.com/news/145566.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言超详细讲解栈的实现及代码
    目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码Stack.h 文件Stack.c 文件Test.c 文件前言 栈...
    99+
    2022-11-13
  • C语言超详细讲解队列的实现及代码
    目录前言队列的概念队列的结构队列的应用场景队列的实现创建队列结构队列初始化  队列销毁  入队列  出队列  队列判空  获取队列元...
    99+
    2022-11-13
  • C语言超详细讲解栈与队列实现实例
    目录1.思考-12.栈基本操作的实现2.1 初始化栈2.2 入栈2.3 出栈2.4 获取栈顶数据2.5 获取栈中有效元素个数2.6 判断栈是否为空2.7 销毁栈3.测试3.1 测试3...
    99+
    2022-11-13
  • C语言超详细讲解函数栈帧的创建和销毁
    目录1、本节目标2、相关寄存器3、相关汇编指令4、什么是函数栈帧5、什么是调用堆栈6、函数栈帧的创建和销毁(1)、main函数栈帧的创建与初始化(2)、main函数的核心代码(3)、...
    99+
    2022-11-13
  • C语言超详细讲解猜数字游戏的实现
    目录rand函数srand函数时间戳完整代码与程序运行图rand函数 先看一下下面这张图： 通过这张图我们可以了解到rand函数的返回值是int类型，形参为空，它的头文件<s...
    99+
    2022-11-13
  • C语言超详细讲解指针的使用
    目录指针概述自身类型指向类型代码例子数值型指针字符型指针单字符字符数组字符串型指针字符数组总结指针概述 C语言中指针也可以认为是一种类型，不同于数值型和字符型的类型。推演过去指针变量...
    99+
    2022-11-13
  • C语言超详细讲解文件的操作
    目录一、为什么使用文件二、什么是文件1.程序文件2.数据文件3.文件名三、文件指针四、文件的打开和关闭五、文件的顺序读写六、文件的随机读写fseekftellrewind七、文件结束...
    99+
    2022-11-13
  • C语言超详细讲解getchar函数的使用
    目录一、getchar 函数二、缓冲区1、什么是缓冲区2、为什么要存在缓冲区3、缓冲区的类型4、缓冲区的刷新三、getchar 函数的正确使用1、getchar 的换行问题2、get...
    99+
    2022-11-13
  • C语言折半查找法的超详细讲解
    折半查找法仅适用于对已有顺序的数组、数据进行操作！！！（从小到大）自我总结：折半查找法就是相当于（通过改变low或high的大小）把中间位置指到了key那个数那里，所以mid应该处于...
    99+
    2022-11-13
  • C语言数据的存储超详细讲解上篇
    目录前言1、数据类型介绍类型的基本归类2、整形在内存中的存储2.1 原码、反码、补码2.2 大小端介绍2.2.1 什么是大小端2.2.2 大端和小端意义2.2.3 写程序判断字节序总...
    99+
    2022-11-13
  • C语言超详细讲解宏与指针的使用
    目录1、关于define2、初识指针（1）内存（2）示例（3）指针的使用示例（4）指针变量的大小1、关于define define是一个预处理指令，有两种用法，一种是用define定...
    99+
    2022-11-13
  • C语言超详细讲解函数指针的运用
    目录前言计算器的例子回调函数转移表前言 前面我们学习了各种各样的指针类型，有些指针可以说是稀奇百怪，特别是函数指针，有些朋友可能觉得，函数指针有些多余，调用函数为什么要用指针调用，直...
    99+
    2022-11-13
  • C语言超详细讲解指向函数的指针
    目录一、函数的指针二、指向函数的指针变量三、调用函数的两种方式四、指向函数的指针的作用五、用指向函数的指针作函数参数(重点)六、为什么要将指向函数的指针变量作为函数的形参(重点)一、...
    99+
    2022-11-13
  • C语言超详细讲解顺序表的各种操作
    目录顺序表是什么顺序表的结构体顺序表的接口函数顺序表相关操作的菜单顺序表的初始化添加元素陈列元素往最后加元素往前面加元素任意位置加元素删除最后元素删除前面元素 删除任意元素...
    99+
    2022-11-13
  • C语言超详细讲解指针的概念与使用
    目录一、指针与一维数组1. 指针与数组基础2. 指针与数组3. 一个思考二、指针与字符串三、指针和二维数组1. 指针数组与数组指针2. 指针数组3. 数组指针一、指针与一维数组 1....
    99+
    2022-11-13
  • C++ 栈和队列的实现超详细解析
    目录1、栈的介绍：2、栈的常用接口实现 3、队列的介绍4、队列的常用接口实现 可算是把链表给结束了，很多小伙伴已经迫不及待想看到栈和队列了，那么它来了！相信有了顺...
    99+
    2022-11-13
  • C++超详细讲解单链表的实现
    目录单链表的实现(从入门到熟练)概念和结构链表的实现增删查改接口节点结构体创建节点开辟数据打印链表尾插数据头删链表数据查找链表pos位置前插数据链表pos位置后插数据链表pos位置数...
    99+
    2022-11-13
  • C语言实现栈的示例代码
    目录一、了解栈的结构特点二、具体实现补充 栈的用处一、了解栈的结构特点 栈是一种特殊的线性表，只允许从一端进出数据，称为后进先出，先进后出。 压栈：栈的插入操作叫做进栈/压...
    99+
    2022-11-13
  • C语言实现通讯录的详细代码
    目录（一）实现思路1.通讯录功能2.模块化实现各方面的功能3.代码实现（二）源代码A.test.cB.Contact.hC.Contact.c（一）实现思路 1.通讯录功能 添加好友...
    99+
    2022-11-12
  • C语言详细讲解strcpystrcatstrcmp函数的模拟实现
    目录一、模拟实现strcpy函数二、模拟实现strcat函数三、模拟实现strcmp函数四、小结一、模拟实现strcpy函数 strcpy函数是字符串拷贝函数,就是将源字符串拷贝到目...
    99+
    2022-11-13
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作