C语言数据结构之栈

embedded/2024/9/24 6:31:12/

目录

    • 1.栈的概念及结构
    • 2.栈的实现
    • 3.栈的代码实现
    • 4.相关例题

在这里插入图片描述
•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!
在这里插入图片描述

1.栈的概念及结构

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

讲到栈，就要提到它的两种基本操作：压栈（入栈）和出栈。

入栈和出栈遵循一种规则：后进先出（进入栈晚的数据先出栈，就像是先进去的数据被后进入的数据压住了，只能先把上面的数据拿走才能拿到下面的数据）。

在这里插入图片描述

连续入栈和连续出栈：

在这里插入图片描述

2.栈的实现

对于栈的实现，我们有两种结构可以选择：顺序表和链表。考虑到先进后出的规则，链表尾插和尾删的成本比顺序表高，不太适合，顺序表尾插和尾删只需要改变加减的size的大小就可以做到，所以我们采用顺序表来实现栈。

关于栈，我们要实现以下几个接口：

在这里插入图片描述

3.栈的代码实现

test.c

#include "Stack.h"void menu()
{printf("********************************************\n");printf("***************    请选择    ***************\n");printf("******   1.PushStack    2.PopStack   *******\n");printf("******   3.PrintStack   4.TopStack   *******\n");printf("******   5.SizeStack    6.CheckEmpty *******\n"); printf("******             0.Exit            *******\n");printf("********************************************\n");
}int main()
{int input = 0;int value = 0;Stack s;Init_Stack(&s);do{menu();scanf("%d", &input);switch (input){case 1:printf("请输入你要入栈的值>:");scanf("%d", &value);Push_Stack(&s, value);break;case 2:Pop_Stack(&s);break;case 3:Print_Stack(&s);break;case 4:if (Empty_Stack(&s) != 0){printf("栈为空\n");break;}printf("栈顶的元素是%d\n", Top_Stack(&s));break;case 5:printf("栈中有效元素的个数为%d\n", Size_Stack(&s));break;case 6:if (Empty_Stack(&s) != 0)printf("栈为空\n");elseprintf("栈不为空\n");break;case 0:Destroy_Stack(&s);printf("销毁栈成功\n");break;default:printf("选择错误，请重新选择\n");break;}} while (input);return 0;
}

Stack.c

#include "Stack.h"//初始化栈
void Init_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针STDataType* tmp = (STDataType*)malloc(3*sizeof(STDataType));if (tmp == NULL) //申请空间可能失败，失败会返回NULL，不能解引用，要终止程序{perror("Init_Stack\n");exit(1);}ptr->stack = tmp; //申请空间成功就正常初始化ptr->capacity = 3;ptr->size = 0;
}//销毁栈
void Destroy_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针free(ptr->stack);ptr->stack = NULL;
}//检查栈是否满了，满了则扩容
void Check_Capacity(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针if (ptr->size == ptr->capacity){STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));if (tmp == NULL) //申请空间可能失败，失败会返回NULL，不能解引用，要终止程序{perror("Check_Capacity\n");exit(1);}ptr->stack = tmp;   //要把申请到的空间赋给原指针，不然后面操作不了这块空间ptr->capacity *= 2; //扩容之后要修改capacity的值，不然检查栈的大小时会一直扩容}
}//打印栈里面的数据
void Print_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针for (int i = 0; i < ptr->size; i++){printf("%d ", ptr->stack[i]);}printf("\n");
}//数据入栈
void Push_Stack(Stack* ptr,STDataType val)
{assert(ptr); // ptr要解引用，不能为空指针Check_Capacity(ptr); //入栈时要检查空间是否足够ptr->stack[ptr->size] = val;ptr->size++;
}//数据出栈
void Pop_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针if (ptr->size == 0){printf("栈为空\n");return;}ptr->size--; //出栈就相当于顺序表可以读取的元素少一个，size - 1 就可以了
}//获取栈顶数据
STDataType Top_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针return ptr->stack[ptr->size-1];
}//获取栈储存的元素个数
int Size_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针return ptr->size;
}//判断栈是否为空
int Empty_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用，不能为空指针if (ptr->size == 0)return 1;elsereturn 0;
}

Stack.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>typedef int STDataType;  // 栈储存的数据的类型typedef struct Stack
{STDataType* stack;  //动态开辟的空间，在堆上int size;			//储存元素的个数int capacity;		//栈的大小（容量），可变化
}Stack;//栈的初始化
void Init_Stack(Stack* ptr);//打印栈里面的数据
void Print_Stack(Stack* ptr);//数据入栈
void Push_Stack(Stack* ptr, STDataType val);//数据出栈
void Pop_Stack(Stack* ptr);//获取栈顶数据
STDataType Top_Stack(Stack* ptr);//获取栈储存元素的个数
int Size_Stack(Stack* ptr);//判断栈是否为空
int Empty_Stack(Stack* ptr);//销毁栈
void Destroy_Stack(Stack* ptr);

4.相关例题

题目描述：

在这里插入图片描述

参考解析：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* stack;int size;int capacity;
}Stack;void Init_Stack(Stack* ptr)
{assert(ptr);STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));if (tmp == NULL){perror("Init_Stack\n");exit(1);}ptr->stack = tmp;ptr->capacity = 3;ptr->size = 0;
}void Destroy_Stack(Stack* ptr)
{assert(ptr);free(ptr->stack);ptr->stack = NULL;
}void Check_Capacity(Stack* ptr)
{assert(ptr);if (ptr->size == ptr->capacity){STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));if (tmp == NULL){perror("Check_Capacity\n");exit(1);}ptr->stack = tmp;ptr->capacity *= 2;}
}void Print_Stack(Stack* ptr)
{assert(ptr);for (int i = 0; i < ptr->size; i++){printf("%d ", ptr->stack[i]);}printf("\n");
}void Push_Stack(Stack* ptr, STDataType val)
{assert(ptr);Check_Capacity(ptr);ptr->stack[ptr->size] = val;ptr->size++;
}void Pop_Stack(Stack* ptr)
{assert(ptr);if (ptr->size == 0){return;}ptr->size--;
}STDataType Top_Stack(Stack* ptr)
{assert(ptr);return ptr->stack[ptr->size - 1];
}int Size_Stack(Stack* ptr)
{assert(ptr);return ptr->size;
}int Empty_Stack(Stack* ptr)
{assert(ptr);if (ptr->size == 0)return 1;elsereturn 0;
}//解题思路：
//该题比较简单，是对栈特性很好的应用，具体操作如下：
//循环遍历String中的字符，逐个取到每个括号，如果该括号是：
//1. 左括号，直接入栈
//2. 右括号，与栈顶的左括号进行匹配，如果不匹配直接返回false
//否则继续循环
//循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配bool isValid(char* s) 
{Stack st;Init_Stack(&st);while (*s){switch (*s){//是左括号则入栈case '(':case '{':case '[':Push_Stack(&st, *s);break;//是右括号则从栈顶获取左括号来检测是否匹配case ')':case '}':case ']':if (Size_Stack(&st) == 0) // 如果有右括号，而栈里面左括号已经没有了，就不是匹配的return false;char tmp = Top_Stack(&st);Pop_Stack(&st);			 // 取完元素要从栈中删除if (tmp == '(' && *s != ')')return false;else if (tmp == '{' && *s != '}')return false;else if (tmp == '[' && *s != ']')return false;}s++;}if (Empty_Stack(&st)) // 如果完全匹配，循环结束时栈内一定是空的return true;elsereturn false;
}

http://www.ppmy.cn/embedded/19295.html

相关文章

JAVA信息传送代码之下载图片

JAVA信息传送代码之下载图片

JAVA信息传送代码之下载图片 package xin.week1.day3; import org.junit.Test;import java.io.*; import java.net.InetAddress; import java.net.ServerSocket; import java.net.Socket; import java.net.UnknownHostException;/*首先开启客户端服务 * 客户端下载服务端侧的图…
阅读更多...
webpack和vite

webpack和vite

webpack 是一个模块打包工具&#xff0c;使得工程中的各种资源能够被打包成一个整体的bundle.js文件。Webpack具有很高的可配置性和灵活性&#xff0c;使得开发者可以使用各种插件和配置文件来优化它们的工作流程。Webpack适用于大型、复杂的项目&#xff0c;它可以处理多种不…
阅读更多...
前端开发攻略---在Vue3中对ElementPlus中的dialog组件进行二次封装

前端开发攻略---在Vue3中对ElementPlus中的dialog组件进行二次封装

1、演示 2、子组件 在component文件夹下面新建一个文件夹&#xff0c;我这里是myDialog&#xff0c;在 myDialog文件夹创建index.vue文件。 <template><el-dialogv-model"visible":title"title":width"width":fullscreen"fullscre…
阅读更多...
Cocos Creator 声音管理模块SoundMgr详解

Cocos Creator 声音管理模块SoundMgr详解

前言 Cocos Creator 是一款用于开发2D和3D游戏的跨平台游戏引擎&#xff0c;它提供了丰富的功能和工具&#xff0c;使开发者能够快速开发出高质量的游戏。在游戏开发中&#xff0c;声音是一个非常重要的元素&#xff0c;可以增强游戏的氛围和互动性。为了更好地管理游戏中的声…
阅读更多...
Transformer实战 单词预测

Transformer实战 单词预测

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f366; 参考文章&#xff1a;TensorFlow入门实战&#xff5c;第3周&#xff1a;天气识别&#x1f356; 原作者&#xff1a;K同学啊|接辅导、项目定制 一、定义模型 from tempfile import Tempor…
阅读更多...
【React】CSS 局部样式

【React】CSS 局部样式

书写 CSS 的时候&#xff0c;如果 CSS 文件名包含 module&#xff0c;那么说明该 CSS 是一个局部 CSS 样式文件&#xff0c;类似于 vue 中的 scoped。 .avatarContainer {width: 40px;height: 40px;border-radius: 50%;background: rgb(213, 226, 226); }import styles from ..…
阅读更多...
J1.数学建模 Python机器学习介绍

J1.数学建模 Python机器学习介绍

1.基本操作 命令行&#xff1a;代码执行的地方脚本文件&#xff08;.m&#xff09;&#xff1a;敲代码的地方实时脚本文件&#xff08;.mlx&#xff09;&#xff1a;代码执行结果和代码放在一起&#xff0c;可以插入图片…类似小word运行节&#xff1a;实时脚本文件的功能&…
阅读更多...
Websocket

Websocket

javaspring实现步骤 1.直接使用websocket页面作为Websocket客户端 2.导入WebSocket的Maven坐标 3.导入WebSocket服务端组件WebSocketServer&#xff0c;用于和客户端建立连接 4.导入配置类WebSocketConfiguration&#xff0c;注册WebSocket的服务端组件 5. 导入定时任务类WebS…
阅读更多...
最新文章

Copyright @ 2022~2023