【数据结构】实现栈

article/2024/4/13 14:23:09

大家好,我是苏貝,本篇博客带大家了解栈,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️
在这里插入图片描述


目录

  • 一 .栈的概念及结构
  • 二 .栈的实现
    • 栈的结构体
    • 初始化
    • 销毁
    • 栈顶插入
    • 栈顶删除
    • 显示栈顶元素
    • 是否为空
    • 栈的大小
  • 三. 模块化代码实现
    • Stack.h
    • Stack.c
    • Test.c
    • 结果演示

一 .栈的概念及结构

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

在这里插入图片描述


二 .栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些,因为数组在尾上插入数据的代价比较小(数组的尾插、尾删很方便)。所以下面我们用数组来实现
在这里插入图片描述

1

栈的结构体

typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int top; // 栈顶
}ST;

上面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;

2

初始化

因为我们要对ST类型的变量进行初始化,所以实参要传ST类型变量的地址,用一级指针来接收。因为实参(ST类型变量的地址)不可能为NULL,所以对它断言(下面的接口同理)。
注意:我们这里的top指的是栈顶元素的下一个,而非栈顶元素,所以将它初始化为0

void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;//指向栈顶元素的下一个
}

3

销毁

注意:在这里我们使用的是动态开辟内存,所以要在销毁时释放掉动态开辟的内存,也就是pst->a指向的那个数组

void STDestroy(ST* pst)
{assert(pst);if (pst->a != NULL){free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;}
}

4

栈顶插入

再插入元素之前我们要先判断是否要增容,因为在初始化时我们将pst->capacity初始化为0,所以在增容时要特别注意将pst->capacity==0的情况。还要注意对realloc的结果进行判断,防止realloc失败返回NULL,又直接将NULL赋值给pst->a,这样就再找不到开辟的数组了。
最后不要忘记pst->top++

void STPush(ST* pst, STDataType x)
{assert(pst);//判断是否需要增容if (pst->top == pst->capacity){int newcapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(ST));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//插入数据pst->a[pst->top] = x;pst->top++;
}

5

栈顶删除

删除时我们必须保证栈内有元素,所以要对pst->top>0断言,如果top==0,表示栈内已无元素,返回错误信息,下面的显示栈顶元素同理

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

6

显示栈顶元素

STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}

7

是否为空

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

8

栈的大小

int STSize(ST* pst)
{assert(pst);return pst->top;
}

三. 模块化代码实现

Stack.h

#include<stdio.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);

Stack.c

#include"Stack.h"//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;//指向栈顶元素的下一个
}//销毁
void STDestroy(ST* pst)
{assert(pst);if (pst->a != NULL){free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;}
}//栈顶插入
void STPush(ST* pst, STDataType x)
{assert(pst);//判断是否需要增容if (pst->top == pst->capacity){int newcapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(ST));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(pst->top > 0);pst->top--;
}//显示栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);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;
}

Test.c

#include"Stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){printf("%d  ", STTop(&s));STPop(&s);}printf("\n");return 0;
}

结果演示

在这里插入图片描述


好了,那么本篇博客就到此结束了,如果你觉得本篇博客对你有些帮助,可以给个大大的赞👍吗,感谢看到这里,我们下篇博客见❤️


http://www.ngui.cc/article/show-1929950.html

相关文章

协议(网络协议)

HTTP/HTTPS 协议 HTTP 实际上是个缩写&#xff0c;英文全称是&#xff1a;Hyper Text Transfer Protocol &#xff08;超文本传输协议&#xff09;。 最常用的网页&#xff08;也叫web页&#xff09;就是一种超文本的具体表现形式。HTTPS &#xff08;全称&#xff1a;Hyper …

二叉树最小深度,最大深度,完全二叉树结点数

第六章 二叉树part03 今日内容&#xff1a; 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数 详细布置 104.二叉树的最大深度 &#xff08;优先掌握递归&#xff09; 给定一个二叉树&#xff0c;找出其最大深度。 二叉树的深度…

蓝桥杯算法题汇总

一.线性表&#xff1a;链式 例题&#xff1a;旋转链表 二.栈&#xff1a; 例题&#xff1a;行星碰撞问题 三.队列 三.数组和矩阵 例题&#xff1a;

王腾飞出席整体系统智能节电设备在工矿企业中的应用

演讲嘉宾&#xff1a;王腾飞 中科兆和电力技术&#xff08;山东&#xff09;有限公司综合能源管理事业部--部长 演讲题目&#xff1a;整体系统智能节电设备在工矿企业中的应用 会议简介 “十四五”规划中提出&#xff0c;提高工业、能源领城智能化与信息化融合&#xff0c;明…

vscode+remote突然无法连接服务器以及ssh连接出问题时的排错方法

文章目录 设备描述状况描述解决方法当ssh连接出问题时的排错方法 设备描述 主机&#xff1a;win11&#xff0c;使用vscode的remote-ssh插件 服务器&#xff1a;阿里云的2C2GUbuntu 22.04 UFIE 状况描述 之前一直使用的是vscode的remote服务&#xff0c;都是能够正常连接服务…

java的jar打包docker镜像,启动加载

测试环境&#xff0c;打包镜像 1,把jar包复制/data/liu/mssda.jar, cd到这个目录下 2&#xff0c;创建Dockerfile文件&#xff0c;jdk17版本&#xff0c;内容如下 jdk8版本 FROM openjdk:8-jre-alpine WORKDIR /app COPY . /app CMD ["java", "-jar",…

输出梯形 C语言

解析&#xff1a;这个输出图形的题就是一个找规律加数学计算&#xff0c;我们发现每行比上一行多两个*&#xff0c;最后一行的*表达式为h&#xff08;h-1&#xff09;*2&#xff0c;即3*h-2&#xff0c;那么每一行就是一个先输出最后一行&#xff0d;当前行*个数个空格&#xf…

太阳能供电井盖-物联网智能井盖监测系统-旭华智能

在这个日新月异的科技时代&#xff0c;城市的每一个角落都在悄然发生变化。而在这场城市升级的浪潮中&#xff0c;智能井盖以其前瞻性的科技应用和卓越的安全性能&#xff0c;正悄然崭露头角&#xff0c;变身马路上的智能“眼睛”&#xff0c;守护城市安全。 传统的井盖监测系统…

基于springboot+vue的客户关系管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

day03-Vue-Element

一、Ajax 1 Ajax 介绍 1.1 Ajax 概述 概念&#xff1a;Asynchronous JavaScript And XML&#xff0c;异步 的 JavaScript 和 XML。 作用&#xff1a; 数据交换&#xff1a;通过 Ajax 可以给服务器发送请求&#xff0c;并获取服务器响应的数据。异步交互&#xff1a;可以在 不…