当前栏目
用动图详细讲解——栈
栈
栈的概念:
栈:
一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作,是操作受到限制的线性表,遵行后进先出LIFO(Last In First Out)的原则。
简单理解就是一个一端封口,另一端没有封口的管子,你往里面放直径与管子的直径相同的球,不管你放多少球,你先取的一定是最后放的球,最里面的球要把前面的球全部取出来才能取到。这个管子里的空间就相当于栈的空间,球就相当于你所要放入栈的数据
栈顶和栈底
进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,非空栈中的栈顶指针始终在栈顶元素的下一个位置上,空栈时,栈顶指针和栈底指针指向同一块位置。
借助管子和球的例子,简单理解就是管子封口那里就是栈底,管子中最外层的球的下一个可以存放球的空间,但还没有存放球的位置就是栈顶,不能直接理解为管口就是栈顶。
当管子中没有球时(空栈),栈顶和栈底所指向的位置相等,都指向管子最里面所能存放一个球的空间
压栈和出栈
栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶,栈的删除操作叫做出栈。出数据也在栈顶。
入栈gif动画
出栈gif动画
栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾部插入数据的代价比较小,可以根据下标直接锁定尾部。
用链表(无头单向非循环链表)在尾部插入数据的代价比较大,需要先遍历一遍才能找到尾部,但也不是不可以,不过尽量用数组比较好一些。
对于栈的实现,有这几个功能,
- 初始化栈
- 检测栈的容量是否充足(不充足进行扩容)
- 入栈
- 出栈
- 获取栈顶元素
- 获取栈中有效元素个数
- 检测栈是否为空(为空返回非0结果,不为空返回0)
- 销毁栈
我们将用函数对这些功能进行封装
用结构体自定义一个栈的数据类型
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
因为我们不知道存放在栈中的数据的类型,所以将存放数据的类型用typedef
重命名为STDataType
,以方便随时更改。(这里我们存放数据的类型是int
)
Stack
就是我们定义并重命名的栈的数据类型
STDataType* a
指向栈用数组存放数据的地方起始位置,即栈底
top
是栈顶,也是用来访问数组尾部的下标
capacity
是栈的容量,指栈所能容纳多少的数据
初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
将栈的地址传过来,对其成员进行初始化
assert(ps)
对传过来的地址进行空指针的判断,因为传过来的地址不能为空
ps->a = NULL
将指针为空,表明栈的容量为0
ps->top = ps->capacity = 0
top记录栈顶位置,capacity记录栈的容量,当容量不足时(也就是ps->top == ps->capacity)进行扩容
检测栈的容量是否充足(不充足进行扩容)
void CheckCapacity(Stack* ps)
{
assert(ps);//传过来的指针不能为空
if (ps->top == ps->capacity)//相等表明容量不足
{
//创建一个新的变量,表示新的容量
int newcapacity = ps->capacity;
//对容量的不足类型判断:
//第一种是未扩容过的空栈,则扩容为4个空间;
//第二种是扩容过,但是容量不足,则扩容为原来容量的二倍
newcapacity = ps->capacity == 0 ? 4 : newcapacity * 2;
//使用realloc函数对ps->a扩容为sizeof(STDataType) * newcapacity个字节的空间,并把扩容后空间的起始地址保存在tmp
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)//判断是否扩容成功,不成功则停止运行并报错
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->a
ps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中
}
}
未扩容过的空栈
扩容过的栈
注:栈空间起始位置的下标为0
入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
CheckCapacity(ps);//检查容量,容量不足则扩容
ps->a[ps->top] = data;
ps->top++;
}
动画演示举例,对5个数据进行入栈,且此时的栈为空栈:
检测栈是否为空(为空返回非0结果,不为空返回0)
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//栈顶指向下标0,则栈为空,返回非零,若不指向下标0,则栈不为空,返回假
}
出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断栈是否为空,为空则不能出栈
ps->top--;
}
将栈顶top-1
即可出栈,类似这个动画,但仅仅是出栈,未对出栈的数据进行存储
获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断栈是否为空,为空则不能获取到元素
ps->top--;//获得栈顶元素的下标
return ps->a[ps->top];//返回栈顶的元素
}
这一步对出栈的数据进行了返回,可以进行存储出栈返回的数据
获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
把栈顶top的存储的下标返回,可获得栈中元素的个数
销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);//free函数可以将从堆区开辟的空间释放,但不能反复释放,所以需要释放后置为空指针,防止再次释放
ps->a = NULL;//置为NULL,防止重复释放堆区开辟的空间
ps->top = ps->capacity = 0;//空间释放,栈的容量为0
}
C语言实现栈的具体代码
//Stack.h
#pragma once
#include<stdlib.h>
#include<assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
//Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void CheckCapacity(Stack* ps)
{
assert(ps);//传过来的指针不能为空
if (ps->top == ps->capacity)//相等表明容量不足
{
//创建一个新的变量,表示新的容量
int newcapacity = ps->capacity;
//对容量的不足类型判断:
//第一种是未扩容过的空栈,则扩容为4个空间;
//第二种是扩容过,但是容量不足,则扩容为原来容量的二倍
newcapacity = ps->capacity == 0 ? 4 : newcapacity * 2;
//使用realloc函数对ps->a扩容为sizeof(STDataType) * newcapacity个字节的空间,并把扩容后空间的起始地址保存在tmp
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)//判断是否扩容成功,不成功则停止运行并报错
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->a
ps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中
}
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
CheckCapacity(ps);
ps->a[ps->top] = data;
ps->top++;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
return ps->a[ps->top];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
相关文章
- 前端面试 【JavaScript】— typeof 是否能正确判断类型?
- 前端面试 【JavaScript】— instanceof 能否判断基本数据类型?
- 前端面试 【JavaScript】— 能不能手动实现一下 instanceof 的功能?
- 前端面试 【JavaScript】— Object.is和=== 有什么区别?
- 前端面试 【JavaScript】— JS中类型转换有哪几种?
- 前端面试 【JavaScript】— == 和 ===有什么区别?
- 前端面试 【JavaScript】— 对象转原始类型是根据什么流程运行的?
- JavaScript 的 parseInt() 函数
- javascript实现两个数字进行组合
- JS监听键盘按键
- 大前端开发中的路由管理之五:Flutter篇
- Javascript的DOM操作
- 在Vue项目中使用WebSocket技术
- 新手向:前端程序员必学基本技能——调试JS代码
- React 毁了 Web 开发!
- 「JS 逆向百例」cnki 学术翻译 AES 加密分析
- 商标注册域名后缀用什么?商标和域名有哪些区别?
- 网站建设流程是怎样的?需要看重哪些细节?
- 网站域名商标注册流程是什么?网站域名商标有什么用?
- 如何建设一个实用性强的网站 网站上线后如何运营