数据结构【第4章】——栈与队列

队列是只允许在一端进行插入操作、而在另-端进行删除操作的线性表。

栈与队列:栈是限定仅在表尾进行插入和删除操作的线性表

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。
在这里插入图片描述

问题:最先进栈的元素,是不是就只能是最后出栈呢?

不一定。栈对线性表的插入和删除的位置进行了限制,并没有对元素进出的时间进行限制,也就是说,在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素出栈就可以。

栈的抽象数据类型

对干栈来讲,理论上线性表的操作特性它都具备,可由干它的特殊性,所以针对它在操作上会有些变化。特别是插入和删除操作,我们改名为push和pop。
在这里插入图片描述
由于栈本身就是一个线性表,因此线性表的顺序存储和链式存储,对于栈来说,也是同样适用。

栈的顺序存储结构及实现

栈是线性表的特例,因此栈的顺序存储也是线性表顺序存储的简化,我们简称为顺序栈

线性表是用数组来实现的,用数组的下标0作为栈底比较好,因为首元素都会存在栈底,变化量小。

我们定义一个top变量来指示栈顶元素在数组中的位置,它可以来回移动,意味着栈顶的top可以变大变小,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在—个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1
在这里插入图片描述
在这里插入图片描述

#include "stdio.h"    
#include "stdlib.h"   #include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int *//* 顺序栈结构 */
typedef struct
{SElemType data[MAXSIZE];int top; /* 用于栈顶指针 */
}SqStack;Status visit(SElemType c)
{printf("%d ",c);return OK;
}/*  构造一个空栈S */
Status InitStack(SqStack *S)
{ /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */S->top=-1;return OK;
}/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{ S->top=-1;return OK;
}/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
Status StackEmpty(SqStack S)
{ if (S.top==-1)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数,即栈的长度 */
int StackLength(SqStack S)
{ return S.top+1;
}/* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{if (S.top==-1)return ERROR;else*e=S.data[S.top];return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{if(S->top == MAXSIZE -1) /* 栈满 */{return ERROR;}S->top++;				/* 栈顶指针增加一 */S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */return OK;
}/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ if(S->top==-1)return ERROR;*e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */S->top--;				/* 栈顶指针减一 */return OK;
}/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{int i;i=0;while(i<=S.top){visit(S.data[i++]);}printf("\n");return OK;
}int main()
{int j;SqStack s;int e;if(InitStack(&s)==OK)for(j=1;j<=10;j++)Push(&s,j);printf("栈中元素依次为:");StackTraverse(s);Pop(&s,&e);printf("弹出的栈顶元素 e=%d\n",e);printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));GetTop(s,&e);printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));ClearStack(&s);printf("清空栈后,栈空否:%d(1:空 0:否)\n",StackEmpty(s));return 0;
}

两栈共享空间

前提:两个栈中的数据类型相同
使用场景:通常是当两个栈的空间需求有相反关系时,即一个栈增长时另一个栈在缩短。
在这里插入图片描述

#include "stdio.h"    
#include "stdlib.h"   #include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int *//* 两栈共享空间结构 */
typedef struct 
{SElemType data[MAXSIZE];int top1;	/* 栈1栈顶指针 */int top2;	/* 栈2栈顶指针 */
}SqDoubleStack;Status visit(SElemType c)
{printf("%d ",c);return OK;
}/*  构造一个空栈S */
Status InitStack(SqDoubleStack *S)
{ S->top1=-1;S->top2=MAXSIZE;return OK;
}/* 把S置为空栈 */
Status ClearStack(SqDoubleStack *S)
{ S->top1=-1;S->top2=MAXSIZE;return OK;
}/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
Status StackEmpty(SqDoubleStack S)
{ if (S.top1==-1 && S.top2==MAXSIZE)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数,即栈的长度 */
int StackLength(SqDoubleStack S)
{ return (S.top1+1)+(MAXSIZE-S.top2);
}/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{if (S->top1+1==S->top2)	/* 栈已满,不能再push新元素了 */return ERROR;	if (stackNumber==1)			/* 栈1有元素进栈 */S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */else if (stackNumber==2)	/* 栈2有元素进栈 */S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */return OK;
}/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{ if (stackNumber==1) {if (S->top1==-1) return ERROR; /* 说明栈1已经是空栈,溢出 */*e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */}else if (stackNumber==2){ if (S->top2==MAXSIZE) return ERROR; /* 说明栈2已经是空栈,溢出 */*e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */}return OK;
}Status StackTraverse(SqDoubleStack S)
{int i;i=0;while(i<=S.top1){visit(S.data[i++]);}i=S.top2;while(i<MAXSIZE){visit(S.data[i++]);}printf("\n");return OK;
}int main()
{int j;SqDoubleStack s;int e;if(InitStack(&s)==OK){for(j=1;j<=5;j++)Push(&s,j,1);for(j=MAXSIZE;j>=MAXSIZE-2;j--)Push(&s,j,2);}printf("栈中元素依次为:");StackTraverse(s);printf("当前栈中元素有:%d \n",StackLength(s));Pop(&s,&e,2);printf("弹出的栈顶元素 e=%d\n",e);printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));for(j=6;j<=MAXSIZE-2;j++)Push(&s,j,1);printf("栈中元素依次为:");StackTraverse(s);printf("栈满否:%d(1:否 0:满)\n",Push(&s,100,1));ClearStack(&s);printf("清空栈后,栈空否:%d(1:空 0:否)\n",StackEmpty(s));return 0;
}

栈的链式存储结构及实现

栈的链式存储结构,简称为链栈。

栈只是栈顶来做插入和删除操作,栈顶应该在链表的头部还是尾部呢?由于单链表有头指针,而栈顶指针也是必需的,所以好的办法是把栈顶放在单链表的头部。

因为已经有栈顶在头部了,所以单链表中的头结点也就失去了意义,通常对于链栈来说,是不需要头结点的

在这里插入图片描述
对于空栈来说,链表原定义是头指针指向空,那么链栈的空其实就是top=NULL的时候。
在这里插入图片描述

#include "stdio.h"    
#include "stdlib.h"   #include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int *//* 链栈结构 */
typedef struct StackNode
{SElemType data;struct StackNode *next;
}StackNode,*LinkStackPtr;typedef struct
{LinkStackPtr top;int count;
}LinkStack;Status visit(SElemType c)
{printf("%d ",c);return OK;
}/*  构造一个空栈S */
Status InitStack(LinkStack *S)
{ S->top = (LinkStackPtr)malloc(sizeof(StackNode));if(!S->top)return ERROR;S->top=NULL;S->count=0;return OK;
}/* 把S置为空栈 */
Status ClearStack(LinkStack *S)
{ LinkStackPtr p,q;p=S->top;while(p){  q=p;p=p->next;free(q);} S->count=0;return OK;
}/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
Status StackEmpty(LinkStack S)
{ if (S.count==0)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数,即栈的长度 */
int StackLength(LinkStack S)
{ return S.count;
}/* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
Status GetTop(LinkStack S,SElemType *e)
{if (S.top==NULL)return ERROR;else*e=S.top->data;return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); s->data=e; s->next=S->top;	/* 把当前的栈顶元素赋值给新结点的直接后继,见图中① */S->top=s;         /* 将新的结点s赋值给栈顶指针,见图中② */S->count++;return OK;
}/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{ LinkStackPtr p;if(StackEmpty(*S))return ERROR;*e=S->top->data;p=S->top;					/* 将栈顶结点赋值给p,见图中③ */S->top=S->top->next;    /* 使得栈顶指针下移一位,指向后一结点,见图中④ */free(p);                    /* 释放结点p */        S->count--;return OK;
}Status StackTraverse(LinkStack S)
{LinkStackPtr p;p=S.top;while(p){visit(p->data);p=p->next;}printf("\n");return OK;
}int main()
{int j;LinkStack s;int e;if(InitStack(&s)==OK)for(j=1;j<=10;j++)Push(&s,j);printf("栈中元素依次为:");StackTraverse(s);Pop(&s,&e);printf("弹出的栈顶元素 e=%d\n",e);printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));GetTop(s,&e);printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));ClearStack(&s);printf("清空栈后,栈空否:%d(1:空 0:否)\n",StackEmpty(s));return 0;
}

顺序栈与链栈对比

对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了—些内存开销,但对于栈的长度无限制。

所以它们的区别和线性表—样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈。反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

栈的作用

栈的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题核心。

而像线性表顺序存储结构用到的数组,因为要分散精力去考虑数组的下标增减等细节问题反而掩盖了问题的本质。

栈的应用——递归

斐波那契数列

在这里插入图片描述
在这里插入图片描述

#include "stdio.h"/* 斐波那契的递归函数 */
int Fbi(int i)  
{if( i < 2 )return i == 0 ? 0 : 1;  return Fbi(i - 1) + Fbi(i - 2);  /* 这里Fbi就是函数自己,等于在调用自己 */
}  int main()
{int i;int a[40];  printf("迭代显示斐波那契数列:\n");a[0]=0;a[1]=1;printf("%d ",a[0]);  printf("%d ",a[1]);  for(i = 2;i < 40;i++)  { a[i] = a[i-1] + a[i-2];  printf("%d ",a[i]);  } printf("\n");printf("递归显示斐波那契数列:\n");for(i = 0;i < 40;i++)  printf("%d ", Fbi(i));  return 0;
}

迭代和递归的区别是:迭代使用的是循环结构,递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本,会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

递归过程退回的顺序是它前行顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复在前行过程中存储起来的某些数据。

这种存储某些数据,并在后面又以存储的逆序恢复这些数据,以提供之后使用的需求,显然很符台栈这样的数据结构,因此,编译器使用栈实现递归就没什么好惊讶的了。

简单地说,就是在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

当然,对于现在的高级语言,这样的递归问题是不需要用户来管理这个栈的,一切都由系统代劳了。

栈的应用—四则运算表达式求值

在这里插入图片描述
"9 3 1 -3 *+10 2/+”,这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/87854.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

yo!这里是STL::list类简单模拟实现

目录 前言 重要接口实现 框架 默认成员函数 迭代器&#xff08;重点&#xff09; 1.引言 2.list迭代器类实现 3.list类中调用实现 增删查改 后记 前言 我们知道&#xff0c;stl中的vector对应数据结构中的顺序表&#xff0c;string类对应字符串&#xff0c;而今天要…

vue3 excel 导出功能

1.安装 xlsx 库 npm install xlsx2.创建导出函数 src/utils/excelUtils.js import * as XLSX from xlsx;const exportToExcel (fileName, datas, sheetNames) > {// 创建工作簿const wb XLSX.utils.book_new()for (let i 0; i < datas.length; i) {let data datas…

【腾讯云 Cloud Studio 实战训练营】使用 Cloud Studio 快速构建 Vue + Vite 完成律师 H5 页面

【腾讯云 Cloud Studio 实战训练营】使用 Cloud Studio 快速构建 Vue Vite 完成律师 H5 页面 前言一、基本介绍1.应用场景2.产品优势 二、准备工作1.注册 Cloud Studio2.进入 Vue 预置开发环境 三、使用 Cloud Studio 快速构建 Vue Vite 完成律师 H5 页面1.安装相关依赖包2.主…

Spring Boot2.xx开启监控 Actuator

spring boot actuator介绍 Spring Boot包含许多其他功能&#xff0c;可帮助您在将应用程序推送到生产环境时监视和管理应用程序。 您可以选择使用HTTP端点或JMX来管理和监视应用程序。 审核&#xff0c;运行状况和指标收集也可以自动应用于您的应用程序。 总之Spring Boot Ac…

【Transformer】自注意力机制Self-Attention | 各种网络归一化Normalization

1. Transformer 由来 & 特点 1.1 从NLP领域内诞生 "Transformer"是一种深度学习模型&#xff0c;首次在"Attention is All You Need"这篇论文中被提出&#xff0c;已经成为自然语言处理&#xff08;NLP&#xff09;领域的重要基石。这是因为Transfor…

【APITable】教程:创建并运行一个自建小程序

1.进入APITable&#xff0c;在想要创建小程序的看板页面点击右上角的【小程序】&#xff0c;进入小程序编辑页面。 2.创建一个新的小程序区。 点击【 添加小程序】 点击创建小程序&#xff0c;选择模板&#xff0c;输入名字。 3.确定后进入小程序部署引导页面。 4.打开Xshell 7…

201、仿真-基于51单片机PT100测温设计铂电阻温度计设计Proteus仿真(程序+Proteus仿真+原理图+流程图+元器件清单+配套资料等)

毕设帮助、开题指导、技术解答(有偿)见文未 目录 一、设计功能 二、Proteus仿真图 三、原理图 四、程序源码 资料包括&#xff1a; 方案选择 单片机的选择 方案一&#xff1a;STM32系列单片机控制&#xff0c;该型号单片机为LQFP44封装&#xff0c;内部资源足够用于本次设…

【vue+el-table+el-backtop】表格结合返回顶部使用,loading局部加载

效果图: 一. 表格结合返回顶部 二. 局部loading 解决方法: 一 返回顶部 target绑定滚动dom的父元素类名就可以了. 1.如果你的表格是 固定表头 的,那滚动dom的父元素类名就是 el-table__body-wrapper <el-backtop target".el-table__body-wrapper" :visibility…

项目介绍:《WeTalk》网页聊天室 — Spring Boot、MyBatis、MySQL和WebSocket的奇妙融合

目录 引言&#xff1a; 前言&#xff1a; 技术栈&#xff1a; 主要功能&#xff1a; 功能详解&#xff1a; 1. 用户注册与登录&#xff1a; 2. 添加好友 3. 实时聊天 4. 消息未读 5. 删除聊天记录 6. 删除好友 未来展望&#xff1a; 项目地址&#xff1a; 结语&am…

zookeeperAPI操作与写数据原理

要执行API操作需要在idea中创建maven项目 &#xff08;改成自己的阿里仓库&#xff09;导入特定依赖 添加日志文件 上边操作做成后就可以进行一些API的实现了 目录 导入maven依赖&#xff1a; 创建日志文件&#xff1a; 创建API客户端&#xff1a; &#xff08;1&#xff09…

阿里云服务器安装部署Docker使用教程

本文阿里云百科分享如何在云服务ECS实例上&#xff0c;部署并使用Docker。Docker是一款开源的应用容器引擎&#xff0c;具有可移植性、可扩展性、高安全性和可管理性等优势。开发者可将应用程序和依赖项打包到一个可移植的容器中&#xff0c;快速发布到Linux机器上并实现虚拟化…

学习51单片机怎么开始?

学习的过程不总是先打好基础&#xff0c;然后再盖上层建筑&#xff0c;尤其是实践性的、工程性很强的东西。如果你一定要先全面打好基础&#xff0c;再学习单片机&#xff0c;我觉得你一定学不好&#xff0c;因为你的基础永远打不好&#xff0c;因为基础太庞大了&#xff0c;基…

许多智能算法并不智能(续)

许多智能算法被认为并不智能&#xff0c;主要是因为它们在某些方面仍然存在一些限制。以下是一些常见的原因&#xff1a; 缺乏常识和理解能力&#xff1a;当前的智能算法主要依赖于大量的数据和模式识别来做出决策&#xff0c;但它们通常缺乏对世界的常识和深层理解。这意味着它…

Android界面设计与用户体验

Android界面设计与用户体验 1. 引言 在如今竞争激烈的移动应用市场&#xff0c;提供优秀的用户体验成为了应用开发的关键要素。无论应用功能多么强大&#xff0c;如果用户界面设计不合理&#xff0c;用户体验不佳&#xff0c;很可能会导致用户流失。因此&#xff0c;在Androi…

数据驱动与关键字驱动

初次接触自动化测试时&#xff0c;对数据驱动和关键字驱动不甚理解&#xff0c;觉得有点故弄玄须&#xff0c;不就是参数和函数其嘛&#xff01;其实其也体现了测试所不同与开发的一些特点&#xff08;主要指系统测试&#xff09;&#xff0c;以及和对技术发展的脉络的展现。 …

【TypeScript】this指向,this内置组件

this类型 TypeScript可推导的this类型函数中this默认类型对象中的函数中的this明确this指向 怎么指定this类型 this相关的内置工具类型转换ThisParameterType<>ThisParameterType<>ThisType TypeScript可推导的this类型 函数中this默认类型 对象中的函数中的this…

在CMamke生成的VS项目中插入程序

在主文件夹的CMakeLists.tex中加入SET(COMPILE_WITH_LSVM OFF CACHE BOOL "Compile with LSVM") 再添加IF(COMPILE_WITH_LSVM) MESSAGE("Compiling with: LSVM") ADD_DEFINITIONS(-DCOMPILE_WITH_LSVM) ADD_SUBDIRECTORY(LSVM) LIST(APPEND SRC LSVM_wrap…

MFC第三十天 通过CToolBar类开发文字工具栏和工具箱、GDI+边框填充以及基本图形的绘制方法、图形绘制过程的反色线模型和实色模型

文章目录 CControlBar通过CToolBar类开发文字工具栏和工具箱CMainFrame.hCAppCMainFrm.cppCMainView.hCMainView.cppCEllipse.hCEllipse.cppCLine.hCLine.cppCRRect .hCRRect .cpp CControlBar class AFX_NOVTABLE CControlBar : public CWnd{DECLARE_DYNAMIC(CControlBar)pro…

运营商二要素认证API接口:提供手机号实名验证服务,确保用户信息的真实性

随着互联网的快速发展&#xff0c;各行各业都需要用户进行实名认证。其中&#xff0c;涉及到用户个人信息的场景&#xff0c;如电商、游戏、直播、金融等需要用户实名认证的场景&#xff0c;必须要进行实名认证。然而&#xff0c;对于这些场景&#xff0c;用户的个人信息的真实…

使用Git进行项目版本控制

文章目录 1、什么是Git&#xff1f;2、安装Git3、Git汉化3.1 Git Bash汉化3.2 Git GUI汉化(了解) 4、快速上手Git基本命令5、Git是怎么运作的&#xff1f;6、工作区、暂存区、本地仓库、远程仓库的区别6.1 工作区6.2 暂存区6.3 本地仓库6.4 远程仓库6.4 总结 7、 Git具体工作流…