首页 > 其他分享 >数据结构3——栈的顺序与链式存储

数据结构3——栈的顺序与链式存储

时间:2025-01-23 18:29:51浏览次数:3  
标签:存储 return ElemType next length bool 链式 数据结构 Stack

前言

经过前面对线性表的顺序存储结构和链式存储结构的熟悉,那么面对接下来栈的这两种存储结构也应该得心应手了。其实接下来的栈、队列、树、图结构都是基于线性表的顺序、链式存储结构构建的。

栈结构在网页跳转、游戏页面等场景中常用到,其“先进后出”“后进先出”的数据访问特点也使其在寻路问题中有一席之地。

1.认识栈

1.1栈

栈是一种特殊的线性表,只能在表的“端点”进行操作,即栈的插入、删除等操作只允许在线性表固定一端进行。

栈的几种状态:

进栈(入栈):把新的元素插入到顶端

出栈:获取顶端元素、并删除该元素

栈顶:允许插入、删除的一端称为栈顶(Top)

栈底:不能插入、删除的另一端称为栈底(Bottom)

空栈

 像下图,按A、B、C、D依次压栈得出图中结果,出栈顺序是D、C、B、A。

如果我按ABCD顺序压栈,但是不考虑出栈时机,我能得出多少种结果呢?

ABCD(压A出A,压B出B……)

DCBA(压完ABCD,才执行出栈)

BACD(压完AB出BA,压C出C,压D出D)

BDCA(压AB,出B,压CD,出DCA)

CDBA(压ABC,出C压D,出BA)

…………共14种

1.2栈的操作

InitStack(&S) 初始化一个空栈

DestroyStack(&S) 销毁一个栈

ClearStack(&S) 清空一个栈

StackEmpty(S) 判断栈是否为空

StackLength(S) 获取栈的长度

GetTop(S, &e) 获得栈顶元素

Pop(&S, &e) 出栈

Push(&S, e) 入栈

…………

2.栈的顺序存储

2.1操作原理

利用一组地址连续的存储单元(一维数组),依次存放从栈底到栈顶的数据元素,(简称“顺序栈”)。此外,还需要定义一个(栈顶)标记,表示它前面是有效元素。

 如果观察仔细的话,可以发现顺序栈的结构与线性表顺序存储结构无异,线性表的length属性可用作顺序栈的top以作为栈顶指针。

2.2代码

typedef int ElemType;
struct Stack{
ElemType *elem;
int length;//用长度作为栈顶指针
int volume;
};
//1.初始化栈
bool Init_Stack( Stack &S )
{
    if(!S.elem)    return false;
    S.elem=new ElemType[size];
    S.length=0;
    S.volume=size;
    return true;
}
//2.销毁栈
bool Destroy_Stack( Stack &S )
{
	delete S.elem;
	return true;
}
//3.清空栈
bool Clear_Stack( Stack &S )
{
    S.length=0;
    return true;
}
//4.判断栈是否为空
bool Stack_Empty( const Stack &S )
{
    return S.length==0;
}
//5.求栈长
int Stack_Length( const Stack &S )
{
	return S.length;
}
//6.取栈顶元素,返回栈顶元素
ElemType GetTop( const Stack &S )
{
	if(S.length==0)    return false;
	return S.elem[S.length-1];
}
//7.入栈
bool Push( Stack &S, ElemType e)
{
    if(S.length>=S.volume)
    {
        cout<<"栈满";
        return false;
    }
    S.elem[S.length]=e;
    ++S.length;
    return true;
}
//8.出栈
bool Pop( Stack &S, ElemType &e )
{
	if(S.length==0)    return false;
	e=S.elem[S.length-1];
	--S.length;
	return true;	
}

3.栈的链式存储 

3.1操作原理

就是线性表的链式存储,只不过插入和删除都在头部进行(头插法和头删法)。

3.2代

typedef int ElemType;
struct Stack{
ElemType data;
Stack *next;
};
typedef Stack* myStack;
//1.初始栈
bool InitStack(myStack &S)
{
	if(S)
	{
		cout<<"fail to init stack";
		return false;
	}
	S=new Stack;
	S->next=NULL;
	return true;
}
//2.销毁栈
bool DestroyStack(myStack &S)
{
    if(S->next!=NULL)
    {
        cout<<"请先执行清空表操作";
        return false;
    }
	delete S;
	return true;
}
//3.清空栈
bool ClearStack(myStack &S)
{
    Stack *p=S->next;
	Stack *del;
	while(p)
	{
		del=p;
		p=p->next;
		delete del;
	}
    return true;
}
//4.判断栈是否为空
bool StackEmpty(const myStack &S)
{
    if(S->next!=NULL)
        return false;
	cout<<"the stack is empty";
    return true;
}
//5.获取栈的长度
int StackLength(const myStack &S)
{
    int count=0;
	Stack *p=S;
	while(p->next)
	{
		p=p->next;
		++count;
	}
	return count;
}
//6.获得栈顶元素
bool GetTop(const myStack &S, ElemType &e)
{
    e=S->next->data;
    return true;
}
//7.出栈
bool Pop(myStack &S, ElemType &e)
{
    if(StackEmpty(S)==false)
    {
        e=S->next->data;
        Stack *del=S->next;
        S=S->next;
        //S->next=S->next;这话其实是多余的
        return true;
    }
    return false;
}
//8.入栈
bool Push(myStack &S, ElemType e)
{
    Stack *p=new Stack;
    p->data=e;
    p->next=S->next;
    S->next=p;
    return true;
}

标签:存储,return,ElemType,next,length,bool,链式,数据结构,Stack
From: https://blog.csdn.net/QiQi_sviper/article/details/145310879

相关文章

  • 记一次k8s集群挂载动态nfs存储故障
    环境查看系统环境#cat/etc/redhat-releaseCentOSLinuxrelease7.9.2009(Core)#uname-aLinuxCentOS7K8SNode0030683.10.0-1160.el7.x86_64#1SMPMonOct1916:18:59UTC2020x86_64x86_64x86_64GNU/Linux软件环境#kubectlgetnodeNAMESTA......
  • JAVA与数据结构-线性表
    目录一.线性表的概念二.线性表的关系及分类三.数组与顺序表四.链表1.静态链表(链表的的数组底层实现)2.循环链表3.双向链表五.栈1.栈的概念2.栈的底层实现3.共享空间栈4.逆波兰表达式(后缀表达式)5.栈与递归 六.队列1.队列概念2.队列的底层实现3.循环队列七.链......
  • 深入探讨存储过程的创建与应用:提高数据库管理效率的关键工具
    title:深入探讨存储过程的创建与应用:提高数据库管理效率的关键工具date:2025/1/23updated:2025/1/23author:cmdragonexcerpt:在数据驱动的商业环境中,数据库管理系统必须具备高效的操作能力。而存储过程作为一种封装的数据库逻辑,提供了一种有效的解决方案,以增强数据库......
  • 初步认识数据结构
    初步认识数据结构本文章可以帮助你初步的去认识数据结构1.什么是数据结构官方定义:在计算机科学中,数据结构是一种数据组织,管理和存储的格式。它是相互之间存在一种或者多种特定关系的数据元素集合。数据在计算机科学中,数据是所有能输入计算机并被计算机程序处理的符号的......
  • 如何利用openssl定义新的数据结构
        依赖openssl实现国密相关的结构时,虽然openssl中也有类似结构定义,但因为oid的差异、国密算法支持度不高等原因导致无法直接使用openssl接口,这时就需要自定义数据结构。实战:依据GMT0033定义时间戳响应//定义数据结构typedefstructSignerInfo_st{ASN1_INTEG......
  • NocoBase 本周更新汇总:改进文件存储扩展
    汇总一周产品更新日志,最新发布可以前往我们的博客查看。NocoBase目前更新包括的版本更新包括三个分支:main,next和develop。main:截止目前最稳定的版本,推荐安装此版本。next:包含即将发布的新功能,经过初步测试的版本,可能存在部分已知或未知问题。主要面向测试用户,用于收集反......
  • ChatGPT 摘要,以 ESS 作为你的私有数据存储
    作者:来自Elastic Ryan_Earle本教程介绍如何设置Elasticsearch网络爬虫,将网站索引到Elasticsearch中,然后利用ChatGPT使用我们的私人数据来总结对其提出的问题。Python脚本的GithubRepo:https://github.com/Gunnerva/elastic_chatgpt/目标:了解如何使用Elasticsea......
  • 记忆层增强的 Transformer 架构:通过可训练键值存储提升 LLM 性能的创新方法
    大语言模型(LLM)通过其参数储存了大量信息,这些信息主要以密集层中线性矩阵变换的权重形式存在。然而,参数规模的扩大必然导致计算成本和能源消耗的显著增加。这种参数存储方式是否可以通过更高效的键值查找机制来优化?尽管此前已有多项相关研究,但在当前AI架构规模下的实践尚属首次......
  • 【云平台】云平台存储主要路线比较分析:存储虚拟化、分布式存储、网络共享文件存储
    #信创#金融领域#云平台【摘要】随着金融数字化转型的推进和深入,大家在选择云架构时开始考虑的更长远、更谨慎。一方面会从企业级、集团级和行业级整体发展演进的眼光进行整体规划,避免出现云或资源池的孤岛林立:另一方面采用自主可控的信创云架构也成为众多金融企业的重要抉择......
  • MySQL存储过程和函数
    存储过程和函数函数与存储过程最大的区别就是函数调用有返回值,调用存储过程用call语句,而调用函数就直接引用函数名+参数即可创建存储过程和函数详解1234567891011121314151617181920212223242526272829303132333435363738394041......