当前位置: 首页 > news >正文

[全网最细数据结构完整版]第六篇:3分钟带你吃透栈并模拟实现

目录

1->栈的概念和结构

1.1栈的概念

 1.2栈的结构

 2->栈的实现

2.1定义关于栈的结构体和各种函数

2.2栈的初始化 STInit 函数

2.3栈的销毁 STDestroy 函数

2.4栈的插入操作 STPush 函数 

2.5栈的判断是否为空操作 STEmpty 函数 

2.6栈的删除操作 STPop 函数

2.7栈的取栈顶元素操作 STTop 函数

2.8求栈的大小即有效元素的个数 STSize 函数

3->测试下我们自己写的栈

4->您的专属鼓励师


1->栈的概念和结构

1.1栈的概念

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

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶

 1.2栈的结构

 

 2->栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小.

使用数组模拟原理:

 使用链表模拟原理:

 

// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;

2.1定义关于栈的结构体和各种函数

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef struct Stack
{int* _arr;//开辟在堆区上存储数据的数组int _top;//栈顶的下一个位置int _capacity;//栈的容量
}ST;//1.栈初始化
void STInit(ST* pst);
//2.栈的销毁
void STDestroy(ST* pst);
//3.栈的插入操作
void STPush(ST* pst, int x);
//4.栈的删除操作
void STPop(ST* pst);
//5.取栈顶元素
int STTop(ST* pst);
//6.判断栈是否为空,空为true,非空为false
bool STEmpty(ST* pst);
//7.求栈的大小即有效元素的个数
int STSize(ST* pst);

2.2栈的初始化 STInit 函数

//1.栈初始化
void STInit(ST* pst)
{assert(pst);pst->_arr = NULL;pst->_capacity = 0;pst->_top = 0;//指向栈顶元素的下一个位置,类似于//之前写的顺序表中的_size,指向未使用位置
}

2.3栈的销毁 STDestroy 函数

//2.栈的销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->_arr);//清理位于堆上的数组pst->_arr = NULL;pst->_capacity = pst->_top = 0;
}

2.4栈的插入操作 STPush 函数 

//3.栈的插入操作
void STPush(ST* pst, int x)
{assert(pst);//插入数据之前判断一下容量是否足够,不够就扩容if (pst->_top == pst->_capacity)//容量满了,扩容{//刚开始插入给4个空间,否则就2倍扩容int newcapacity = (pst->_capacity == 0 ? 4 : pst->_capacity * 2);int* newarr = (int*)realloc(pst->_arr, newcapacity * sizeof(int));if (newarr == NULL){perror("realloc failed");return;}pst->_arr = newarr;pst->_capacity = newcapacity;}//有容量了,插入数据pst->_arr[pst->_top] = x;pst->_top++;
}

2.5栈的判断是否为空操作 STEmpty 函数 

//4.判断栈是否为空,空为true,非空为false
bool STEmpty(ST* pst)
{assert(pst);return pst->_top == 0;
}

2.6栈的删除操作 STPop 函数

//5.栈的删除操作
void STPop(ST* pst)
{//首先你得有元素才能删除对吧assert(pst);assert(!STEmpty(pst));pst->_top--;
}

2.7栈的取栈顶元素操作 STTop 函数

//6.取栈顶元素
int STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->_arr[pst->_top - 1];
}

2.8求栈的大小即有效元素的个数 STSize 函数

//7.求栈的大小即有效元素的个数
int STSize(ST* pst)
{assert(pst);return pst->_top;
}

3->测试下我们自己写的栈

#include "Stack.h"//1.测试栈插入,删除,取栈顶元素
void testStack1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d : ",STTop(&st));STPop(&st);}STDestroy(&st);}int main()
{testStack1();return 0;
}

运行,看控制台输出:欧耶,我们自己写的栈可以正常运行

4->您的专属鼓励师

        有些事情,你永远都没有办法做到“顶尖”,因为智力跟不上.但是所有的事情,你都可以做到“高段”,因为它需要的是时间的累积和精力的打磨.不聪明与聪明之间的区别,是很微妙的.有时候我们只会通过一次两次的结果,来判断整个人、整件事,其实这是不明智的.从小,邻居和亲戚在谈论我的时候,都会觉得我很聪明。但是只有我自己知道,我从来没有聪明过,只是看上去比较聪明而已.

        修行之路确实枯燥,但是我们把问题搞懂以后就发现他是那样的美妙!一遍学不会没关系吖,多看几遍,我也是学了好多遍呢,小伙伴们肯定学的又快又好!!!最后希望写的内容对小伙伴们有所帮助,我写的如果有哪里不对的地方请在评论区或者私信指出来哦!让我们一起进步吖,任何疑问包括心情不好都可以找我聊聊,我很乐意当你的倾听者吖.   

http://www.lryc.cn/news/479762.html

相关文章:

  • 如何在 Docker 容器中启动 X11 图形界面程序
  • pycharm保存是自动格式化
  • .netCore WebAPI中字符串加密与解密
  • Next.js + Move 石头剪刀布
  • [面试]关于Redis 的持久化你了解吗
  • Systemd:tmpfiles
  • 【Flutter 内嵌 android 原生 View以及相互跳转】
  • python externally-managed-environment 外部管理环境
  • 前端 | MYTED单篇TED词汇学习功能优化
  • 64 mysql 的 表锁
  • 【计网不挂科】计算机网络期末考试——【选择题&填空题&判断题&简述题】题库(1)
  • ajax关于axios库的运用小案例
  • 微搭低代码入门01变量
  • 盘点2024年10款视频剪辑,哪款值得pick!!
  • 苹果手机照片批量删除:一键清理,释放空间
  • 《AI 大模型:重塑软件开发新生态》
  • uniapp(API-Promise 化)
  • 【考研数学 - 数二题型】考研数学必吃榜(数二)
  • Redis生产问题(缓存穿透、击穿、雪崩)——针对实习面试
  • android openGL中模板测试、深度测试功能的先后顺序
  • CCF PTA 编程培训师资认证2021年7月真题- C++兑换礼品
  • 火山引擎云服务docker 安装
  • 【taro react】 ---- 常用自定义 React Hooks 的实现【六】之类渐入动画效果的轮播
  • 基础算法练习--滑动窗口(已完结)
  • 深度学习经典模型之ZFNet
  • Linux系统-ubuntu系统安装
  • 2-Ubuntu/Windows系统启动盘制作
  • 你使用过哪些MySQL中复杂且使用不频繁的函数?
  • Redis-07 Redis哨兵
  • 7.qsqlquerymodel 与 qtableview使用