C语言实现栈--数据结构-Toy模板网

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

C语言实现栈--数据结构

魔王的介绍：😶‍🌫️一名双非本科大一小白。

魔王的目标：🤯努力赶上周围卷王的脚步。

魔王的主页：🔥🔥🔥大魔王.🔥🔥🔥

❤️‍🔥大魔王与你分享：“断剑重铸的锐雯败于菲奥娜，原来破镜重圆的爱到处都是破绽”。

一、前言

1、介绍

栈是一种特殊的线性表，其只允许在固定的一端插入和删除元素，进行插入和删除的一端称为栈顶，另一端称为栈底，栈中的数据元素遵循后进先出（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

C语言实现栈--数据结构

2、说明

栈的实现可以采用顺序表或链表，顺序表就是按顺序存进去（尾插），然后出的时候需要从后往前出。链表的话我们一边采用头插，因为如果是尾插的话，还要有前一个的地址，比头插麻烦一点，所以链表实现一般采用头插。
相对来说数组（顺序表）实现更优一些，因为数组在尾上插入数据代价更小。
如果顺序表和链表你已经掌握，那么相信栈和队列对你来说都是很简单的，因为它们只是对顺序表和链表进行特殊处理而已。

本篇将通过顺序表实现栈。

二、栈的实现

1、创建结构体

我们需要创建一个结构体来存放数组指针和该数组的元素个数及数组的容量。

代码：

typedef int STDateType;

typedef struct Stack
{
	STDateType* a;
	int top;//如果初始化为0，可以理解为元素个数（也就是栈顶元素下标+1），如果初始化为-1，可以理解为栈顶元素的下标
	int capacity;
}ST;

2、初始化和销毁

初始化：
就像顺序表一样，我们需要首先开辟一个初始空间，然后不够的时候在扩容。
销毁：
因为空间是malloc在堆区申请出来的，所以需要我们进行手动释放，防止内存泄露。

代码：

//初始化和最后销毁
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDateType*)malloc(sizeof(ST) * 5);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = 5;
}
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->a = NULL;
	1.没有让top也就是栈顶位置重置。
	ps->top = 0;
	//最后在Test.c上让结构体指针指向空。
}

3、入栈

入栈只能从栈顶入。

//入栈
void STPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity) //判断是否满了
	{
		STDateType* temp = (STDateType*)realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
		else
		{
			ps->a = temp;
			ps->capacity *= 2;
			temp = NULL;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

4、出栈

直接减1就行。

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

5、元素个数

就等于我们结构体里记录数据个数的值。

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

6、判断是否为空

为什么这些简单的操作也要封装成函数呢？
因为编写函数的肯定是一个人，但是使用函数的人并不知道创建的具体是什么，比如结构体里的那个记录元素个数的，可能另一个人编写的时候该变量是记录栈顶下标的，那么就会总是比总个数小1，所以使用者并不能判断到底是哪个，所以需要编写函数的人把每个单独的功能都尽可能封装成函数，当使用者使用时，不需要区分那么多，直接调用对应函数，就能得到想要的结果。

代码：

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

7、栈顶元素

同上一个的描述，因为不知道记录的是栈顶元素的下标还是元素的总个数，所以为了方便且避免出错，需要封装成函数让使用者使用。

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

三、总代码

Stack.h

`Stack.h

  #pragma once

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

typedef int STDateType;

typedef struct Stack
{
	STDateType* a;
	int top;//如果初始化为0，可以理解为元素个数（也就是栈顶元素下标+1），如果初始化为-1，可以理解为栈顶元素的下标
	int capacity;
}ST;

//初始化和最后销毁
void STInit(ST* ps);
void STDestory(ST* ps);

//入栈
void STPush(ST* ps, STDateType x);

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

//元素个数
int STSize(ST* ps);

//判断是否为空
bool STEmpty(ST* ps);

//栈顶元素
STDateType STTop(ST* ps);

Stack.c

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

//初始化和最后销毁
void STInit(ST* ps)
{
	assert(ps);
	//ps->a = malloc(sizeof(ST) * 5);  1.没有强转
	ps->a = (STDateType*)malloc(sizeof(ST) * 5);
	2.开辟新空间后没有检查
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = 5;
}
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->a = NULL;
	1.没有让top也就是栈顶位置重置。
	ps->top = 0;
	//最后在Test.c上让结构体指针指向空。
}

//入栈
void STPush(ST* ps, STDateType x)
{
	assert(ps);
	//if (ps->top == ps->capacity)
	//{
	//	ST* str = realloc(ps->a, ps->capacity * sizeof(ST) * 2);
	//	if (str == NULL)
	//	{
	//		perror("realloc fail");
	//		return;
	//	}
	//}  
	1.没有把扩容的时候创建的新指针赋给原指针
	if (ps->top == ps->capacity) //判断是否满了
	{
		//ST* temp = realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		//2.指针应该指向数据的类型的地址，而且realloc也没强转为数据类型的指针
		STDateType* temp = (STDateType*)realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
		else
		{
			ps->a = temp;
			3.忘记让结构体内的容量*2
			ps->capacity *= 2;
			temp = NULL;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

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

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

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

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

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

int main()
{
	ST ps;
	STInit(&ps);
	STPush(&ps, 0);
	STPush(&ps, 1);
	STPush(&ps, 2);
	STPush(&ps, 3);
	STPush(&ps, 4);

	//打印，因为只能从栈顶出，所以每打印一个数据就需要弹出这个数据(出栈)。

	while (!STEmpty(&ps))
	{
		printf("%d ", STTop(&ps));
		STPop(&ps);//打印和出栈是一对，因为想要打印下一个，那么栈顶的元素必须出栈
	}
	STDestory(&ps);
	ps.a = NULL;
	return 0;
}