数据结构 - 共享栈

作者: 主教主

共享栈

共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间;
两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。

基本概念

栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的,对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时,称之为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的,对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时,称之为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。

共享栈示意图

image
image

第一个栈从数组头开始存储,第二个栈从数组尾开始,两个栈向中间拓展。
当top1+1 == top2或者top1 == top2-1时,即staock overflow!.
与普通栈一样,共享栈出栈入栈的时间复杂度仍为O(1).

实验报告

当一个应用程序中需要使用多少个栈时,为了提高空间的使用效率,要让多个栈共享空间,这样既能减少预分配的空间过多造成的浪费,又能降低发生栈上溢产生错误中断的可能性,如上图所示,仅当两个栈相遇才会发生上溢

一、问题描述(标题黑体小四)

实现共享栈

二、实验目的

实现共享栈

三、实验设计

1.逻辑结构

逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的存储无关,是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构,线性表是典型的线性结构;集合、树和图是典型的非线性结构。数据的逻辑结构分类见图1-1。

  • 集合结构中的数据元素之间除了 “同属于一个集合"的关系外,别无其他关系。
  • 线性结构结构中的数据元素之间只存在一对一的关系。
  • 树形结构结构中的数据元素之间存在一对多的关系。
  • 图状结构或网状结构结构中的数据元素之间存在多对多的关系。

栈是特殊的线性表,它的逻辑结构和线性表相同,只是起操作规则受到了限制,因此,又称它是操作受限的线性表。共享栈也是栈,故逻辑结构为线性结构。

2.存储结构

存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。数据的存储结构主要有:顺序存储、链式存储、索引存储和散列存储。

  • 顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里,元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取,每个元素占用最少的存储空间;缺点是只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。
  • 链接存储:不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象,充分利用所有存储单元;缺点是每个元素因存储指针而占用额外的存储空间,并且只能实现顺序存取。
  • 索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,索引项的一般形式是:(关键字,地址)。其优点是检索速度快;缺点是增加了附加的索引表,会占用较多的存储空间。另外,在增加和删除数据时要修改索引表,因而会花费较多的时间。
  • 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称为Hash存储。其优点是检索、增加和删除结点的操作都很快;缺点是如果散列函数不好可能出现元素存储单元的冲突,而解决冲突会增加时间和空间开销。

可以采用顺序表,也可以采用链式表。本次实验用顺序表实现。故本次为顺序存储。

/—变量的定义—/

typedef int Selemtype;
define Maxsize 100          //定义共享栈中元素的最大个数
define TURE 1;
define FALSE 0;

/—栈的顺序存储结构—/

typedef struct
{
    Selemtype data[Maxsize];    //栈的大小
    int top1;                   //第一个栈的栈顶
    int top2;                   //第二个栈的栈顶
}ShareStack;

3.算法设计思想

image

两个栈共享一个存储空间,top1栈在指向空间的左端,依次向右入栈同时top1++,top2栈在指定空间的右端,依次向左入栈同时top2–,
栈满,既

S1入栈:指针右移一个位置,即stack[++top[0]]=x;
S2入栈:指针左移一个位置,即stack[–top[0]]=x;

当top1-1 = top2时 栈满

4.输入、输出设计

输入:入栈(数字+栈序)
结束入栈操作(F)
输出:出栈(栈内存储变量值)

四、主要代码

/—初始化—/

int InitStack(ShareStack *s)
{

    s->top1 = 0;
    s->top2 = Maxsize-1;
    return TURE;
}

/—判断共享栈是否为空—/

int IsEmpty(ShareStack *s)
{
    if(s->top1==0 && s->top2==Maxsize-1)
    {
        return TURE;
    }
    return FALSE;
}

/—入栈操作—/

int pushSStack(ShareStack *s,Selemtype x,int stackNum)
{
    if(s->top1 == s->top2+1)
    {
        return FALSE;
    }
    switch(stackNum)
    {
        case 1:s->data[s->top1++] = x;break;
        case 2:s->data[s->top2--] = x;break;
    }
    return TURE;
}

/—出栈操作—/

int PopSStack(ShareStack *s,Selemtype *x,int stackNum)
{
    switch(stackNum)
    {
        case 1:
            {
                if(s->top1 == 0) return FALSE;
                *x = s->data[--s->top1];
            };break;
        case 2:
            {
                if(s->top2==Maxsize-1) return FALSE;
                *x = s->data[++s->top2];
            };break;

    }
    return TURE;
}

五、程序运行结果截图

image

六、遇到的问题和解决方法

问题:栈空输出临界重复输出数值
解决方法:利用if语句进行先判断后打印操作

完整代码

点击查看代码

include <stdio.h>
include <stdlib.h>
include "SStack.h"   //自定义头文件 内部有共享栈的定义初始化 出入栈 判断栈空等函数

int main(){
    ShareStack *s;
    s = (ShareStack *)malloc(sizeof(ShareStack));
    InitStack(s);
    int n;
    int SStackNum;
    char c;
    /*---判断栈空---*/
    if(IsEmpty(s))
        printf("栈空\n");
    else
        printf("栈不空\n");

    printf("入栈\n");
    while(!(c = getchar() == 'F') )
    {
        printf("输入入栈数字和栈序(末尾加F:退出):");
        scanf("%d %d",&n,&SStackNum);
        pushSStack(s,n,SStackNum);

    }
    printf("出栈\n");
        while(!(c = getchar() == 'F') )
    {
        printf("输入出栈序(末尾加F:退出):");
        scanf("%d",&SStackNum);
        if(PopSStack(s,&n,SStackNum))
        printf("%d\n",n);
        else
            break;
    }
    /*---判断栈空---*/
      if(IsEmpty(s))
        printf("栈空");
    else
        printf("栈不空");


}

原文创作:主教主

原文链接:https://www.cnblogs.com/zhujiaozhu/p/15408889.html

更多推荐

更多
  • Azure数据工程指南-二十四、数据治理的权限 创建 azure 预览帐户,探索 azure 预览,探索词汇表,浏览资产,以编程方式使用预览,摘要,管理凭证和访问,创建扫描, 许多组织需要建立数据治理流程、标准和方法,并且已经能够使用内部 SQL Server 工具(如 Master
    Apache CN

  • Azure数据工程指南-二十二、Synapse 分析工作区 创建 Synapse 分析工作区,使用 Spark 探索样本数据,用 SQL 查询数据,用 SQL 创建外部表,摘要, 微软 Azure 数据平台的众多新增功能已经围绕许多类似的产品及其在现代 Azure 数据平台中的用途产生了兴奋和困
    Apache CN

  • Azure数据工程指南-二十三、数据块中的机器学习 创建 MLflow 实验,安装 MLflow 库,创建笔记本,选择性测井,自动记录,摘要, 寻求利用机器学习(ML)和人工智能能力的组织和开发人员花费大量时间构建 ML 模型,并寻求一种方法来简化他们的机器学习开发生命周期,以跟踪实验,
    Apache CN

  • Azure数据工程指南-二十一、将 Apache Spark 的 GraphFrame API 用于图形分析 安装 JAR 库,加载新数据表,将数据加载到数据块笔记本中,用顶点和边构建一个图,查询图表,寻找有图案的图案,用 PageRank 发现重要性,探索入度和出度度量,摘要,进行广度优先搜索,查找连接的组件, 图形技术使用户能够以图形的形式
    Apache CN

  • Azure数据工程指南-20 二十、部署 SQL 数据库先决条件,创建 Visual Studio SQL 数据库项目,安装 Visual Studio GitHub 扩展,导入 AdventureWorks 数据库,连接到 GitHub Repo 源代码控制,将
    Apache CN

  • Azure数据工程指南-十九、部署数据工厂更改 先决条件,创建 DevOps 持续集成构建管道,创建 DevOps 持续部署发布渠道,验证部署的数据工厂资源,摘要,Azure PowerShell 任务停止触发器,ARM 模板部署任务,Azure PowerShell 任务启动触发器
    Apache CN

  • Azure数据工程指南-十八、用于 Cosmos DB 的 Azure Synapse 链接 创建一个 Azure Cosmos DB 帐户,启用 Azure Synapse 链接,创建一个 Cosmos DB 容器和数据库,将数据导入 Azure Cosmos DB,在 Azure Synapse Analytics 中创建
    Apache CN

  • Azure数据工程指南-十六、流分析异常检测 先决条件,创建流分析输入和输出,创建实时电源 BI 仪表板,监控实时电源 BI 流,摘要,创建 Azure 流分析作业,创建物联网中心,创建 Power BI 服务,下载设备模拟器,添加流输入,添加流输出,编写流分析查询,启动流分析作业
    Apache CN

  • Azure数据工程指南-十七、使用 Apache Spark 的实时物联网分析 先决条件,创建物联网中心,创建数据块集群,安装 Maven 库,创建笔记本并运行结构化流查询,摘要,配置笔记本连接,开始结构化流,启动物联网设备模拟器,显示实时流数据,创建 Spark SQL 表,将流写入增量表, 实时物联网分析、高级
    Apache CN

  • Azure数据工程指南-十五、DeltaLake 为什么是酸性 DeltaLake,先决条件,创建并插入 DeltaLake,更新 DeltaLake,从 DeltaLake 删除,浏览增量日志,摘要,插入,更新,删除, 在使用 Azure Data Lake Storage Gen2
    Apache CN

  • 近期文章

    更多
    文章目录

      推荐作者

      更多