数据结构【第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;
        else
                return 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;
        else
                return 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;
        else
                return 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/+”,这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【大数据】Flink 详解(二):核心篇 Ⅱ

Flink 详解&#xff08;二&#xff09;&#xff1a;核心篇 Ⅱ 22、刚才提到 State&#xff0c;那你简单说一下什么是 State。 在 Flink 中&#xff0c;状态 被称作 state&#xff0c;是用来保存中间的计算结果或者缓存数据。根据状态是否需要保存中间结果&#xff0c;分为 无状…

ADB连接安卓手机提示unauthorized

近期使用airtest进行自动化测试时&#xff0c;因为需要连接手机和电脑端&#xff0c;所以在使用adb去连接本人的安卓手机vivo z5时&#xff0c;发现一直提示unauthorized。后来经过一系列方法尝试&#xff0c;最终得以解决。 问题描述&#xff1a; 用数据线将手机接入电脑端&…

一个案例:Vue2组件化开发组件从入门到入土

1. 环境搭建 1.1. 创建项目 npm install -g vue/clivue create vue_study_todolist1.2. 清空项目代码 清楚HelloWorld.Vue代码中的内容。 1.3. 启动空项目 1.4 项目目标 项目组件实现以下效果 2. 组件拆分代码 Vue是一个基于组件的框架&#xff0c;允许您将界面拆分成小的…

任我行 CRM SQL注入漏洞复现(HW0day)

0x01 产品简介 任我行CRM&#xff08;Customer Relationship Management&#xff09;是一款专业的企业级CRM软件&#xff0c;旨在帮助企业有效管理客户关系、提升销售效率和提供个性化的客户服务。 0x02 漏洞概述 任我行 CRM SmsDataList 接口处存在SQL注入漏洞&#xff0c;未…

基于熵权法对Topsis模型的修正

由于层次分析法的最大缺点为&#xff1a;主观性太强&#xff0c;影响判断&#xff0c;对结果有很大影响&#xff0c;所以提出了熵权法修正。 变异程度方差/标准差。 如何度量信息量的大小&#xff1a; 把不可能的事情变成可能&#xff0c;这里面就有很多信息量。 概率越大&…

IC设计仿真云架构

对于IC仿真来说&#xff0c;最重要的是要安全、可维护、高性能的的HPC环境环境。 那么云上如何搭建起一套完整的IC仿真云环境呢&#xff1f; 这种架构应该长什么样子&#xff1f; 桌面虚拟化基础架构 将所有桌面虚拟机在数据中心进行托管并统一管理&#xff1b;同时用户能够…

HTML详解连载(5)

HTML详解连载&#xff08;5&#xff09; 专栏链接 [link](http://t.csdn.cn/xF0H3)下面进行专栏介绍 开始喽行高&#xff1a;设置多行文本的间距属性名属性值行高的测量方法 行高-垂直居中技巧 字体族属性名属性值示例扩展 font 复合属性使用场景复合属性示例注意 文本缩进属性…

挑战Open AI!!!马斯克宣布成立xAI.

北京时间7月13日凌晨&#xff0c;马斯克在Twitter上宣布&#xff1a;“xAI正式成立&#xff0c;去了解现实。”马斯克表示&#xff0c;推出xAI的原因是想要“了解宇宙的真实本质”。Ghat GPT横空出世已有半年&#xff0c;国内外“百模大战”愈演愈烈&#xff0c;AI大模型的现状…

Ajax-AJAX请求的不同发送方式

&#x1f954;&#xff1a;你一定能成为想要成为的人 发送AJAX请求不同方式 发送AJAX请求不同方式1、jQuery发送AJAX请求2、axios发送AJAX请求&#xff08;重点&#xff09;3、fetch发送AJAX请求 发送AJAX请求不同方式 1、jQuery发送AJAX请求 首先需要jquery的js文件&#xf…

集合Collection-List-ArrayList学习

一、集合 集合是数据容器。相较于数组集合具有以下几个特点&#xff1a; 数组一旦创建&#xff0c;长度不可改变。集合的长度会自动扩容。集合具有很多数组没有的功能函数API数组元素的存储特点单一&#xff0c;不同的集合有不同的存储特点。 1. Collection顶层接口 Collect…

用python来爬取某鱼的商品信息(2/2)

目录 上一篇文章 本章内容 设置浏览器为运行结束后不关闭&#xff08;可选&#xff09; 定位到搜索框的xpath地址 执行动作 获取cookie 保存为json文件 修改cookie的sameSite值并且导入cookie 导入cookie&#xff08;出错&#xff09; 导入cookie&#xff08;修改后&…

Jmeter(五) - 从入门到精通 - 创建网络计划实战和创建高级Web测试计划(详解教程)

1.简介 上一篇中已经将其的理论知识介绍了一下&#xff0c;这一篇就带着大家一步一步的把上一篇介绍的理论知识实践一下&#xff0c;然后再说一下如何创建高级web测试计划。 2.网络计划实战 通过上一篇的学习&#xff0c;将其分类为&#xff1a; &#xff08;1&#xff09;不需…

python -- 函数闭包

1. LEGB规则 L: local 是局部作用域 E: Enclosed 是嵌套函数的外层函数作用域 G: Global 全局作用域 B:Build-In 内置作用域 变量的使用权重&#xff1a;局部变量 > 外层作用域变量 > 全局变量 > 内置变量 下面代码执行后&#xff0c;x变量的值分别为多少&#xff1…

KafkaStream:Springboot中集成

1、在kafka-demo中创建配置类 配置kafka参数 package com.heima.kafkademo.config;import lombok.Data; import org.apache.kafka.common.serialization.Serdes; import org.apache.kafka.streams.StreamsConfig; import org.springframework.boot.context.properties.Configu…

怎么做Tik Tok海外娱乐公会呢?新加坡市场怎么样?

一、为什么选择TikTok直播 1. 海外市场潜力巨大 • 自2016年始&#xff0c;多家直播平台陆续拓展至东南亚、中东、俄罗斯、日韩、欧美、拉美等地区。 • 海外市场作为直播发展新蓝海&#xff0c;2021年直播行业整申请cmxyci体规模达百亿美元&#xff0c;并维持高速增长。 &a…

【数据结构系列】链表

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…

异常(下)Java常见异常,异常的使用原则

文章目录 前言一、Java常见异常 1.常见异常2.实例展示二、异常的使用原则总结 前言 该文介绍了Java的一些常见异常&#xff0c;并给出对应的例子进行解释。介绍异常的使用原则&#xff0c;即创建&#xff0c;抛出异常的编程规范。 一、Java常见异常 前要&#xff1a;Java API中…

sklearn机器学习库(一)sklearn中的决策树

sklearn机器学习库(一)sklearn中的决策树 sklearn中决策树的类都在”tree“这个模块之下。 tree.DecisionTreeClassifier分类树tree.DecisionTreeRegressor回归树tree.export_graphviz将生成的决策树导出为DOT格式&#xff0c;画图专用tree.export_text以文字形式输出树tree.…

Jmeter(六) - 从入门到精通 - 建立数据库测试计划(详解教程)

1.简介 在实际工作中&#xff0c;我们经常会听到数据库的性能和稳定性等等&#xff0c;这些有时候也需要测试工程师去评估和测试&#xff0c;因此这篇文章主要介绍了jmeter连接和创建数据库测试计划的过程,在文中通过示例和代码非常详细地介绍给大家&#xff0c;希望对各位小伙…

基于YOLOv8+PyQt5开发的行人过马路危险行为检测告警系统(附数据集和源码下载)

系列文章目录 文章目录 系列文章目录前言欢迎来到我的博客&#xff01;我很高兴能与大家分享关于基于YOLOv8的行人过马路危险行为检测告警系统的内容。 一、系统特点1. 采用最新最优秀的目标检测算法YOLOv82. 系统分别基于PyQt5开发了两种GUI图形界面&#xff0c;供大家学习使用…