当前位置： 首页 > 编程日记 > 正文

c语言 栈结构存放数据类型,数据结构——栈的详解

编程日记 2024-08-25 19:10:00

栈和队列是两种重要的线性结构，从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表的子集。他们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，他们是和线性表大不相同的两类重要的的抽象数据类型。

文章目录

C语言中的栈

栈的定义

C语言中栈的基本操作

栈的初始化

判断是否为空栈

判断是否为满栈

入栈

出栈

C语言实现栈的具体代码

C++中的栈

C++中栈的基本操作

初始化

判断是否为空栈

入栈

出栈

返回栈顶元素

返回栈中元素数目

C语言中的栈

栈的定义

栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶(top)，表头端称为栈低(bottom)。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，所以栈又被称为后进先出的线性表(简称LIFO:Last in, First out.结构)。

1d78e6e8e869a3a90f51d3d0f72c5484.png

C语言中栈的基本操作

栈的基本操作主要有：栈的初始化、判空、判满、取栈顶元素、在栈顶进行插入和删除。在栈顶插入元素称为入栈，在栈顶删除元素称为出栈。

栈的初始化

栈和线性表类似，也有两种存储表示方法顺序栈和链栈，链栈的操作是线性表操作的特例，操作比较容易实现。顺序栈即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，top = 0表示空栈。由于栈在使用的过程中所需要的大小难以估计，所以通常是先为栈分配一个基本容量，然后再使用的过程中，当栈的空间不够使用的时候再继续追加存储空间。我们以下述类型说明作为顺序栈的定义：

typedef struct{

SDataType *base; //栈底指针

SDataType *top; //栈顶指针

int StackSize; //当前已经分配的存储空间，以元素为单位

}SqStack;

栈的初始化操作为：按照设定的初始分配量进行第一次存储分配，这里使用==malloc()==函数来分配存储空间。malloc()函数的详细说明请看：malloc详细说明。base作为栈底指针，它始终指向栈底，所以s.top = s.base可以作为栈空的标记。top为栈顶指针，top的初值指向栈底。每当插入一个元素时top加1，弹出一个元素时top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

206f67c8b62468265d8e1ddac4753d9b.png

//初始化顺序栈，构造一个空栈

Status InitStack(SqStack &S){

//分配存储空间

S.base = (SDataType *)malloc(STACK_INIT_SIZE*sizeof(SDataType));

if(!S.base){

//如果分配失败，则返回error

return OVERFLOW;

}

//S.top 始终指向栈顶元素的下一个位置

S.top = S.base; //初始状态下为空栈

S.StackSize = STACK_INIT_SIZE; //当前已经分配的存储容量为100个

return OK;

}

判断是否为空栈

当我们弹出栈顶元素时，往往需要判断一下栈是否为空来防止发生下溢。上面我们说到==base作为栈底指针，它始终指向栈底，所以s.top = s.base可以作为栈空的标记。==所以我们可以这样判断栈是否为空：

//判断是否为空栈

void judgeNull(SqStack &s){

if(s.top == s.base){

printf("此栈为空栈！\n");

}else{

printf("此栈不为空栈！\n");

}

}

判断是否为满栈

当我们使一个元素入栈的之前，我们往往需要判断一下栈是否为满栈，防止发生上溢的情况。因为我们定义了一个StackSize来表示当前已经分配的存储空间，所以我们可以用s.top - s.base 来算出当前已经使用的栈空间。所以当s.top - s.base == s.StackSize时表示已经满栈：

//判断是否为满栈

void judgeFull(SqStack &s){

if(s.top-s.base == s.StackSize){

printf("栈满！\n");

}else{

printf("栈未满！\n");

}

}

入栈

入栈时我们首先要判断栈是否为满栈，如果为满栈我们要首先追加存储空间，然后才能将元素入栈。realloc()函数详解请看realloc详解

//入栈

Status Push(SqStack &s,SDataType e){

SDataType *p;

//首先判断栈是不是满的(上溢)

if(s.top-s.base == s.StackSize){

//追加空间

p = (SDataType *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SDataType));

if(!p){

//如果没有找到符合条件的存储空间，则返回error

return OVERFLOW;

}

//成功找到则使s.base指向p

s.base = p;

s.top = s.base + s.StackSize;

s.StackSize += STACKINCREMENT;

}

//先插入元素，然后将栈顶指针加 1

*(s.top) = e;

s.top++;

return OK;

}

出栈

出栈时我们首先要判断栈是否为空栈。如果栈已经空了，则返回error。

//出栈

Status Pop(SqStack &s,SDataType &e){

//判断是否会发生下溢

if(s.top != s.base){

s.top--; //先将栈顶指针减 1

e = *(s.top);

}else{

return 0;

}

return e;

}

C语言实现栈的具体代码

#include

#include

#define STACK_INIT_SIZE 100//栈的初始容量

#define STACKINCREMENT 10//容量增量

#define OK 1

#define OVERFLOW -2

typedef int SDataType;

typedef int Status;

typedef struct{

SDataType *base; //栈底指针

SDataType *top; //栈顶指针

int StackSize; //当前已经分配的存储空间，以元素为单位

}SqStack;

//初始化顺序栈，构造一个空栈

Status InitStack(SqStack &S){

//分配存储空间

S.base = (SDataType *)malloc(STACK_INIT_SIZE*sizeof(SDataType));

if(!S.base){

//如果分配失败，则返回error

return OVERFLOW;

}

//S.top 始终指向栈顶元素的下一个位置

S.top = S.base; //初始状态下为空栈

S.StackSize = STACK_INIT_SIZE; //当前已经分配的存储容量为100个

return OK;

}

//入栈

Status Push(SqStack &s,SDataType e){

SDataType *p;

//首先判断栈是不是满的(上溢)

if(s.top-s.base == s.StackSize){

//追加空间

p = (SDataType *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SDataType));

if(!p){

//如果没有找到符合条件的存储空间，则返回error

return OVERFLOW;

}

//成功找到则使s.base指向p

s.base = p; //系统会将原来的内容复制过来

s.top = s.base + s.StackSize;

s.StackSize += STACKINCREMENT;

}

//先插入元素，然后使栈顶指针加 1

*(s.top) = e;

s.top++;

return OK;

}

//出栈

Status Pop(SqStack &s,SDataType &e){

//判断是否会发生下溢

if(s.top != s.base){

s.top--; //先将栈顶指针减 1

e = *(s.top);

}else{

return 0;

}

return e;

}

//判断是否为空栈

void judgeNull(SqStack &s){

if(s.top == s.base){

printf("此栈为空栈！\n");

}else{

printf("此栈不为空栈！\n");

}

}

//判断是否为满栈

void judgeFull(SqStack &s){

if(s.top-s.base == s.StackSize){

printf("栈满！\n");

}else{

printf("栈未满！\n");

}

}

int main(){

SqStack s;

SDataType element;

InitStack(s); //初始化栈

//将1-5入栈

for(int i=1;i<=10;i++){

Push(s,i);

}

judgeNull(s);

judgeFull(s);

printf("出栈：\n");

//只要栈不为空

while(s.top != s.base){

Pop(s,element); //出栈的元素用e接收

printf("%d ",element);

}

printf("\n");

judgeNull(s);

return 0;

}

C++中的栈

C++ 对模板(Template)支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。STL的代码从广义上讲分为三类：algorithm(算法)、container(容器)和iterator(迭代器)，几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文件：、、、、、、、、、、、和。其中的就是栈。

C++的STL已经将栈的操作都封装成了函数，我们只需要引进#include头文件即可使用。

C++中栈的基本操作

初始化

我们可以直接使用stacks;来创建一个空的 stack 对象。

判断是否为空栈

使用empty()函数来判断栈是否为空。

d0f18c3f57131ce400a3da4ef7118f86.png

入栈

使用push()函数来完成入栈操作。

1760263b2ec3c1afec5b7afe77251893.png

出栈

使用pop()函数实现出栈

654d7e7fea68bee47ae4a3151445e3a5.png

返回栈顶元素

使用top()函数返回栈顶元素

34474fcbeb344e9cad67de858a93620f.jpg

返回栈中元素数目

使用size()函数返回栈中元素的数目。

6ee7352b68acc06f6bd6f7c166015d23.png

以上就是C语言和C++中栈的基本用法了，如果你觉得我的文章对你有用请点个赞支持一下吧，如果喜欢我写的文章那么请点个关注再走。

f24b41ce88be65a0c319ff54867c2c7c.png

下一篇将继续写数据结构的队列，后续将会再写一些有关栈和队列的具体应用。我是ACfun：一个成长中的程序猿，感谢大家的支持。


https://www.dkcj.cn/info/15848.html

相关文章：

Verlet Integration

Verlet Integration Verlet 积分法是一种用于求解牛顿运动方程的数值方法&#xff0c;被广泛运用于动力学模拟以及视频游戏中。尔莱算法的优点在于&#xff1a;数值稳定性比简单的欧拉方法高很多&#xff0c;并保持了物理系统中的时间可逆性与相空间体积元体积守恒的性质。 基本…

编程日记2024/08/25 19:00:00

[译] iOS 开发之新版 APNs 搭建必备知识

原文链接&#xff1a;http://www.jianshu.com/p/d8dba6c2c07a本文的大部分内容是对苹果关于 APNs 官方文档的翻译以及整理。 —— 由 稀土君 分享本文的大部分内容是对苹果关于APNs官方文档的翻译以及整理。 一、设备token和消息的生命周期 关于设备token以及推送消息的生命周期…

编程日记2024/08/25 18:50:00

使用Application.GetResourceStream从XAP安装包加载任意资源

不得不说&#xff0c;WP7开发的资料真的是太少了&#xff0c;国内有句话叫“天下文章一大抄”&#xff0c;查Application.GetResourceStream的用法&#xff0c;找遍了整个网络&#xff0c;无非就那一两篇&#xff0c;而且写得还不完整&#xff0c;包括微软官方的例子。在花了近…

编程日记2024/08/25 18:40:00

c语言知道算法写不出代码,这个代码怎么写算法啊，求教，我真的不会写算法怎么办#incl...

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼这个代码怎么写算法啊&#xff0c;求教&#xff0c;我真的不会写算法怎么办#include "stdio.h"#define N 3 //学生数3。struct Student //建立结构体。{int num;char name[20];float score[3];float aver;};int main(){v…

编程日记2024/08/25 18:30:00

猎豹MFC--列表控件ListControl

ListControl添加变量&#xff1a;关联控件变量&#xff1a;初始化&#xff1a;设置样式 添加列标题&#xff1a;添加位图资源&#xff1a;添加位图变量&#xff1a;创建图像列表&#xff1a;并把图像列表 给 列表控件使用&#xff1a;双击添加行按钮&#xff1a;添加第2列时 不…

编程日记2024/08/25 18:20:00

iOS 命令行自动打包 (archive)

原文链接&#xff1a;http://www.jianshu.com/p/2247f76404ebiOS 开发工程师在测试修复 bug 的过程中&#xff0c;一般会存在频繁打包的情况&#xff0c;如果一步步在 xcode 中点击 archive&#xff0c;下一步&#xff0c;下一步。。。这样太浪费我们的时间了。下面我们来介绍在…

编程日记2024/08/25 18:10:00

看看现在大型网站都是用什么语言写的 ？

看看现在大型网站都是用什么语言写的 &#xff1f; 不排除一个网站用多种技术&#xff01;如淘宝是Java php&#xff0c;底层是java&#xff0c;表现层是php。新浪&#xff0c;网易&#xff0c;腾讯应该也是用了多种技术。 据说是这样的&#xff1a;php&#xff0c;新浪&#…

编程日记2024/08/25 18:00:00

数据结构 算法与应用C 语言描述第六章,数据结构算法与应用-C语言描述002.pdf

下载下载第2 章 程 序 性 能以下是本章中所介绍的有关程序性能分析与测量的概念&#xff1a;• 确定一个程序对内存及时间的需求。• 使用操作数和执行步数来测量一个程序的时间需求。• 采用渐进符号描述复杂性&#xff0c;如 O、 、 、o 。• 利用计时函数测量一个程序的实际…

编程日记2024/08/25 17:50:00

GCD 容易让人迷惑的几个小问题

来源&#xff1a;涂耀辉 链接&#xff1a;http://www.jianshu.com/p/ff444d664e51 写在开头&#xff1a; 本文旨在阐述一些大家容易产生迷惑的GCD相关内容&#xff0c;如果是需要了解一些GCD概念或者基础用法&#xff0c;可以看看这两篇文章&#xff1a;GCD 扫盲篇、巧谈GCD 。…

编程日记2024/08/25 17:40:00

【贪心】【codevs】1214 线段覆盖

http://codevs.cn/problem/1214/ 我去这个题。。。wa的我都没脾气了。。。 我写while&#xff08;~scanf&#xff08;“%d”&#xff0c; &n&#xff09;&#xff09;竟然是不对的。。。 这个程序你妹多次输入是不能结束的&#xff1f;&#xff1f;&#xff1f;&#xff1f…

编程日记2024/08/25 17:30:00

虚函数表剖析，网上转的，呵呵

http://www.cppblog.com/xczhang/archive/2008/01/20/41508.html C虚函数表解析(转)C中的虚函数的作用主要是实现了多态的机制。关于多态&#xff0c;简而言之就是用父类型别的指针指向其子类的实例&#xff0c;然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的…

编程日记2024/08/25 17:20:00

c++语言文件流,C++ IO类、文件输入输出、string流详细讲解

新的C标准中有三分之二的内容都是描述标准库。接下来重点学习其中几种核心库设施&#xff0c;这些是应该熟练掌握的。标准库的核心是很多容器类(顺序容器和关联容器等)和一簇泛型算法(该类算法通常在顺序容器一定范围内的元素上或其他类型的序列上进行操作)。该篇主要学习IO库。…

编程日记2024/08/25 17:10:00

iOS 走近商城 APP(三 WKWebView 商品规格选择框架封装)

原文链接&#xff1a;http://www.jianshu.com/p/293ee1bfe104商城 —— 由 3033 分享开篇 忽然发现最近也只有值班才能写东西了&#xff0c;中间更新了两篇其他的断了下商城相关的文章&#xff0c;仔细看了看之前觉得干货太少&#xff0c;今天写点实际的吧&#xff0c;闲说少说…

编程日记2024/08/25 17:00:00

c语言如何不产生僵尸进程,第三章 九析带你处理 zombie(defunct) 进程

目录1 前言2 僵尸进程2.1 进程简介2.2 僵尸进程例子2.3 僵尸进程危害3 处理僵尸进程3.1 kill 命令3.2 kill 父进程3.3 reboot3.4 magic sysrq key 方法1 前言在 centos7 跑 Docker 和 k8s 时&#xff0c;偶尔会出现 systemctl 失效的情况&#xff0c;现象如下&#xff1a;Faile…

编程日记2024/08/25 16:50:00

音视频开发学习笔记

http://www.jianshu.com/notebooks/6409162/top

编程日记2024/08/25 16:40:00

VS2010 MFC中改变static字体颜色、大小、背景颜色（自定义类），及手动关联变量的方法...

在MFC的Dialog工程中生成一个CStatic的自定义类&#xff0c;类名例如为&#xff1a;CColorStatic 定义必要的变量&#xff1a; protected:COLORREF m_crText; // 字体颜色COLORREF m_crBackColor; // 背景颜色HBRUSH m_hBrush; // 画刷LOGFONT m_lf; // 字体…

编程日记2024/08/25 16:30:00

android 上传字符串,Android中发送Http请求(包括文件上传、servlet接收)的实例代码...

/*** 通过拼接的方式构造请求内容&#xff0c;实现参数传输以及文件传输* param actionUrl* param params* param files* return* throws IOException*/public static String post(String actionUrl, Map params,Map files) throws IOException {String BOUNDARY java.util.UU…

编程日记2024/08/25 16:20:00

JavaScript最全编码规范

转载: JavaScript最全编码规范 类型 ●基本类型&#xff1a;访问基本类型时&#xff0c;应该直接操作类型值 ●string ●number ●boolean ●null ●undefined var foo 1; var bar foo; bar 9; console.log(foo, bar); // > 1, 9 ●复合类型&#xff1a;访问复合类型时&a…

编程日记2024/08/25 16:10:00

源码推荐：collectionView拖拽,仿凤凰FM iOS 局部监听键盘再也不会挡住输入框

UICollectionView拖拽移动单元以及本地保存&#xff08;上传者&#xff1a;dengqi&#xff09; UICollectionView拖拽移动单元以及本地保存&#xff0c;可以保存你上次移动的位置。 仿映客直播导航条&#xff08;上传者&#xff1a;Coolcool&#xff09; 仿映客直播自定义TabBa…

编程日记2024/08/25 16:00:00

采集练习(一) php 获得全国的小学(数据来自腾讯朋友网)

注&#xff1a;发现腾讯朋友网已经改版&#xff0c;部分参数需要自己获得修改 &#xff01;&#xff01;&#xff01; 年前有个需求获得某省的小学数据&#xff0c;分析了下朋友网的小学学校发现可以获得相关数据。 如获得 湖南省郴州市宜章县的全部小学 发现网页请求的地址…

编程日记2024/08/25 15:50:00

android 模板方法模式,安卓设计模式(七)模板方法模式

模板方法模式用于固定相关操作的执行流程,将具体实现延迟到子类中该系列其他文章:定义: 定义一个操作中算法的框架,而降一些步骤延迟到子类中,使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤.使用场景:代码重构时,模板方法是经常被用到的,将固定部分提取到父…

编程日记2024/08/25 15:40:00

solr单机版的搭建

一、solr单机版的搭建 1.运行环境 solr 需要运行在一个Servlet容器中&#xff0c;Solr4.10.3要求jdk使用1.7以上&#xff0c;Solr默认提供Jetty&#xff08;ja&#xff09;&#xff0c;本教va写的Servlet容器程使用Tocmat作为Servlet容器&#xff0c;环境如下&#xff1a; Solr…

编程日记2024/08/25 15:30:00

android5.0后新特性修改标题头,Android5.0中Material Design的新特性

Material Design简介Material Design是谷歌新的设计语言&#xff0c;谷歌希望寄由此来统一各种平台上的用户体验&#xff0c;Material Design的特点是干净的排版和简单的布局&#xff0c;以此来突出内容。Material Design对排版、材质、配色、光效、间距、文字大小、交互方式、…

编程日记2024/08/25 15:20:00

MFCard：易用的信用卡支付集成类库

原文链接&#xff1a;https://github.com/MobileFirstInc/MFCardMFCard&#xff1a;易用的信用卡支付集成类库。# 为开源点赞# —— 由 SwiftLanguage 分享MFCard is an awesome looking Credit Card input & validation control. Written in Swift 3. Demo Usage First St…

编程日记2024/08/25 15:10:00

Castle ActiveRecord学习（四）延迟加载、分页查询、where条件

一、延迟加载 //用户发布的主题&#xff0c;一对多&#xff1b;Table&#xff1a;外键表&#xff1b;ColumnKey&#xff1a;外键&#xff1b;Lazy&#xff1a;延迟加载&#xff1b;Cascade&#xff1a;级联操作&#xff08;级联删除&#xff09;[HasMany(typeof(ThemeInfo), Ta…

编程日记2024/08/25 15:00:00

系统吞吐量（TPS）、用户并发量、性能测试概念和公式(转载)

原文地址&#xff1a;http://www.ha97.com/5095.html PS&#xff1a;下面是性能测试的主要概念和计算公式&#xff0c;记录下&#xff1a; 一&#xff0e;系统吞度量要素&#xff1a; 一个系统的吞度量&#xff08;承压能力&#xff09;与request对CPU的消耗、外部接口、IO等等…

编程日记2024/08/25 14:50:00

android layout后还原位置,Android图片框架photoview如何记住所有状态并还原，包括缩放度，缩放后的移动的距离等等...

Android图片框架photoview如何记住状态并还原&#xff0c;包括缩放度&#xff0c;缩放后的移动的距离等等,尝试了好多方法都没有作用。private void generateImages() {for (int i 0; i < imagesEntities.size(); i) {// PhotoViewAttacher attacher;final ImagesEntity en…

编程日记2024/08/25 14:40:00

Shiro安全登录框架

环境准备 本文使用Maven构建&#xff0c;因此需要一点Maven知识。首先准备环境依赖&#xff1a; Java代码 <dependencies> <dependency> <groupId>junit</groupId> <artifactId>junit</artifactId> <…

编程日记2024/08/25 14:30:00

iOS自动签名打包(xcodebuild)----常用

iOS自动打包主要用xcodebuild命令, 在终端输入xcodebuild --help可以查看xcodebuild的参数。 xcodebuild具体语法&#xff1a; 无workspace的工程 xcodebuild [-project name.xcodeproj] [[-target targetname] … | -alltargets] [-configuration configurationname] [-sdk [s…

编程日记2024/08/25 14:20:00

设计模式解析（五）——几种设计模式之Facade和Adapter

由于个人时间原因&#xff0c;无法详细描述这些模式&#xff0c;暂且记录下来以后慢慢补充详细。 Facade模式 Facade模式&#xff1a;关键特征 意图希望简化原有系统的使用方式。需要定义自己的接口。问题只需使用某个复杂系统的子集&#xff0c;或者&#xff0c;需要以一种特殊…

编程日记2024/08/25 14:10:00