前言:
还是举一个生活中的例子,大家都玩过积木,当我们把积木叠起来的时候,如果要拿到最底部的积木,我们必须从顶端一个一个打出,最后才能拿到底部的积木,也就是后进先出(先进后出)的道理,今天分享栈的实现的本质也就是后进先出(先进后出)。
目录
前言:
栈的概念及结构
栈的实现
栈的结构定义
初始化栈
压栈(数据的添加)
出栈(数据的删除)
获取栈顶元素
获取栈中有效元素个数
判断栈是否为空
栈实现的总代码(vs2022)
头文件Stack.h
函数文件Stack.c
测试Text.c
栈的概念及结构
要去实现栈,我们要知道什么是 栈,栈的结构是什么,该从什么方向去实现。
如图我们会发现数据进栈出栈后的顺序倒置了,其实栈不只是可以将顺序导致,我们也可以先把A,B放进去,拿出来之后,再将C,D放进去,全部拿出来可以得到C,D,A,B,所以栈最后导致的结果是多种多样的,这取决你如何运用栈了。
栈的实现
栈的结构定义
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //栈顶
int capacity;//栈容量
}Stack;
栈只需要对栈顶进行操作,所以我们有一个变量top表示栈顶。后面需要判断栈是否为空,我们需要一个变量capacity表示栈容量。
初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
ps->top = 0;
ps->capacity = 4;
}
这里我们创造了4个整型变量的空间,所以capacity给4。
压栈(数据的添加)
void StackPush(Stack* ps,STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//考虑到空间大小不够,使用realloc进行增容操作
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)//要注意tmp可能为空的情况。
{
printf("realloc fail!!!");
exit(-1);
}
ps->a = tmp;//别忘了把指针a指向新开辟的空间
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;//注意个数的增加
}
在压栈的时候要注意几点:
1.压栈时要考虑空间的大小是否足够,不够时要进行增容操作。
2.增容操作后的原指针要指向新指针,保证数据不会丢失。
3.压栈过后要对将top往后移动一位,因为top的指向是数组最后元素的下一个位置。
出栈(数据的删除)
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//top不能小于或等于0,因为top是指向栈顶元素的下一个位置
ps->top--;
}
因为是用数组进行栈的实现,我们只需要把栈顶往前移动一位,就表示删除了数据。
获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];//因为top是指向栈顶元素的下一个位置,所以要-1
}
一定注意对ps->top>0进行断言,保证栈的元素不为空。
获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
top指向的数组尾部元素后一位,刚好是数组中有效元素的个数。
判断栈是否为空
bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{
assert(ps);
return ps->top == 0;
}
检查栈是否为空,如果不为空则返回0,如果为空则返回非零结果。
栈实现的总代码(vs2022)
头文件Stack.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //栈顶
int capacity;//栈容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//栈的销毁
void StackDestory(Stack* ps);
//压栈
void StackPush(Stack* ps,STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检查栈是否为空,如果不为空则返回0,如果为空则返回非零结果
bool StackEmpty(Stack* ps);//bool也可以使用 表示真假
函数文件Stack.c
#include"Stack.h"
void StackInit(Stack* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
ps->top = 0;
ps->capacity = 4;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps,STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//考虑到空间大小不够,使用realloc进行增容操作
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)//要注意tmp可能为空的情况。
{
printf("realloc fail!!!");
exit(-1);
}
ps->a = tmp;//别忘了把指针a指向新开辟的空间
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;//注意个数的增加
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//top不能小于或等于0,因为top是指向栈顶元素的下一个位置
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];//因为top是指向栈顶元素的下一个位置,所以要-1
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{
assert(ps);
return ps->top == 0;
}
测试Text.c
#include"Stack.h"
void StackText()
{
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestory(&st);
}
int main()
{
StackText();
return 0;
}
好啦,这就是今天学习的分享啦!看到希望大家的三连呀!
如果有不当之处,欢迎大佬指正!