首页 > 其他分享 >数据结构——栈(C语言版)

数据结构——栈(C语言版)

时间:2024-03-27 17:58:54浏览次数:26  
标签:C语言 top 元素 ST STDataType 数据结构 void pst

前言:

在学习完数据结构顺序表和链表之后,其实我们就可以做很多事情了,后面的栈和队列,其实就是对前面的顺序表和链表的灵活运用,今天我们就来学习一下栈的原理和应用。

准备工作:本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现,其中test.c用来放主函数,SeqList.c用来放调用的函数,SeqList.h用来放头文件和函数声明

目录

什么是队列?

栈的节点结构

栈的基本操作

1、初始化

2、销毁

3、插入元素

4、判断栈顶元素是否为空

5、删除元素

6、返回栈顶元素

7、栈中元素个数

完整的栈实例

总结


什么是队列?

队列中的数据是按照先进后出的顺序的,也就是说先进去的数字后出来

因为栈的这种性质,所以栈我们用顺序表来实现比链表方便很多,顺序表就可以实现尾插尾出,所以我们一般就采用顺序表来实现

栈的节点结构

队列采用的顺序表的结构,所以与顺序表差异不大

typedef int STDataType;
typedef struct stack
{
	STDataType* a;
	int top;         //指向栈元素下一位
	int capacity;
}ST;

栈的结构很简单,定义一个整形指针,一个表示容量和一个表示尾部元素的整形变量即可

栈的基本操作

//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//插入元素
void STPush(ST* pst, STDataType x);
//删除元素
void STPop(ST* pst);
//判断栈顶元素是否为空
bool STEmpty(ST* pst);
//找栈顶元素
STDataType STTop(ST* pst);
//栈中元素个数
STDataType STSize(ST* pst);

看上面的函数声明部分我们就可以看到我们每一步要实现的内容,接下来,我们就来一步一步进行实现

1、初始化

//初始化
void STInit(ST* pst)
{
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}

2、销毁

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

3、插入元素

插入元素时要先检查空间是否够用,如果不够用要先进行扩容

//插入元素
void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* newnode = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("STPush");
			return;
		}
		pst->a = newnode;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

4、判断栈顶元素是否为空

这一步在下面有用到,例如当删除栈顶元素时,如果栈顶元素为空就无法操作,所以需要判断栈顶元素是否为空

//判断栈顶元素是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

5、删除元素

这里删除元素是删除栈顶元素,因为栈的特性是即出即删

//删除元素
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}

6、返回栈顶元素

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

7、栈中元素个数

//栈中元素个数
STDataType STSize(ST* pst)
{
	assert(pst);
	return pst->capacity;
}

完整的栈实例

SeqList.h

//实现栈
typedef int STDataType;
typedef struct stack
{
	STDataType* a;
	int top;         //指向栈元素下一位
	int capacity;
}ST;

//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//插入元素
void STPush(ST* pst, STDataType x);
//删除元素
void STPop(ST* pst);
//判断栈顶元素是否为空
bool STEmpty(ST* pst);
//找栈顶元素
STDataType STTop(ST* pst);
//栈中元素个数
STDataType STSize(ST* pst);

test.c

//实现栈
void test()
{
	ST st;
	STInit(&st);
	STPush(&st,1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	STDestroy(&st);
}
int main()
{
	test();
	return 0;
}

SeqList.c

//实现栈
//初始化
void STInit(ST* pst)
{
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}
//销毁
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
}
//插入元素
void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* newnode = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("STPush");
			return;
		}
		pst->a = newnode;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
//判断栈顶元素是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//删除元素
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
//找栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
//栈中元素个数
STDataType STSize(ST* pst)
{
	assert(pst);
	return pst->capacity;
}

总结

总之,其实栈就是对顺序表的应用,熟练栈和队列,对我们巩固顺序表和链表帮助很大,当然,栈在一些场景下很实用,后面我会出一个专门的习题讲解篇章,讲数据结构的一些经典题型,感兴趣的可以点赞关注一下

创作不易,还请各位大佬点赞支持一下!!!

标签:C语言,top,元素,ST,STDataType,数据结构,void,pst
From: https://blog.csdn.net/2301_80220607/article/details/137076389

相关文章

  • Java开发千万别错过的好课程:Java版数据结构和算法+AI算法课程13
    AI人工智能时代,Java从业者必学科目精品课程推荐:Java版数据结构和算法+AI算法课程【点击开始学习】工作机会推荐和资源分享群:819391432学习地址:https://class.imooc.com/sale/fullstackalgo在当今数字时代,数据已成为驱动创新和决策的关键资源。为了在这个竞争激烈的世界......
  • pat mooc 浙江大学数据结构 01-复杂度1 最大子列和问题
    输入格式:输入第1行给出正整数K(≤100000);第2行给出K个整数,其间以空格分隔。输出格式:在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。输入样例:6-211-413-5-2输出样例:20#include<stdio.h>intmain(){ intk,n; intsum=0; intm......
  • C语言 预处理详解
    目录前言一、预定义符号二、#define定义常量三、#define定义宏四、带有副作用的宏参数五、宏替换的规则六、宏与函数的对比七、#和##7.1#运算符7.2##运算符八、命名约定九、#undef十、命令行定义十一、条件编译十二、头文件的包含12.1头文件被包含的方式:12......
  • 网上的一个用C语言实现FFT算法
     用C语言实现FFT算法/*****************fftprograme*********************/#include"typedef.h"#include"math.h"structcompxEE(structcompxb1,structcompxb2){structcompxb3;b3.real=b1.real*b2.real-b1.imag*b2.imag;b3.imag=b1.real*b2.imag+b1.imag*b2.real;......
  • 宏定义(C语言)
    1、宏定义一个两数相乘#defineMUL(a,b)a*b代码如下:#include<stdio.h>#defineMUL(a,b)a*bintmain(){intvalue;printf("value=%d\n",MUL(2,4));return0;}2、在虚拟机中运行,利用如下命令进行屏蔽屏蔽头文件,就可以完成宏替换。gcc-Edemo.c-o......
  • 0基础 三个月掌握C语言(15)
    动态内存管理为什么要有动态内存分配我们已经掌握的内存开辟⽅式有:intval=20; //在栈空间上开辟四个字节chararr[10]={0};//在栈空间上开辟10个字节的连续空间但上述的开辟空间的⽅式有两个特点:•空间开辟⼤⼩是固定的。•数组在申明的时候,必须指定数组的......
  • C语言-实现文件操作
    0.前言:    我们知道下载东西,电脑上就会有各种的文件夹及文件里面的内容,那么文件里面的数据怎么通过编写程序来帮我们获取呢,这些文件又是怎么创建的呢?C语言给我们提供了一些可以操作文件的函数。这里我只列举了一部分操作文件的函数,使用这些函数需要引入头文件<stdlib.......
  • 数据结构-二叉搜索树(Java实现)
    1.概念二叉搜索树也叫做二叉排序树,如果中序遍历,这棵二叉搜索树的结果就是有序的,它是具备以下性质的二叉树:若它的左子树不为空,则左子树上所有结点的值都小于根节点的值若它的右子树不为空,则右子树上所有结点的值都大于根节点的值它的左右子树也分别为二叉搜索树{5,3,......
  • 数据结构-排序算法(Java实现)
    1.插入排序1.1基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。1.2图解 1.3原理解析第一趟:一组数据可以分为有序序列和无序序列, i表示无序序列的第一个元素,j表示有序序列的......
  • C语言实现游戏——三子棋
    三子棋是一种民间传统游戏,又叫九宫棋、井字棋等。游戏分为双方对战,双方依次在9宫格棋盘上摆放棋子,率先将自己的三个棋子走成一条线就视为胜利,而对方就算输了,但是三子棋在很多时候会出现和棋的局面。今天我们就来用C语言来实现一下这个游戏游戏分解:本文采用分文件编写的模式,实......