精华内容
下载资源
问答
  • windows下协程实现(fiber、汇编、非共享栈共享栈)
  • 共享栈

    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;
    }

    代码结果:

     

    展开全文
  • 数据结构(C语言版)——共享栈(代码版),里面是C文件和exe文件。其中包含的操作有1:初始化共享栈2:向共享栈中插入元素3:当前共享栈元素个数
  • 数据结构---栈和队列之共享栈(C语言)完整代码,可以运行
  • 根据栈和队列的抽象数据类型的定义,按要求实现一个栈或一个队列。 要求: 1、 实现一个共享栈 2、 实现一个链栈 3、 实现一个循环队列 4、 实现一个链队列
  • 一文搞懂共享栈

    千次阅读 多人点赞 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++;
     }     
    
    展开全文
  • 【数据结构】-共享栈

    千次阅读 多人点赞 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号栈读取...

    共享栈示意图

    共享栈

    1.头文件及类型定义

    #include<stdio.h>
    #define MaxSize 10				//定义共享栈中元素的最大个数
    #define ElemType int			
    

    2.共享栈类型定义

    typedef struct {
    	ElemType data[MaxSize];		//静态数组存放栈中元素
    	int top1;					//1号栈栈顶指针
    	int top2;					//2号栈栈顶指针
    }ShStack;
    

    3.函数声明

    /*函数声明*/
    void InitShStack(ShStack& S);				//1.初始化共享栈
    bool Stack1Empty(ShStack S);				//2. 1号栈判空
    bool Stack2Empty(ShStack S);				//2. 2号栈判空
    bool Push1(ShStack& S, ElemType x);			//3. 1号栈入栈
    bool Push2(ShStack& S, ElemType x);			//4. 2号栈入栈
    bool Pop1(ShStack& S, ElemType& x);			//5. 1号栈出栈
    bool Pop2(ShStack& S, ElemType& x);			//6. 2号栈出栈
    bool GetTop1(ShStack S, ElemType& x);		//7. 1号栈读取栈顶元素
    bool GetTop2(ShStack S, ElemType& x);		//8. 2号栈读取栈顶元素
    

    4.基本操作

    4.1 初始化共享栈

    //1.初始化共享栈
    void InitShStack(ShStack& S) {
    	S.top1 = -1;		//初始化1号栈栈顶指针
    	S.top2 = MaxSize;	//初始化2号栈栈顶指针
    }
    

    4.2 1号栈判空

    //2. 1号栈判空
    bool Stack1Empty(ShStack S) {
    	return (S.top1 == -1);
    }
    

    4.3 2号栈判空

    //2. 2号栈判空
    bool Stack2Empty(ShStack S) {
    	return (S.top2 == MaxSize);
    }
    

    4.4 1号栈入栈

    //4. 1号栈入栈操作:新元素入栈(先存再加)
    bool Push1(ShStack& S, ElemType x) {
    	if (S.top1+1 == S.top2)		//栈满,报错
    		return false;
    	S.data[++S.top1] = x;
    	return true;
    }
    

    4.5 2号栈入栈

    //5. 2号栈入栈操作:新元素入栈(先存再加)
    bool Push2(ShStack& S, ElemType x) {
    	if (S.top1 + 1 == S.top2)		//栈满,报错
    		return false;
    	S.data[--S.top2] = x;
    	return true;
    }
    

    4.6 1号栈出栈

    //6. 1号栈出栈操作:栈顶元素出栈
    bool Pop1(ShStack& S, ElemType& x) {
    	if (S.top1 == -1)	//1号栈栈空,报错
    		return false;
    	x = S.data[S.top1--];	
    	return true;
    }
    

    4.7 2号栈出栈

    //7. 2号栈出栈操作:栈顶元素出栈
    bool Pop2(ShStack& S, ElemType& x) {
    	if (S.top2 == MaxSize)	//2号栈栈空,报错
    		return false;	
    	x = S.data[S.top2++];
    	return true;
    }
    

    4.8 1号栈读取栈顶元素

    //8. 1号栈读取栈顶元素操作
    bool GetTop1(ShStack S, ElemType& x) {
    	if (S.top1 == -1)	//1号栈栈空,报错
    		return false;
    	x = S.data[S.top1];
    	return true;
    }
    

    4.9 2号栈读取栈顶元素

    //9. 2号栈读取栈顶元素操作
    bool GetTop2(ShStack S, ElemType& x) {
    	if (S.top2 == MaxSize)	//2号栈栈空,报错
    		return false;
    	x = S.data[S.top2];
    	return true;
    }
    

    4.10 main函数

    int main() {
    	ShStack S;		//声明一个共享栈(分配内存空间)
    
    	/*1、初始化共享栈*/
    	InitShStack(S);
    
    	/*2、1号栈-判空*/
    	if (Stack1Empty(S))
    		printf("当前1号栈空!\n");
    	else
    		printf("当前1号栈非空!\n");
    
    	/*3、1号栈-入栈操作*/
    	ElemType e1;
    	printf("请输入1号栈入栈元素的值:");
    	scanf("%d", &e1);
    	if (Push1(S, e1))
    		printf("1号栈新元素入栈成功!\n");
    	else
    		printf("共享栈已满,1号栈新元素入栈失败!\n");
    
    	/*4、1号栈-读取栈顶元素*/
    	ElemType e2 = -1;
    	if (GetTop1(S, e2))
    		printf("1号栈读取栈顶元素成功,当前栈顶元素值为:%d\n", e2);
    	else
    		printf("1号栈已空,读取栈顶元素失败!\n");
    
    	/*5、1号栈-出栈操作*/
    	ElemType e3 = -1;
    	if (Pop1(S, e3))
    		printf("1号栈栈顶元素出栈成功,出栈元素值为:%d\n", e3);
    	else
    		printf("1号栈已空,栈顶元素出栈失败!\n");
    
    	/*6、1号栈-读取栈顶元素*/
    	ElemType e4 = -1;
    	if (GetTop1(S, e4))
    		printf("1号栈读取栈顶元素成功,当前栈顶元素值为:%d\n", e4);
    	else
    		printf("1号栈已空,读取栈顶元素失败!\n");
    
    	/*7、2号栈-判空*/
    	if (Stack2Empty(S))
    		printf("当前2号栈空!\n");
    	else
    		printf("当前2号栈非空!\n");
    
    	/*8、2号栈-入栈操作*/
    	ElemType e21;
    	printf("请输入2号栈入栈元素的值:");
    	scanf("%d", &e21);
    	if (Push2(S, e21))
    		printf("2号栈新元素入栈成功!\n");
    	else
    		printf("共享栈已满,2号栈新元素入栈失败!\n");
    
    	/*9、2号栈-读取栈顶元素*/
    	ElemType e22 = -1;
    	if (GetTop2(S, e22))
    		printf("2号栈读取栈顶元素成功,当前栈顶元素值为:%d\n", e22);
    	else
    		printf("2号栈已空,读取栈顶元素失败!\n");
    
    	/*10、2号栈-出栈操作*/
    	ElemType e23 = -1;
    	if (Pop2(S, e23))
    		printf("2号栈栈顶元素出栈成功,出栈元素值为:%d\n", e23);
    	else
    		printf("2号栈已空,栈顶元素出栈失败!\n");
    
    	/*11、2号栈-读取栈顶元素*/
    	ElemType e24 = -1;
    	if (GetTop2(S, e24))
    		printf("2号栈读取栈顶元素成功,当前栈顶元素值为:%d\n", e24);
    	else
    		printf("2号栈已空,读取栈顶元素失败!\n");
    	return 0;
    }
    

    5.小结

    1. 共享栈的定义
      共享栈是逻辑上实现了两个栈,但物理上这两个栈共享同一片内存空间。因此在进行判空操作时,两个栈分别进行判断,但在判满时要判断整个共享栈的存储情况。
    2. 说明
      共享栈的实现与顺序栈的实现大同小异,它们都属于栈的顺序存储,只需要注意在栈顶指针处别犯错就可以。
    展开全文
  • 共享栈的使用,出栈,入栈等操作,判断栈是否为空
  • 共享栈语言实现

    2015-10-05 15:21:39
    共享栈语言实现
  • 目录共享栈的定义为何使用共享栈栈满后记 共享栈的定义 简单说就是两栈共用一片连续内存空间。 (王道书定义:)共享栈就是让两个顺序栈(一片连续内存,栈就是顺序栈)共享一个一维数组空间,将两个栈的栈底设置在...

    共享栈的定义

    简单说就是两栈共用一片连续内存空间
    (王道书定义:)共享栈就是让两个顺序栈(一片连续内存,栈就是顺序栈)共享一个一维数组空间,将两个栈的栈底设置在共享空间的两端, 两个栈顶向共享空间的中间延伸。 如图所示(再嫖张王道书的图):

    为何使用共享栈

    首先介绍一下上溢和下溢,对栈而言:栈满还存为上溢,栈空再取即下溢。上溢和下溢都修改了栈之外的内存,因此有可能导致程序崩溃。

    那有人就会说,那我给每个栈都分配足够大的空间就能解决上溢了吧?
    这么说确实有道理,但是却有以下的问题:
    ①给每个栈都分配足够大的空间不太现实
    ②栈内的数据在不断的变化,而一个栈只存储的一点数据的话,这样不就造成空间利用率过低

    共享栈就是因此而生的,由上面共享栈的定义可以知道它能使两个栈的空间可以相互调节(因为是共用嘛),从而更有效地利用存储空间。只有当两栈栈顶相遇(即栈满,若不清楚栈满往下看)时,存储空间被用尽,之后再进栈才会产生上溢。

    由于栈往往不止一个,如果通过给每个栈分配很大的空间来解决上溢,造成的是存储空间的浪费,因此采用共享栈能在保证节省存储空间的基础上,在一定程度上减少上溢。(直白点的解释就是一个栈数据多,一个栈数据少,我本来一个栈存不下那么多的数据,我通过空间共用的方法,把你没用到的空间用来存我的数据,既提高了空间利用率,又让我不上溢。再配张一个老哥不知道哪找的图:)

    在这里插入图片描述

    所以说某道题:采用共享栈的好处是( )” 答案为:节省存储空间,降低发生上溢的可能


    栈满

    举个例子描述一下栈满,对于栈底指针设为 top0= -1,top1=Maxsize这种情况,需要先移动指针再赋值,假设Maxsize=5。

    在这里插入图片描述

    从上述例子可以看出,栈满条件为top1-top0=1,即两栈顶指针相邻
    栈满之后,如果再有push操作,就会发生上溢。


    后记

    ①参考了很多网上零零碎碎的东西总结出来的,王道书上讲的也稀碎。
    ②文中有一张图源自 这个老哥

    展开全文
  • 本文为数据结构课程的第一篇实验报告,主要是用c++实现共享栈、循环队列和链栈,仅供参考学习(也没人看),如有错误望及时提出,我及时改正。 实验一:线性结构的实现 一、实验目的 实验目标: 验证C语言环境下,...
  • //共享栈的结构体定义 typedef struct{ int elem[maxsize]; int top[2];//top[0]为s0栈顶 top[1]为s1栈顶 }SqStack; //入栈 int push(SqStack &amp;st,int stNo,int x) { if(st.top[0]+1&lt;st.top[1])...
  • 共享栈和双端队列

    2020-08-03 13:12:45
    共享栈和双端队列 一、共享栈 相比于普通的顺序栈,共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计的。 为了增加内存空间的利用率和减少溢出的可能性,当两个栈共享一篇连续的内存空间时,应将两栈的栈...
  • 共享栈的定义及基本操作的代码实现 所用编译器:Visual Studio Code 1.42.1 C++环境 #include <stdio.h> #define MaxSize 15 //定义int别名为ElemType typedef int ElemType; //栈的数据结构表示 typedef ...
  • 共享栈的基本操作-C语言

    千次阅读 2018-12-22 17:54:51
    共享栈的基本操作 共享栈是用顺序表实现, 在两端分别设置为栈底, 并且分别初始化栈顶, 实现可以在两端进行入栈和出栈操作, 并且互不干扰, 模拟分工成两个栈, 当两个栈顶索引重合时, 这代表该共享栈已满. 具体实现 ...
  • 数据结构——共享栈的栈满条件判断

    千次阅读 多人点赞 2020-09-08 09:42:04
    共享栈判断栈满的条件,即判断两个栈顶的位置的状态,其根本是由两个栈顶指针的操作方式决定的。 用入栈操作来说有以下两种操作方式:(1)栈顶指针先加1,再赋值,那么栈顶指针所指的地方是最后入栈的元素(2)若先...
  • 共享栈的原理及代码实现(C语言)

    千次阅读 2019-04-28 09:19:54
    共享栈是一种特殊的栈,由顺序存储结构实现。 其特点在于两个栈共享同一块存储空间。 可以参考下面这张示意图(莫嫌丑) 两个栈的栈底分别位于数组的两端,而栈顶位于中间的位置(由元素数量决定),在上图中栈一有...
  • 为了使栈的空间能充分利用,可以让多个栈共享一个足够大的连续存储空间,通过移动栈顶指针,从而使多个栈空间互相补充,存储空间得到有效利用,这就是共享栈的设计思想。   最常见的是两个栈的共享。栈的共享原理...
  • 5. 共享栈模式 这种做法有什么好处?其实我们可以直接想想以前的方法(每个协程单独分配栈)有什么坏处好了: 以前的方法为每个协程都单独分配一段内存空间,因为是固定大小的,实际使用中协程并不能使用到这么...
  • 共享栈的定义以及基本操作

    千次阅读 2019-09-30 15:58:13
    1、共享栈:利用栈底位置相对不变的特性,让两个顺序栈共享一个一维数组空间。 2、共享栈的存储结构: #define stacklen 100 typedef struct{ char ch[stacklen]; int top1; //左边栈的栈顶 int top2; //右边...
  • 共享栈的入栈和出栈

    千次阅读 2020-03-20 13:25:23
    题目:设有两个s1,s2都采用顺序的方式,并共享一个存储区[0,…,maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶向上、迎面增长的存储方式。试设计s1,s2有关入栈和出栈的操作算法。 解答: 两个栈共享...
  • 共享栈是两个栈在一个顺序的存储空间中。两个栈的栈底分别是存储空间的首尾地址。 代码如下: stack.h #pragma once #include #define STACKMAXSIZE 1000 typedef char StackType; /*定义一个共享栈的结构*...
  • 共享栈的基本操作

    千次阅读 2018-07-07 17:45:50
    共享栈的实现:如图,top1从0开始向右入栈,top2从maxsize开始向左入栈,这样就可以满足在一个数组中创建两个栈,同时也避免了空间的浪费基本操作我们分为:初始化栈、入栈、出栈、取栈顶元素,具体实现代码如下 1 #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 268,079
精华内容 107,231
关键字:

共享栈