精华内容
下载资源
问答
  • 共享栈

    2020-08-03 19:28:26
    一 概述 利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。...共享栈是为了更有效地利用存储空间,两个栈的空间相...

    一 概述

    利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。

    二 共享栈

                   

    如图所示,两个栈的栈顶指针都指向栈顶元素,top0=-1的时候0号栈为空,top1=MaxSize时1号栈为空;仅当两个栈顶指针相邻(top1-top0=1)时,判断为栈满。当0号栈进栈时top0先加1再赋值,1号栈进栈时top1先减1再赋值;出栈时则刚好相反。

    共享栈是为了更有效地利用存储空间,两个栈的空间相互调节,只有在整个存储空间被占满时才发生溢出。其存取数据的时间复杂度均为O(1),所以对存取效率没有什么影响。

    三 共享栈的实现

    #include<stdio.h>
    
    typedef int ElemType;
    
    /*定义共享栈*/
    #define MaxSize 10
    typedef struct{
    	ElemType data[MaxSize];
    	ElemType top0;
    	ElemType top1;
    }SharedStack;
    
    /*初始化*/
    void InitStack(SharedStack &S){
    	S.top0 = -1;			//初始化栈顶指针
    	S.top1 = MaxSize;
    }
    
    /*判空*/
    bool StackEmpty(SharedStack &S){
    	if(S.top0 == -1 && S.top1 == MaxSize)
    		return true;
    	else
    		return false;
    }
    
    /*入0号栈*/
    bool PushStack0(SharedStack &S,ElemType x){
    	if(S.top0+1 == S.top1)
    		return false;			//判断栈满
    	else
    		S.data[++S.top0] = x;	//指针加1,再入栈
    	return true;
    }
    
    /*入1号栈*/
    bool PushStack1(SharedStack &S,ElemType x){
    	if(S.top0+1 == S.top1)
    		return -1;			//判断栈满
    	else
    		S.data[--S.top1] = x;	//指针减1,再入栈
    	return true;
    }
    
    int PopStack(ElemType x){
    	
    	return x;
    } 
    
    int main(){
    	
    	SharedStack S;
    	InitStack(S);
    	ElemType x;
    	
    	for(int i = 1; i <= MaxSize/2; i++){
    		PushStack0(S,i);
    		PushStack1(S,MaxSize-i+1);
    	}
    	
    	printf("top_Stack0:");
    	for(int i = 0; i < MaxSize/2; i++) {
    		
    		printf("%d ",PopStack(S.data[S.top0-i]));
    	}
    	printf("\ntop_Stack1:");
    	for(int i = 0; i < MaxSize/2; i++) {
    	
    		printf("%d ",PopStack(S.data[S.top1+i]));
    	}
    	
    	return 0;
    }

    代码结果:

     

    展开全文
  • 一文搞懂共享栈

    千次阅读 多人点赞 2020-04-18 16:17:14
    共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间; 两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。 忘记栈的...


    共享栈的概念

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

    忘记栈的概念的朋友可以回顾一下

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

    共享栈的实现

    在这里插入图片描述

    • 这里为什么用int top[2]={-1,maxsize};而不用int top1=-1,top2=maxSize;呢?

    为了体现这两个栈底指针是属于一个共享栈的,我们习惯于用一个长度为2的数组表示它们,这样显得代码的可读性更强一点。

    • 什么时候为栈空状态呢?

    在这里插入图片描述

    • 共享栈怎么入栈呢?

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

    • 什么时候栈满呢?
      两个栈顶指针重合时,表示共享栈已经满了
      在这里插入图片描述

    用两个栈模拟队列

    在这里插入图片描述
    注意栈和队列的本质区别:栈先进后出,队列先进先出。因此务必要注意下图的规则:
    在这里插入图片描述
    注意:如果要把栈S1的元素导入到栈S2,必须一次性全部导入,不然就会出错。

    基本操作我们分为:初始化栈、入栈、出栈、取栈顶元素,具体实现代码如下:(此处参考)

     #include<stdio.h>                                                           
     #define SharedStackMax 100
     typedef char SharedStackType;
     typedef struct SharedStack{
         SharedStackType data[SharedStackMax];
         size_t top1;
         size_t top2;
     }SharedStack;
     
     void SharedStackInit(SharedStack*stack)
     {
         if(stack==NULL)
         {
             return;
         }
         stack->top1=0;
         stack->top2=SharedStackMax;
     }
     void SharedStackPush1(SharedStack*stack,SharedStackType value)
     {
         if(stack==NULL)
         {
             return;
         }
         if(stack->top1==stack->top2)
         {
             return;
         }
         stack->data[stack->top1++]=value;
         return;
     }
     void SharedStackPush2(SharedStack*stack,SharedStackType value)
     {
         if(stack==NULL)
         {
             return;
         }
         if(stack->top2==stack->top1)
         {
             return;
         }                                                                       
         stack->data[--stack->top2]=value;
     }
     int  SharedStackTop1(SharedStack*stack,SharedStackType*value)
     {
         if(stack==NULL||value==NULL)
         {
             return 0;
         }
         if(stack->top1==0)
         {
             return 0;
         }
         *value=stack->data[top1-1];
         return 1;
     
     }
     int SharedStackTop2(SharedStack*stack,SharedStackType*value)
     {
         if(stack==NULL||value==NULL)
         {
             return 0;
         }
         if(stack->top2==SharedStackMax)                                         
         {
             return 0;
         }
         *value=stack->data[stack->top2];
         return 1;
    }
     void SharedStackPop1(SharedStack*stack)
     {
         if(stack==NULL)
         {
             return;
         }
         if(stack->top1==0)
         {
             return;
         }
         stack->top1--;
     }
     void SharedStackPop2(SharedStack*stack)
     {
         if(stack==NULL)
         {
             return;                                                             
         }
         if(stack->top2==SharedStackMax)
         {
             return;
         }
         stack->top2++;
     }     
    
    展开全文
  • 栈的顺序存储——共享栈

    千次阅读 2016-05-16 19:15:01
    :充分利用顺序栈单向延伸的特性,使用一个数组来存储两个,让 一个底为该数组的始端 , 另一个底为该数组的末端 ,每一个从自己的端点    向中间延伸 。 优点: 由于两个相向增长,...

    两栈共享空间:充分利用顺序栈单向延伸的特性,使用一个数组来存储两个栈,让一个栈的栈底为该数组的始端另一个栈的栈底为该数组的末端,每一个栈从自己的端点     向中间延伸

    优点:

    由于两个栈相向增长,这样浪费的空间救护减少,同时发生上衣的概率也会减少。

    缺点:

    只有当两个栈的空间需求有相反的关系时,这种方法才会奏效。

    当三个或三个以上的栈共享一个数组空间时,只有相向增长的栈才能互补余缺,而背向增长或同向增长的栈之间无法自动互补,所以必须对某些栈作整体的调整,这将 使问题变得复杂而且效果欠佳。


    代码:

    #include<iostream>
    
    using namespace std;
    
    const int MaxSize=100;
    
    class BothStack
    {
    private:
        int data[MaxSize];
        int top1,top2;
    public:
        BothStack(){top1=-1;top2=MaxSize;}
        BothStack(int a[],int n,int b[],int m);
        ~BothStack(){}
        void Push(int x,int i);
        int Pop(int i);
        int GetTop(int i);
        int Empty(int i);
        void PrintStack(int i);
    };
    
    BothStack::BothStack(int a[],int n,int b[],int m)
    {
        top1=-1;top2=MaxSize;
        if(n+m>MaxSize) throw "上溢";
    
        for(int i=0;i<n;i++)
        {
            data[++top1]=a[i];
        }
    
        for(int i=0;i<m;i++)
        {
            data[--top2]=b[i];
        }
    }
    void BothStack::Push(int x,int i)
    {
        if(top1==top2-1) throw "上溢";
        if(i==1) data[++top1]=x;
        if(i==2) data[--top2]=x;
    }
    
    int BothStack::Pop(int i)
    {
        if(i==1)
        {
            if(top1==-1) throw "下溢";
            return data[top1--];
        }
        if(i==2)
        {
            if(top2==MaxSize) throw "下溢";
            return data[top2++];
        }
    
    }
    
    int BothStack::GetTop(int i)
    {
        if(i==1)
        {
            if(top1==-1) throw "下溢";
            else return data[top1];
        }
        if(i==2)
        {
            if(top2==MaxSize) throw "下溢";
            else return data[top2];
        }
    }
    int BothStack::Empty(int i)
    {
        if(i==1)
        {
            if(top1==-1)
                return 1;
            else
                return 0;
        }
        if(i==2)
        {
            if(top2==MaxSize)
            return 1;
        else
            return 0;
        }
    }
    void BothStack::PrintStack(int i)
    {
        if(i==1)
        {
            int m=top1;
            while(m!=-1)
            {
                cout<<data[m--]<<" ";
            }
            cout<<endl;
        }
        if(i==2)
        {
            int n=top2;
            while(n!=MaxSize)
                cout<<data[n++]<<" ";
            cout<<endl;
        }
    }
    int main()
    {
        int a[5]={11,15,12,6,15};
        int b[3]={13,14,10};
        BothStack aa(a,5,b,3);
        aa.PrintStack(1);
        aa.PrintStack(2);
    
        aa.Push(1,1);
        aa.PrintStack(1);
        aa.Push(2,2);
        aa.Push(3,2);
        aa.PrintStack(2);
    
        cout<<aa.Empty(1)<<endl;
        cout<<aa.Empty(2)<<endl;
    
        cout<<aa.GetTop(1)<<endl;
        cout<<aa.GetTop(2)<<endl;
    
         cout<<aa.Pop(1)<<endl;
        aa.PrintStack(1);
        cout<<aa.Pop(2)<<endl;
        aa.PrintStack(2);
    
        return 0;
    }
    


    展开全文
  • 共享栈空间

    2013-05-05 21:02:58
    利用顺序栈单向延伸的特性,使用一个数组来存储两个,让一个底为该数组的始端,另一个底为该数组的末端,每个从各自的端点向中间延伸。
  • 共享栈和双端队列

    2020-08-03 13:12:45
    共享栈和双端队列 一、共享栈 相比于普通的顺序栈,共享栈主要是为了提高内存的利用率和...他们与两个栈共享存储空间的共享栈的不同指出是,两个栈的栈顶指针式向两端延伸的。由于双端队列允许在两端插入和删除元素,

    共享栈和双端队列

    一、共享栈

    相比于普通的顺序栈,共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计的。
    为了增加内存空间的利用率和减少溢出的可能性,当两个栈共享一篇连续的内存空间时,应将两栈的栈底分别设在这片内存空间的两端,这样当两个栈的栈顶在栈空间的某一位置相遇时,才产生上溢。

    二、双端队列

    双端队列是一种插入和删除操作在两端均可进行的线性表,可以把双端队列看成栈底连在一起的两个栈。他们与两个栈共享存储空间的共享栈的不同指出是,两个栈的栈顶指针式向两端延伸的。由于双端队列允许在两端插入和删除元素,因此需要设立两个指针,分别指向双端队列中两端的元素。
    允许在一端进行插入和删除(进队和出队),另一端只允许删除的双端队列称为输入受限的双端队列。
    允许在一端进行插入和删除,另一端只允许插入的双端队列称为输出受限的双端队列

    例1.设有一 个双端队列,元素进入该队列的顺序是1, 2, 3, 4.试分别求出满足下列条件的
    输出序列。
    (1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列。
    (2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列。
    (3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。
    在这里插入图片描述
    解答
    (1)先看输入受限的双端队列,假设end1端输入1,2,3,4,那么end2端的输出相当于队列的输出;1,2,3,4;而end1端的输出相当于栈的输出,n=4时,可以通过Catalan()仅通过end1端有14中输出序列,仅仅通过end1端不能得到的输出序列有4!-14=10种,它们是:

    1,4,2,32,4,1,3
    3,4,1,23,1,4,2
    3,1,2,44,3,1,2
    4,2,1,34,1,2,3
    4,1,3,24,2,1,3

    通过end1和end2端混合输出,可以输出着10种中的8种。其中,SL,XL分别代表end1端的进队和出队,XR代表end2端的出队
    通过end1和end2端的混合输出序列图如下
    在这里插入图片描述
    可以得出有两种是不可能通过受限的双端队列输出的,即4,2,1,3和4,2,3,1
    (2)假设end1端和end2端输入,还可以输出其中8种,假设SL代表end1端的输入,SR,XR代表end2端的输入和输出,则可能输出序列以及进队和出队序列如下图所示。
    在这里插入图片描述
    可得通过输出受限的双端队列不能输出的两种序列是:4,1,3,2和4,2,3,1
    (3)取如上(1)和(2)的交集可得既不能由输入受限的双端队列得到 ,也不能由输出受限的双端队列得到的输出序列是4,2,3,1

    综上得:
    能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列是4,1,3,2;能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列是4,2,1,3;
    既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是4,2,3,
    1。

    展开全文
  • C语言顺序栈:共享栈

    2020-05-13 13:35:03
    共享栈 个人理解:共享顺序栈栈就是普通顺序栈在存储数组的另一头加上第二个栈顶指针。从而能够更有效地利用存储空间。 而顺序栈与链栈的区别可以参考顺序表和链表的关系。 代码如下 #include<stdio.h> #...
  • 顺序存储共享栈本质上就是把一个数组两端分别当成一个栈,这两个栈共用一块存储空间。 #include <stdio.h> #include <stdlib.h> #define MaxSize 20 #define ElemType int typedef struct{ ...
  • 数据结构—共享栈

    2021-08-09 09:31:22
    共享栈是为了更有效地利用存储空间,两个栈的空间相互调节,只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1),所以对存取效率没有什么影响。 栈空条件:栈0空为top0==-1;栈1空为top==...
  • 【数据结构】-共享栈

    2020-07-24 20:00:50
    共享栈共享栈示意图1.头文件及类型定义2.共享栈类型定义3.函数声明4.基本操作4.1 初始化共享栈4.2 1号栈判空4.3 2号栈判空4.4 1号栈入栈4.5 2号栈入栈4.6 1号栈出栈4.7 2号栈出栈4.8 1号栈读取栈顶元素4.9 2号栈读取...
  • 数据结构——共享栈算法的栈满问题

    千次阅读 多人点赞 2018-07-15 03:13:21
    共享栈是为了有效的利用存储空间,两个栈的空间可以相互调节 二、共享栈的概念 因为栈底位置不变,所以让两个顺序栈共享一个数组空间,两个栈的栈底分别设置在两端,两个栈顶向数组中间延伸。   三、共享栈栈满...
  • 为了使栈的空间能充分利用,可以让多个栈共享一个足够大的连续存储空间,通过移动栈顶指针,从而使多个栈空间互相补充,存储空间得到有效利用,这就是共享栈的设计思想。   最常见的是两个栈的共享。栈的共享原理...
  • 共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间; 两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。 图示 ...
  • C/C++实现共享栈

    2021-06-19 17:11:43
    何为共享栈 两个栈共享一个存储空间。两个栈的指针分别为top1和top2。   基本功能 1.初始化共享栈 2.判断共享栈是否为空 3.栈1和栈2:进栈、出栈 4.获得栈1和栈2的栈顶元素   代码 #include <...
  • 前言 栈(Stack)是一种只允许在一端进行插入或删除...共享栈是让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。 相关知识: C++结构体 C++指针 C++...
  • 共享栈的定义以及基本操作

    千次阅读 2019-09-30 15:58:13
    1、共享栈:利用栈底...2、共享栈存储结构: #define stacklen 100 typedef struct{ char ch[stacklen]; int top1; //左边栈的栈顶 int top2; //右边栈的栈顶 }sharestack; 3、共享栈的初始化 Status I...
  • 【数据结构】共享栈

    2021-10-15 16:47:12
    共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间; 两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。 基本...
  • 1.共享栈 1.1共享栈的定义 共享栈其实就是两个栈,合起来,共享一个数组存数据。这样子的好处就是,两个栈同一个空间。当栈1的数据多,栈2数据比较少,就可以这样子共享,对空间的浪费就会减少。当栈1为空,top1 = -...
  • 数据结构c++顺序表实现栈(共享栈)前言一、什么为共享栈?二、实现代码总结 前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习...
  • 顺序栈,共享栈以及链栈的相关操作
  • 目录共享栈的定义为何使用共享栈栈满后记 共享栈的定义 简单说就是两栈共用一片连续内存空间。 (王道书定义:)共享栈就是让两个顺序栈(一片连续内存,栈就是顺序栈)共享一个一维数组空间,将两个栈的栈底设置在...
  • #include using namespace std; const int MAXSIZE = 20;.../* 两栈共享空间结构 */ typedef struct { SElemType data[MAXSIZE]; int top1; /* 1 栈顶指针 */ int top2; /* 2 栈顶指针 */ }SqDoubleSta
  • Java编写一个共享栈,两栈共享同一块儿存储空间
  • 本文为数据结构课程的第一篇实验报告,主要是用c++实现共享栈、循环队列和链栈,仅供参考学习(也没人看),如有错误望及时提出,我及时改正。 实验一:线性结构的实现 一、实验目的 实验目标: 验证C语言环境下,...
  • /* 共享栈 2018/8/4 利用栈底位置不对称性,可以让两个顺序栈共享一个一维数据空间, 将两个栈的栈底分别设置为共享空间的两端,两个栈顶向共享空间...共享栈为了更加有效的利用存储空间,同时只有整个存储空间...
  • 一个数组实现两个栈,就是共享栈的实现问题。从图中可以看出,数组的起始位置和终点位置分别为两个栈的栈底。 给一个数组,给出两个栈顶,再给一个数组的容量。废话不说,代码实现template class SharedStack { ...
  • 共享栈的原理及代码实现(C语言)

    千次阅读 2019-04-28 09:19:54
    共享栈是一种特殊的栈,由顺序存储结构实现。 其特点在于两个栈共享同一块存储空间。 可以参考下面这张示意图(莫嫌丑) 两个栈的栈底分别位于数组的两端,而栈顶位于中间的位置(由元素数量决定),在上图中栈一有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 172,302
精华内容 68,920
关键字:

共享栈存储