数据结构之栈的超详细讲解

2024-05-07 09:44
文章标签 讲解 数据结构 详细 之栈

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

目录

引言

一.栈的概念

二.栈的结构

三.栈的实现

栈结构的实现

栈操作函数的声明

栈中方法的实现

栈的初始化

栈的销毁

入栈

出栈

取栈顶元素

判断栈中是否为空

获取栈中数据个数

四.测试 

代码展示:

结构展示:

五.小结

六.完整代码

Stack.h

Stack.c

text.c

引言

这个专题是专门对栈进行详细的讲解,栈这个数据结构其实和之前的顺序表和单链表一样,同样是线性结构,但它的限制更大,如果想看之前单链表和顺序表数据结构的实现,或者是之后的数据结构我现在还没出的,都可以订阅我这个数据结构初阶的专栏--http://t.csdnimg.cn/sz4xS.好了,话不多说,点赞关注我们开始!

一.栈的概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。 

栈这个数据结构可以总结为四个字:后进先出

二.栈的结构

因为栈也是一种线性结构,所以并不复杂,如下图所示:

栈这种结构在我们生活中其实并不少见,比如我们打羽毛球用的羽毛球桶,装子弹的弹匣,都满足后进先出的一个特性. 

三.栈的实现

栈结构的实现

我们可以用三种方法实现栈这个结构:

方法一:

我们用双向链表构建栈,如下图所示:

这样做的好处是:双向链表能很轻松的寻找前面的节点

方法二:

我们用单链表构建栈,如下图所示:

我们用单链表构建栈时,我们入栈时需要头插,因为单链表找前面的节点是不好找的

方法三:

我们用动态数组构建栈:

这个方法就类似于基于动态数组构建顺序表

那么这三种方法选择哪一种呢?

首先因为单链表的原因,我们先把双向链表PASS掉

接下来就在单链表和动态数组中选择

其实两者相差不大,但由于动态数组具有元素高效率存储,所以这里选择动态数组实现栈

代码展示:

//栈的结构
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

 注意:这里的STDataType和之前的链表和顺序表一样,方便后面进行类型的替换

a时我们的动态数组

top是我们的栈顶指针

capacity是我们的空间容量

栈操作函数的声明

对于线性表来说,操作函数大同小异,所以栈的操作函数其实跟单链表和顺序表差不多

下面便是操作函数的声明:

//函数的声明
//初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//取栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取数据个数
int STSize(ST* pst);

栈中方法的实现

栈的初始化

注意:

栈这里的初始化分为两种方式:

1.top指向-1,top指向栈顶元素,如下图所示:

注意:这里的top不能指向为0,因为这样的话,当top指为0时,不知道是否含有数据

2.top指向0,top指向栈顶元素的下一位,如下图所示:

这里我用了第二种,因为这里的top即为元素个数,对于后面的操作会方便一点.

//初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置pst->top = 0;//top指向栈顶数据//pst->top = -1;pst->capacity = 0;
}

栈的销毁

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

注意最后要将top和capacity置为0

入栈

和顺序表的插入数据类似,首先进行断言处理,再看空间是否够用,不够用就进行两倍扩容.

注意:这里使用了三目操作符,因为我们初始化capacity为0,两倍扩容之后还是为0,所以当它为0时,直接初始化为4,或者其他值.

void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");return;}pst->a = tmp;pst->capacity = newcapcacity;}pst->a[pst->top] = x;pst->top++;
}

出栈

这个很简单,只需top--即可

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

取栈顶元素

注意:这里需要额外对top进行判空处理

//取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}

判断栈中是否为空

top即为我们栈中元素的个数

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

获取栈中数据个数

//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}

四.测试 

我们入栈一些元素,再将它们打印出来.

代码展示:

#include "Stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);//遍历栈中的元素while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}}

结构展示:

后进先出没有问题

五.小结

栈这个数据结构对比顺序表和单链表的实现真的简单了不少,但它的OJ题可不简单,后面我会更新关于栈的经典OJ练习,如果觉得这篇博客对你有帮助的话,一定要点赞关注哦!如果你有任何问题后可以打在评论区,大家一起学习,共同进步!

六.完整代码

Stack.h

#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//栈的结构
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//函数的声明
//初始化和销毁
void STInit(ST* pst);
void STDestory(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

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"//初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置pst->top = 0;//top指向栈顶数据//pst->top = -1;pst->capacity = 0;
}
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
//入栈和出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");return;}pst->a = tmp;pst->capacity = newcapcacity;}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;
}

text.c

#include "Stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);//遍历栈中的元素while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}}

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


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

相关文章

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

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

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
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）
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
《数据结构（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
阅读更多...
沁恒CH32在MounRiver Studio上环境配置以及使用详细教程

沁恒CH32在MounRiver Studio上环境配置以及使用详细教程

目录 1.  RISC-V简介 2.  CPU架构现状 3.  MounRiver Studio软件下载 4.  MounRiver Studio软件安装 5.  MounRiver Studio软件介绍 6.  创建工程 7.  编译代码 1.  RISC-V简介         RISC就是精简指令集计算机（Reduced Instruction SetCom
阅读更多...
arduino ide安装详细步骤

arduino ide安装详细步骤

​ 大家好，我是程序员小羊！ 前言： Arduino IDE 是一个专为编程 Arduino 微控制器设计的集成开发环境，使用起来非常方便。下面将介绍如何在不同平台上安装 Arduino IDE 的详细步骤，包括 Windows、Mac 和 Linux 系统。 一、在 Windows 上安装 Arduino IDE 1. 下载 Arduino IDE 打开 Arduino 官网
阅读更多...
GPT系列之：GPT-1，GPT-2，GPT-3详细解读

GPT系列之：GPT-1，GPT-2，GPT-3详细解读

一、GPT1 论文：Improving Language Understanding by Generative Pre-Training 链接：https://cdn.openai.com/research-covers/languageunsupervised/language_understanding_paper.pdf 启发点：生成loss和微调loss同时作用，让下游任务来适应预训
阅读更多...
多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

目录 多路转接之select 引入 介绍 fd_set 函数原型 nfds readfds / writefds / exceptfds readfds  总结  fd_set操作接口  timeout timevalue 结构体 传入值 返回值 代码 注意点 -- 调用函数 select的参数填充  获取新连接 注意点 -- 通信时的调用函数 添加新fd到
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
【详细介绍一下GEE】

【详细介绍一下GEE】

GEE（Google Earth Engine）是一个强大的云计算平台，它允许用户处理和分析大规模的地球科学数据集，如卫星图像、气候模型输出等。以下是对GEE用法的详细介绍： 一、平台访问与账户设置 访问GEE平台： 用户可以通过访问Google Earth Engine的官方网站来开始使用GEE。 创建账户： 用户需要注册并登录Google账户，然后申请访问GEE平台。申请过程可能需要提
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2