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。

相关文章

使用SQL语言查询多个Excel表格的操作方法

使用SQL语言查询多个Excel表格的操作方法

《使用SQL语言查询多个Excel表格的操作方法》本文介绍了如何使用SQL语言查询多个Excel表格,通过将所有Excel表格放入一个.xlsx文件中,并使用pandas和pandasql库进行读取和... 目录如何用SQL语言查询多个Excel表格如何使用sql查询excel内容1. 简介2. 实现思路3
阅读更多...
Go语言实现将中文转化为拼音功能

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求：新用户入职 创建一系列账号比较麻烦，打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英
阅读更多...
Go语言使用Buffer实现高性能处理字节和字符

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ
阅读更多...
深入理解C语言的void*

深入理解C语言的void*

《深入理解C语言的void*》本文主要介绍了C语言的void*,包括它的任意性、编译器对void*的类型检查以及需要显式类型转换的规则,具有一定的参考价值,感兴趣的可以了解一下... 目录一、void* 的类型任意性二、编译器对 void* 的类型检查三、需要显式类型转换占用的字节四、总结一、void* 的
阅读更多...
C语言线程池的常见实现方式详解

C语言线程池的常见实现方式详解

《C语言线程池的常见实现方式详解》本文介绍了如何使用C语言实现一个基本的线程池,线程池的实现包括工作线程、任务队列、任务调度、线程池的初始化、任务添加、销毁等步骤,感兴趣的朋友跟随小编一起看看吧... 目录1. 线程池的基本结构2. 线程池的实现步骤3. 线程池的核心数据结构4. 线程池的详细实现4.1 初
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2