C语言实现栈及栈的详解
前言以及成型代码：
一、栈的概念
二、栈的实现
三、代码实现以及详细解释
1. 初步介绍
2. 定义结构体，以及栈内数据类型
3. 初始化栈 void STInit(ST* pst);
4. 销毁栈 void STDestroy(ST* pst);
5.添加数据 void STPush(ST* pst, STDataType x);
6.删除数据 void STPop(ST* pst)；
7. 弹出数据 STDataType STTop(ST* pst);
8. 判断是否为空 bool STEmpty(ST* pst);
9. 判断大小 int STSize(ST* pst);
前言以及成型代码：学习完数据表和链表以后我们来学习一个新的数据结构：栈 。 还是老套路先把成型代码给各位看关老爷呈上方便有一个初步了解。更重要的是可以方便CV工程师的工作
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.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);
// 弹出数据
STDataType STTop(ST* pst);
// 判断是否为空
bool STEmpty(ST* pst);
// 判断大小
int STSize(ST* pst);
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->top = 0;
pst->capacity = 0;
}
// 添加数据
void STPush(ST* pst, STDataType x)
{
if (pst->capacity == pst->top)
{
int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2);
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
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--;
}
// 弹出数据
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;
}
一、栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
定义结构体，以及栈内数据类型初始化栈 void STInit(ST* pst);2. 定义结构体，以及栈内数据类型销毁栈 void STDestroy(ST* pst);
添加数据 void STPush(ST* pst, STDataType x);
删除数据 void STPop(ST* pst)；
弹出数据 STDataType STTop(ST* pst);
判断是否为空 bool STEmpty(ST* pst);
判断大小 int STSize(ST* pst);
代码：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType; //定义栈内数据类型，方便后面修改
typedef struct Stack //创建栈的基本结构
{
STDataType* a;
int top;
int capacity;
}ST;
这几行代码是栈的地基，也是这个结构中最简单的代码了。
3. 初始化栈 void STInit(ST* pst);代码：
// 初始化栈
void STInit(ST* pst)
{
assert(pst); //判断是否为空指针
pst->a = NULL; //栈为空的，所以先初始化为空指针
pst->top = 0;
pst->capacity = 0;
}
初始化栈，顾名思义就是把栈的结构上面添加一些初始值。让前面的地基有框架。
4. 销毁栈 void STDestroy(ST* pst);代码：
// 销毁栈
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a); //释放指针
pst->a = NULL; //置空指针a
pst->top = 0; //把栈顶的位置降低，释放数据
pst->capacity = 0;//把栈的大小置为0
}
创建以后肯定是要销毁的，要不然就会造成内存泄漏。
5.添加数据 void STPush(ST* pst, STDataType x);代码：
// 添加数据
void STPush(ST* pst, STDataType x)
{
if (pst->capacity == pst->top) //判断是否要扩容
{
int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2); //扩容步骤，当为空栈时扩基础的大小，不为空则扩成原来的二倍
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));//使用realloc扩出来一定的空间
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp; //初始化这一块空间
pst->capacity = newcapacity;
}
pst->a[pst->top] = x; //把x的直插入到栈的顶部
pst->top++;
}
添加数据也是很重要的一个步骤，这一步直接决定了这个栈的成功与否。添加的时候要首先判断后面的空间是否足够，够的话直接加上去，不够的话就扩容。
6.删除数据 void STPop(ST* pst)；// 删除数据
void STPop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst))); //判断是否为空
pst->top--;
}
删除数据的时候要借助后面的判空函数，为空就不能再删除了
7. 弹出数据 STDataType STTop(ST* pst);代码：
// 弹出数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst)));
return pst->a[pst->top - 1];
}
弹出数据就是：调用完这个函数以后可以返回栈顶的值
8. 判断是否为空 bool STEmpty(ST* pst);// 判断是否为空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;//判空
}
判空就是看里面还有数据没有了，有的话返回false 没有数据也就是空值的状态就返回true
9. 判断大小 int STSize(ST* pst);代码：
// 判断大小
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
直接返回栈顶就可以了
到此这篇关于C语言实现栈及栈的详解的文章就介绍到这了,更多相关C语言实现栈内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！
