数据结构与算法学习笔记五---栈的表示和实现(C语言)

目录

​​​​​​​前言

一、栈的定义

二、栈的表示和实现

1.定义

2.初始化

3.入栈

4.出栈

5.销毁顺序栈

6.清空顺序栈

7.判断栈是否为空

8.顺序栈的长度

9.遍历顺序栈

10.完整代码

前言

    本片博客介绍的是栈的用法。

一、栈的定义

        栈是一种具有特定操作的数据结构，它按照"先进后出"的原则存储和访问数据。栈具有两个基本操作，分别为入栈（push）和出栈（pop）。入栈将元素放入栈的顶部，出栈则将栈顶的元素取出。栈在计算机科学中广泛应用，例如函数调用、表达式求值、递归算法等。

二、栈的表示和实现

1.定义

        我们一般使用顺序表来表示栈。使用一段连续的存储空间存储栈中的元素。

#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10   // 存储空间分配增量

typedef struct{
    int * base;// 栈底指针
    int * top; // 栈顶指针
    int stacksize;
}SeqStack;

2.初始化

        栈初始化的时候，给栈的基址分配存储空间，初始化之后，栈顶和栈底相同。

// 构造一个空栈
int initSeqStack(SeqStack * seqStack){
    seqStack->base = (int *)malloc(sizeof(int) * STACK_INIT_SIZE);
    if (!seqStack->base) {
        return 0;
    }
    seqStack->top = seqStack->base;
    seqStack->stacksize = STACK_INIT_SIZE;
    return 1;
}

3.入栈

        入栈的时候，我们首先判断下顺序栈是否已满，如果栈满则需要追加存储空间。然后入栈，栈顶指针上移。

// 入栈
int push(SeqStack * seqStack, int element){
    // 如果栈满，则追加存储空间
    if (seqStack->top - seqStack->base >= seqStack->stacksize) {
        seqStack->base = (int *)realloc(seqStack->base, (seqStack->stacksize + STACKINCREMENT) * sizeof(int));
        if (!seqStack->base) {
            return 0; // 存储分配失败
        }
        seqStack->top = seqStack->base + seqStack->stacksize; // 栈顶指针重新定位
        seqStack->stacksize += STACKINCREMENT; // 更新栈的大小
    }
    *(seqStack->top) = element; // 将元素压入栈顶
    seqStack->top++; // 栈顶指针上移
    return 1; // 入栈成功
}

4.出栈

        出栈的时候，首先判断栈是否为空，然后取出栈顶元素。

// 出栈
int popSeqStack(SeqStack *seqStack, int *element){
    if (seqStack->top == seqStack->base) {
        return 0; // 栈空，无法出栈
    }
    *element = *(--seqStack->top); // 出栈，栈顶指针下移
    return 1; // 出栈成功
}

5.销毁顺序栈

        销毁栈的时候，释放栈的存储空间，置空栈顶和栈底。

// 销毁顺序栈
int destroySeqStack(SeqStack *seqStack){
    free(seqStack->base); // 释放存储空间
    seqStack->base = seqStack->top = NULL; // 栈底指针和栈顶指针置空
    seqStack->stacksize = 0; // 栈大小置为0
    return 1; // 销毁成功
}

6.清空顺序栈

        清空栈，栈顶指针回栈底。

// 清空顺序栈
int clearSeqStack(SeqStack *seqStack){
    seqStack->top = seqStack->base; // 栈顶指针回归栈底
    return 1; // 清空成功
}

7.判断栈是否为空

        入栈的时候，我们首先判断下顺序栈是否已满，如果栈满则需要追加存储空间。然后入栈，栈顶指针上移。

// 栈是否为空
int seqStackEmpty(SeqStack * seqStack){
    return seqStack->top == seqStack->base;
}

8.顺序栈的长度

// 顺序栈的长度
int seqStackLength(SeqStack * seqStack){
    int length = seqStack->top - seqStack->base;
    return length;
}

9.遍历顺序栈

// 遍历顺序栈
void traverseSeqStack(SeqStack * seqStack){
    printf("遍历栈中元素：");
    int *p = seqStack->base;
    while (p < seqStack->top) {
        printf("%d ", *p++);
    }
    printf("\n");
}

10.完整代码

#include <stdlib.h>
#include <stdio.h>

#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10   // 存储空间分配增量

typedef struct{
    int * base;// 栈底指针
    int * top; // 栈顶指针
    int stacksize;
}SeqStack;

#pragma mark -- 栈的常用操作

// 构造一个空栈
int initSeqStack(SeqStack * seqStack){
    seqStack->base = (int *)malloc(sizeof(int) * STACK_INIT_SIZE);
    if (!seqStack->base) {
        return 0;
    }
    seqStack->top = seqStack->base;
    seqStack->stacksize = STACK_INIT_SIZE;
    return 1;
}

// 入栈
int push(SeqStack * seqStack, int element){
    // 如果栈满，则追加存储空间
    if (seqStack->top - seqStack->base >= seqStack->stacksize) {
        seqStack->base = (int *)realloc(seqStack->base, (seqStack->stacksize + STACKINCREMENT) * sizeof(int));
        if (!seqStack->base) {
            return 0; // 存储分配失败
        }
        seqStack->top = seqStack->base + seqStack->stacksize; // 栈顶指针重新定位
        seqStack->stacksize += STACKINCREMENT; // 更新栈的大小
    }
    *(seqStack->top) = element; // 将元素压入栈顶
    seqStack->top++; // 栈顶指针上移
    return 1; // 入栈成功
}

// 打印栈中的数据元素
void printSeqStack(SeqStack * seqStack){
    printf("栈中的元素:\n");
    int * p = seqStack->base;
    while (p < seqStack->top) {
        printf("%d\t",*p);
        p++;
    }
    printf("\n");
}

// 获取栈顶元素
int getSeqStackTop(SeqStack * seqStack, int * stackTopElement){
    if (seqStack->top == seqStack->base) {
        return 0; // 栈空，无栈顶元素
    }
    *stackTopElement = *(seqStack->top - 1); // 获取栈顶元素
    return 1;
}

// 出栈
int popSeqStack(SeqStack *seqStack, int *element){
    if (seqStack->top == seqStack->base) {
        return 0; // 栈空，无法出栈
    }
    *element = *(--seqStack->top); // 出栈，栈顶指针下移
    return 1; // 出栈成功
}

// 销毁顺序栈
int destroySeqStack(SeqStack *seqStack){
    free(seqStack->base); // 释放存储空间
    seqStack->base = seqStack->top = NULL; // 栈底指针和栈顶指针置空
    seqStack->stacksize = 0; // 栈大小置为0
    return 1; // 销毁成功
}

// 清空顺序栈
int clearSeqStack(SeqStack *seqStack){
    seqStack->top = seqStack->base; // 栈顶指针回归栈底
    return 1; // 清空成功
}

// 栈是否为空
int seqStackEmpty(SeqStack * seqStack){
    return seqStack->top == seqStack->base;
}

// 顺序栈的长度
int seqStackLength(SeqStack * seqStack){
    int length = seqStack->top - seqStack->base;
    return length;
}

// 遍历顺序栈
void traverseSeqStack(SeqStack * seqStack){
    printf("遍历栈中元素：");
    int *p = seqStack->base;
    while (p < seqStack->top) {
        printf("%d ", *p++);
    }
    printf("\n");
}

// 测试各个方法
void testSeqStack(void){
    SeqStack seqStack;
    printf("栈初始化.......\n");
    if(initSeqStack(&seqStack)){
        printf("栈初始化成功\t✅\n");
    }else{
        printf("栈初始化失败\n");
        return;
    }

    // 入栈
    printf("入栈.......\n");
    for (int i = 1; i <= 10; i++) {
        if (push(&seqStack, i)) {
            printf("%d入栈成功\t✅\n", i);
        } else {
            printf("入栈失败!");
        }
    }

    // 打印栈中元素
    printf("\n********************\t打印栈栈中元素\t********************\n");
    printSeqStack(&seqStack);
    printf("顺序栈的长度:%d\n",seqStackLength(&seqStack));
    // 获取栈顶元素
    int topElement;
    if (getSeqStackTop(&seqStack, &topElement)) {
        printf("栈顶元素：%d\n", topElement);
    } else {
        printf("栈为空，无法获取栈顶元素！\n");
    }

    // 出栈
    int popElement;
    if (popSeqStack(&seqStack, &popElement)) {
        printf("出栈元素：%d\n", popElement);
    } else {
        printf("栈为空，无法出栈！\n");
    }

    // 打印栈中元素
    printf("\n********************\t打印栈栈中元素\t********************\n");
    printSeqStack(&seqStack);

    // 清空栈
    clearSeqStack(&seqStack);
    printf("清空栈后，栈是否为空：%d\n", seqStackEmpty(&seqStack));
}

int main(int argc, const char *argv[]) {
    testSeqStack();
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/593507.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【网络通信】Windows搭建RTMP视频流服务器（含推流/拉流详细教程）

【网络通信】Windows搭建RTMP视频流服务器（含推流/拉流详细教程）

RTMP&#xff08;Real-Time Messaging Protocol&#xff09;是一种用于实时流媒体传输的网络协议&#xff0c;主要用于传输音频、视频和数据。RTMP最初是由Adobe Systems公司开发的&#xff0c;用于其Flash平台和Adobe Media Server&#xff0c;但随着技术的发展和开源社区的推…
阅读更多...
数据结构学习/复习6---双向链表的实现/随机指针链表练习/顺序表与链表对比/存储体系简述

数据结构学习/复习6---双向链表的实现/随机指针链表练习/顺序表与链表对比/存储体系简述

一、链表的结构*8 二、带头双向循环链表的实现 注意事项1&#xff1a;是否需要断言于实际情况中传来的指针是否可以为空&#xff0c;不可以则要断言 三、链表、指针、拷贝经典练习题 四、顺序表与链表总结对比
阅读更多...
通过helm在k8s上安装minio

通过helm在k8s上安装minio

1 helm安装minio 1.1 下载minio 添加仓库 helm repo add bitnami https://charts.bitnami.com/bitnami 将minio拉取下来 helm pull bitnami/minio --version 版本号 解压到本地开始编辑配置文件 tar -zxf minio-xxx.tgz [rootk8s-master01 minio]# vi values.yaml 1.2…
阅读更多...
【C语言】简单有趣的扫雷游戏

【C语言】简单有趣的扫雷游戏

**©作者:末央&#xff06; ©系列:C语言初阶(适合小白入门) ©说明:以凡人之笔墨&#xff0c;书写未来之大梦 目录 一、分析游戏规则二、分文件三、菜单实现四、游戏内容核心实现1.初始化棋盘2.打印棋盘3.布置雷4.排查雷5.game()函数实现调用 五、全部源码 一、分…
阅读更多...
二维泊松方程（Neumann+Direchliet边界条件）有限元Matlab编程求解|程序源码+说明文本

二维泊松方程（Neumann+Direchliet边界条件）有限元Matlab编程求解|程序源码+说明文本

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…
阅读更多...
MySQL索引及优化

MySQL索引及优化

MySQL索引及优化 一、MySQL索引1、什么是索引&#xff1f;2、了解过索引的数据结构吗&#xff1f;B树和B树的区别&#xff1f;&#xff08;底层原理&#xff09;3、什么是聚簇索引&#xff08;聚集索引&#xff09;&#xff1f;什么是非聚簇索引&#xff08;二级索引&#xff0…
阅读更多...
给Ollama套个WebUI，方便使用

给Ollama套个WebUI，方便使用

Ollama 基本的安装使用参考前文 https://xugaoxiang.com/2024/05/01/ollama-offline-deploy/&#xff0c;前文使用的模型是 llama2&#xff0c;本篇将使用 llama3&#xff0c;因此在启动时&#xff0c;命令是 ollama run llama3。 Ollama Llama3 Llama3 是 Meta 发布的大语言模…
阅读更多...
【AI工具声音克隆】——OpenVoice一键部署modelScope一键使用

【AI工具声音克隆】——OpenVoice一键部署modelScope一键使用

一、声音/音色克隆简介 声音或音色克隆的原理实现步骤主要基于深度学习技术&#xff0c;特别是语音合成和生成模型。以下是声音/音色克隆的大致实现步骤&#xff1a; 数据收集&#xff1a; 收集语音数据&#xff0c;作为模型的训练样本。数据应尽可能多样化&#xff0c;包括不…
阅读更多...
GRU模块：nn.GRU层的输出state与output

GRU模块：nn.GRU层的输出state与output

在 GRU&#xff08;Gated Recurrent Unit&#xff09;中&#xff0c;output 和 state 都是由 GRU 层的循环计算产生的&#xff0c;它们之间有直接的关系。state 实际上是 output 中最后一个时间步的隐藏状态。 GRU 的基本公式 GRU 的核心计算包括更新门&#xff08;update gat…
阅读更多...
[C++基础学习-04]----C++数组详解

[C++基础学习-04]----C++数组详解

前言 在C中&#xff0c;数组是一种用来存储相同类型元素的数据结构。一维数组是最简单的数组形式&#xff0c;它由一系列按顺序存储的元素组成。二维数组则是由一维数组构成的数组&#xff0c;可以看作是一堆一维数组堆叠在一起形成的矩阵。 正文 01-数组简介 一维数组和二维…
阅读更多...
库存管理系统开源啦

库存管理系统开源啦

软件介绍 ModernWMS是一个针对小型物流仓储供应链流程的开源库存管理系统。该系统的开发初衷是为了满足中小型企业在有限IT预算下对仓储管理的需求。通过总结多年ERP系统研发经验&#xff0c;项目团队开发了这套适用于中小型企业的系统&#xff0c;以帮助那些有特定需求的用户。…
阅读更多...
计算机毕业设计springboot基于vue电商抢购限时秒杀系统ch0h8

计算机毕业设计springboot基于vue电商抢购限时秒杀系统ch0h8

技术栈 ide工具&#xff1a;IDEA 或者eclipse 编程语言: java 数据库: mysql5.7以上版本 可选框架&#xff1a;ssmspringboot都有的 前端&#xff1a;vue.jsElementUI 详细技术&#xff1a;springbootSSMvueMYSQLMAVEN 数据库工具&#xff1a;Navicat/SQLyog都可以 开发工具 Ec…
阅读更多...
【iOS】KVC

【iOS】KVC

文章目录 前言一、KVC常用方法二、key与keypath区别key用法keypath用法 三、批量存值操作四、字典与模型相互转化五、KVC底层原理KVC设值底层原理KVC取值底层原理 前言 KVC的全称是Key-Value Coding&#xff0c;翻译成中文叫做键值编码 KVC提供了一种间接访问属性方法或成员变…
阅读更多...
基于stm32的USB虚拟U盘+FATFS+W25Q64

基于stm32的USB虚拟U盘+FATFS+W25Q64

基于stm32的USB虚拟U盘FATFSW25Q64 本文目标&#xff1a;基于stm32的USB虚拟U盘FATFSW25Q64 按照本文的描述&#xff0c;简单跑通USB的MSC类来进行简单交互。 先决条件&#xff1a;拥有C语言基础&#xff0c;装有编译和集成的开发环境&#xff0c;比如&#xff1a;Keil uVis…
阅读更多...
mysql其它补充

mysql其它补充

exist和in的区别 exists 用于对外表记录做筛选。 exists 会遍历外表&#xff0c;将外查询表的每一行&#xff0c;代入内查询进行判断。 当 exists 里的条件语句能够返回记录行时&#xff0c;条件就为真&#xff0c;返回外表当前记录。反之如果 exists 里的条件语句不能返回记…
阅读更多...
使用python开发的词云图生成器2.0

使用python开发的词云图生成器2.0

使用python开发的词云图生成器2.0 更新部分词云图主要三方库工具介绍和效果工具界面&#xff1a; 代码 更新部分 1.支持选择字体&#xff1b; 2.支持选择词云图形状 词云图 词云图啊&#xff0c;简单来说&#xff0c;它可以把文本数据中的高频关键词变成不同大小、颜色的词汇…
阅读更多...
一篇文章带你深入了解“指针”

一篇文章带你深入了解“指针”

一篇文章带你深入了解“指针” 内存和地址了解指针指针类型const修饰指针指针的运算指针与整数之间的运算指针与指针之间的运算指针的关系运算 void* 指针传值调用和传址调用数组和指针的关系野指针野指针的形成原因规避野指针 二级指针字符指针指针数组数组指针数组传参一维数…
阅读更多...
(三)JVM实战——对象的内存布局与执行引擎详解

(三)JVM实战——对象的内存布局与执行引擎详解

对象的内存布局 对象的实例化 对象的创建方式 - new的方式 - Class的newInstance():反射的方式 - Construct的newInstance() - clone:实现Cloneable接口,默认浅拷贝 - 使用反序列化&#xff1a;将二进制流转化为内存对象 创建对象的步骤 - 判断对象对应的类是否加载、链接、初…
阅读更多...
基础I/O--文件系统

基础I/O--文件系统

文章目录 回顾C文件接口初步理解文件理解文件使用和并认识系统调用open概述标记位传参理解返回值 closewriteread总结 文件描述符fd0&1&2理解 回顾C文件接口 C代码&#xff1a; #include<stdio.h> int main() { FILE *fpfopen("log.txt",&…
阅读更多...
08 - 步骤 表输出

08 - 步骤 表输出

简介 表输出&#xff08;Table Output&#xff09;步骤是用于将 Kettle 中的数据写入关系型数据库表的步骤。它允许用户将数据流中的数据插入、更新或删除到目标数据库表中。 使用 场景 我要将处理完的数据流中的sysOrgCode 跟 plateNumber 保存记录到mysql 1、拖拽表输出…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站