C语言数据结构之栈

2024-04-27 21:28
文章标签 语言 数据结构 之栈

本文主要是介绍C语言数据结构之栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

    • 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;
}

这篇关于C语言数据结构之栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/941571。

相关文章

GO语言短变量声明的实现示例

GO语言短变量声明的实现示例

《GO语言短变量声明的实现示例》在Go语言中,短变量声明是一种简洁的变量声明方式,使用:=运算符,可以自动推断变量类型,下面就来具体介绍一下如何使用,感兴趣的可以了解一下... 目录基本语法功能特点与var的区别适用场景注意事项基本语法variableName := value功能特点1、自动类型推
阅读更多...
GO语言中函数命名返回值的使用

GO语言中函数命名返回值的使用

《GO语言中函数命名返回值的使用》在Go语言中,函数可以为其返回值指定名称,这被称为命名返回值或命名返回参数,这种特性可以使代码更清晰,特别是在返回多个值时,感兴趣的可以了解一下... 目录基本语法函数命名返回特点代码示例命名特点基本语法func functionName(parameters) (nam
阅读更多...
Go语言连接MySQL数据库执行基本的增删改查

Go语言连接MySQL数据库执行基本的增删改查

《Go语言连接MySQL数据库执行基本的增删改查》在后端开发中,MySQL是最常用的关系型数据库之一,本文主要为大家详细介绍了如何使用Go连接MySQL数据库并执行基本的增删改查吧... 目录Go语言连接mysql数据库准备工作安装 MySQL 驱动代码实现运行结果注意事项Go语言执行基本的增删改查准备工作
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
Go语言使用Gin处理路由参数和查询参数

Go语言使用Gin处理路由参数和查询参数

《Go语言使用Gin处理路由参数和查询参数》在WebAPI开发中,处理路由参数（PathParameter）和查询参数（QueryParameter）是非常常见的需求,下面我们就来看看Go语言... 目录一、路由参数 vs 查询参数二、Gin 获取路由参数和查询参数三、示例代码四、运行与测试1. 测试编程路
阅读更多...
Go语言使用net/http构建一个RESTful API的示例代码

Go语言使用net/http构建一个RESTful API的示例代码

《Go语言使用net/http构建一个RESTfulAPI的示例代码》Go的标准库net/http提供了构建Web服务所需的强大功能,虽然众多第三方框架（如Gin、Echo）已经封装了很多功能,但... 目录引言一、什么是 RESTful API？二、实战目标：用户信息管理 API三、代码实现1. 用户数据
阅读更多...
Go语言网络故障诊断与调试技巧

Go语言网络故障诊断与调试技巧

《Go语言网络故障诊断与调试技巧》在分布式系统和微服务架构的浪潮中,网络编程成为系统性能和可靠性的核心支柱,从高并发的API服务到实时通信应用,网络的稳定性直接影响用户体验,本文面向熟悉Go基本语法和... 目录1. 引言2. Go 语言网络编程的优势与特色2.1 简洁高效的标准库2.2 强大的并发模型2.
阅读更多...
Go语言使用sync.Mutex实现资源加锁

Go语言使用sync.Mutex实现资源加锁

《Go语言使用sync.Mutex实现资源加锁》数据共享是一把双刃剑,Go语言为我们提供了sync.Mutex,一种最基础也是最常用的加锁方式,用于保证在任意时刻只有一个goroutine能访问共享... 目录一、什么是 Mutex二、为什么需要加锁三、实战案例：并发安全的计数器1. 未加锁示例（存在竞态）
阅读更多...
C语言自定义类型之联合和枚举解读

C语言自定义类型之联合和枚举解读

《C语言自定义类型之联合和枚举解读》联合体共享内存,大小由最大成员决定,遵循对齐规则；枚举类型列举可能值,提升可读性和类型安全性,两者在C语言中用于优化内存和程序效率... 目录一、联合体1.1 联合体类型的声明1.2 联合体的特点1.2.1 特点11.2.2 特点21.2.3 特点31.3 联合体的大小1
阅读更多...
Go语言使用select监听多个channel的示例详解

Go语言使用select监听多个channel的示例详解

《Go语言使用select监听多个channel的示例详解》本文将聚焦Go并发中的一个强力工具,select,这篇文章将通过实际案例学习如何优雅地监听多个Channel,实现多任务处理、超时控制和非阻... 目录一、前言：为什么要使用select二、实战目标三、案例代码：监听两个任务结果和超时四、运行示例五
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2