【数据结构】--- 几分钟走进栈和队列(详解-上)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】--- 几分钟走进栈和队列(详解-上)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

👧个人主页：@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：数据结构
🔑本章内容：[数据结构]—栈和队列
送给各位💌：一事无成也代表万事皆有可能
欢迎评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

🌟一、栈

🌏1.1栈的概念及结构：

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

🌏1.2实现栈的两种方式：

数组栈

链式栈

对于链式栈是不建议第一种写法的因为尾删需要找到前一个结点(单链表)

🌟二、栈实现(数组栈)

🌏2.1结构：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Strack
{
	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);
//获取元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取size
int STSize(ST* pst);

🌏2.2初始化：

对于初始化有两种写法，可不要小看这两种，对后面的代码每种都有每种的情况所以要分情况写。

💫2.2.1第一种代码：

void STInit(ST* pst)
{
	assert(pst);//判空不然为空就需要传二级指针或者返回值
	pst->a = NULL;
	pst->top = -1;
	pst->capacity = 0;
}

💫2.2.2流程图：

💫2.2.3第二种代码：

void STInit(ST* pst)
{
	assert(pst);//判空不然为空就需要传二级指针或者返回值
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

💫2.2.4流程图：

总结：两种的区别就在于top指向哪到底是栈顶元素还是栈顶后一个元素，我们选择第二种写法

🌏2.3：释放内存

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

🌏2.4：入栈

void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->a [pst->top ] = x;
	pst->top++;
}

对于初始化第一种扩容要判断pst->top+1 == pst->capacity

🌏2.5：出栈

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;//这里要注意top不能为空
}

🌏2.6：访问栈顶元素

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];//当top为空时-1就越界了所以要判空
}

对于初始化第一种写法，返回return pst->a[pst->top ];

🌏2.7：判空

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

🌏2.8：获取元素个数

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

对于初始化第一种获取元素个数要返回return pst->top+1;

🌟二、栈实现完整代码

//Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Strack
{
	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);
//访问栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取size
int STSize(ST* pst);
//Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* pst)
{
	assert(pst);//判空不然为空就需要传二级指针或者返回值
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	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* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->a [pst->top ] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;//这里要注意top不能为空
}

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top-1 ];
}

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void  TestStack()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPop(&st);
	STPush(&st, 3);
	STPush(&st, 4);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	STDestroy(&st);
}
int main()
{
	TestStack();
	return 0;
}