您现在的位置是:首页 > Javascript
当前栏目
【数据结构】————栈
2023-04-18 16:29:32 时间
前言
本文主要讲述特殊的线性表——栈:
栈是什么,栈的特点
数据结构中有一种特殊的线性表叫栈。
栈有一种特点:
它允许后进入的数据先拿出来。
类似一个弹夹,或是一个装砖头的容器。
栈的基本操作有如上图:
类比一个缸,缸的底端是栈底,顶端是栈顶,放入数据称为入栈,取出数据称为出栈。
对于一个栈,其特点为后进先出
Last In Fist Out
或者
先进后出
Fist Out Last In
所以在实现栈这种特殊的线性表时,当我们拿出数据的时候,只需要取栈顶元素即可,存入数据时,只需往栈顶存放数据。
综合栈的特点,在实现其结构时更适合使用数组 ,而不是链表。
当然使用链表也是可行的,相比而言:
使用链表的缺点有:
1.在压栈时总需要next的指针来维护。
2。出栈时需要记录上一个节点的位置,效率较低。
数组的方式可以解决上述两个问题,且无其他较为严重的缺点。
下面来实现栈的基本功能:
实现栈的基本操作
栈的相关操作声明
void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);
void CheckCapacity(ST** ps);//检查容量
void StackPush(ST* ps,STDataType x);//插入元素
void StackPop(ST* ps);//删除栈顶元素
int StackSize(ST* ps);//计算栈有多少个数据
bool StackEmpty(ST* ps);//判断栈是否为空
STDataType StackTop(ST* ps);//取栈顶元素
注:ps是指向一个结构体的指针,在main函数创建了一个结构体:
ST st;
并且传参传的是结构体的地址
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;
解读: 定义一个结构体:使用结构体的指针来维护数组栈
top表示栈顶的元素
capacity表示栈的容量大小
2.对栈进行初始化
void StackInit(ST* ps)//初始化
{
assert(ps!=NULL);
ps->a = NULL;
ps->top = ps->capacity = 0;
//ps->top可以初始化成-1,此时先++,再赋值
//此时指向的就是栈顶元素
}
3.销毁栈
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
4.判断栈是否为空
bool StackEmpty(ST* ps)//判断栈是否为空
{
assert(ps);
return ps->top == 0;
}
5.压栈操作
void CheckCapacity(ST**ps)//检查容量
{
assert(ps != NULL);
if ((*ps)->top == (*ps)->capacity)
{
STDataType newcapacity = (*ps)->capacity == 0 ? 4 : (*ps)->capacity * 2;
STDataType* tmp = (STDataType*)realloc((*ps)->a,(sizeof(STDataType)*newcapacity));//申请的空间是存放STDataType的
//不是用来存放结构体的
//如果第一个参数是一个NULL,realloc的作用就跟malloc一样,所以可以传NULL
assert(tmp != NULL);
(*ps)->a = tmp;// 把新地址给ps->a
(*ps)->capacity = newcapacity;
}
}
void StackPush(ST* ps, STDataType x)//插入元素
{
assert(ps);
CheckCapacity(&ps);//这里如果传参传的是ps,相当于传值调用,在CheckCapacity函数内部申请的空间就无法返回来了。
ps->a[ps->top] = x; // 先赋值,再++,因为ps->top初始化是0,就是指向栈顶元素的下一个。
ps->top++;
}
解读:入栈时首先需要检查栈空间的容量大小,如果栈空间不足则需增容。
在这里分装了一个检查容量的函数。
6.删除栈顶元素
void StackPop(ST* ps)//删除栈顶数据
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
7.取出栈顶元素
注:第六个函数仅仅删除栈顶元素并未拿到该数据
这里分装函数是更方便的
STDataType StackTop(ST* ps)//取栈顶元素
{
assert(ps);
assert(!StackEmpty(ps)); //感叹号表达式让语句的逻辑相反
return ps->a[ps->top - 1];
//在这里我初始化top为0,表示指向栈顶元素的下一个位置
//因为初始化为0时,需要先压栈,top值再++,此时就指向了下一个位置了
}
8.计算栈内存放多少个数据
int StackSize(ST* ps)//计算栈有多少个数据
{
assert(ps);
assert(!StackEmpty(ps));
return ps->top;
}
解读:
这里直接返回top,而不是返回top-1
因为我们在初始化的时候是将top置为0,先入栈,top再++
假如入栈三次,那么top此时就是3,但是top指向的位置是入栈的第三个元素的下一个位置。
函数基本功能如下:
总结
掌握了链表的结构之后,实现栈难度是不大的。
相关文章
- 总结vue的13种传值方法
- Vue 介绍
- 每天用SpringBoot,还不懂RESTful API返回统一数据格式是怎么实现的?
- 微服务架构一直火,为什么服务化要搞懂?
- html的input type=file
- Vue——initLifecycle【五】
- Kali Linux 下搭建Web环境
- 对一款不到2KB大小的JavaScript后门的深入分析
- 为什么 SpringBoot 零配置,开箱即用?
- kali下Apache搭建虚拟主机
- 1 前端路径问题
- CSS四种导入方式
- Resolved [org.springframework.web.HttpRequestMethodNotSupportedException: Request method 'GET' not supported]
- React-Router V6 使用详解
- CVE-2018-6389: WordPress <= 4.9.x 拒绝服务(DOS)漏洞
- vue知识点
- 基于Web的图书管理系统设计与实现(附源码下载地址)
- Vue3响应式provide、inject传值
- 文件上传(一)基于前端js的破解
- 网站地图有什么用