精华内容
下载资源
问答
  • //定义共享栈存储结构 typedef struct { ElemType data[MAXSIZE]; int leftTop; int rightTop; }Stack; //初始化 Status InitStack(Stack *s) { s -> leftTop = -1; s -> rightTop = MAXSIZE; return OK; ...

    关于该代码的理解,请参照下图

    出自大话数据结构

    #include <stdio.h>
    
    #define OK 1
    #define ERROR 0
    #define MAXSIZE 20
    
    typedef int ElemType;
    typedef int Status;
    
    //采用枚举类型, 是为了对对操作两个栈顶指针更为明显,不至于产生歧义,或者拥有视觉混淆
    typedef enum
    {
    	e_leftTop = 1,
    	e_rightTop = 2
    }TopType;
    
    //定义共享栈的存储结构
    typedef struct 
    {
    	ElemType data[MAXSIZE];
    	int leftTop;
    	int rightTop;
    }Stack;
    
    //初始化
    Status InitStack(Stack *s)
    {
    	s -> leftTop = -1;
    	s -> rightTop = MAXSIZE;
    	return OK;
    }
    
    //压栈
    Status Push(Stack *s, TopType type, ElemType elem)
    {
    	if(s -> leftTop + 1 == s -> rightTop) return ERROR;
    	switch(type)
    	{
    		case e_leftTop:
    			s -> data[s -> leftTop + 1] = elem;
    			s -> leftTop++;
    			break;
    		case e_rightTop:
    			s -> data[s -> rightTop - 1] = elem;
    			s -> rightTop--;
    			break;
    		default :
    			return ERROR;	
    	}
    	return OK;
    }
    
    //弹栈
    Status Pop(Stack *s, TopType type, ElemType *elem)
    {
    	switch(type)
    	{
    		case e_leftTop:
    			if(s -> leftTop == -1) return ERROR;
    			*elem = s -> data[s -> leftTop];
    			s -> leftTop --;
    			break;
    		case e_rightTop:
    			if(s -> rightTop == MAXSIZE) return ERROR;
    			*elem = s -> data[s -> rightTop];
    			s -> rightTop ++;
    			break;
    		default:
    			return ERROR;
    	}
    	return OK;			
    }
    
    //获取长度
    int Length(Stack s)
    {
    	return s.leftTop + 1 + MAXSIZE - s.rightTop; 
    }
    
    //清空
    Status Clear(Stack *s)
    {
    	s -> leftTop = -1;
    	s -> rightTop = MAXSIZE;
    	return OK;
    }
    
    int main(void)
    {
    	Status statu;
    	Stack s;
    	statu = InitStack(&s);
    	if(statu == OK)
    	{
    		printf("%s : %d, %d\n", "InitStack", s.leftTop, s.rightTop);
    		statu = Push(&s, e_leftTop, 21);
    		statu = Push(&s, e_rightTop, 22);
    		if(statu == OK)
    		{
    			printf("%s : %d, %d, %d, %d\n", "Push", s.leftTop, s.data[0], s.rightTop, s.data[MAXSIZE-1]);
    			ElemType poplElem;
    			ElemType poprElem;
    			statu = Pop(&s, e_leftTop, &poplElem);
    			statu = Pop(&s, e_rightTop, &poprElem);
    			if(statu == OK)
    			{
    				printf("%s : %d, %d, %d, %d\n", "Pop", s.leftTop, poplElem, s.rightTop, poprElem);
    				printf("%s : %d\n", "Length", Length(s));
    				//statu = Push(&s, e_leftTop, 21);
    				//statu = Push(&s, e_rightTop, 22);
    				//printf("%s : %d\n", "Length", Length(s));
    				statu = Clear(&s);
    				if(statu == OK)
    				{
    					printf("%s : %d, %d\n", "Clear", s.leftTop, s.rightTop);
    				}
    			}
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 栈的顺序存储——共享栈

    千次阅读 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;
    }
    


    展开全文
  • 两个栈共享连续存储空间:它主要利用了栈底位置不变,栈顶位置动态变化的特性。 所以在定义栈顶指针时,需要定义两个栈顶指针。 双栈类型定义如下: ...两个共享栈的压栈算法: int push(STACK *s,Ele...

    两个栈共享连续存储空间:它主要利用了栈底位置不变,栈顶位置动态变化的特性。
    所以在定义栈顶指针时,需要定义两个栈顶指针。

    双栈类型定义如下:

    typedef  struct
       {  datatype  data[MAXSIZE];
           int top[2];   /*  栈顶指针  */
        }DqStack;
    

    两个共享栈的压栈算法:

    int push(STACK *s,ElemType x,int k){//将x元素压入到以s为栈空间的第k个栈中
    if(s->top[0]+1==s->top[1])
        {
            printf("\n stack is full!");
            return 0;
        }
        if(k==0)
        {
            s->top[0]++;
            s->data[s->top[0]]=x;
        }
        else
        {
            s->top[1]--;
            s->data[s->top[1]]=x;
        }
        return 1;
        }
    

    两个共享栈的出栈算法:

    int pop(STACK *s,int k,ElemType *x)//将以s为栈空间的第k个栈顶元素取出
    {
        if((k==0)&&(s->top[0]==-1))
        {
            printf("\n stack is free!");
        }
        if((k==1)&&(s->top[1]==Max))
        {
            printf("\n stack is free!");
        }
        if(k==0)
        {
           * x=s->data[s->top[0]];
            s->top[0]--;
        }
        else
        {
            *x=s->data[s->top[1]];
            s->top[1]++;
        }
        return 1;
    }

    取栈顶元素:

    int stacktop(STACK *s,int k)//取栈顶元素
    {
    //ElemType x;
    if(k==0)
        {
    if (s->top[0]==-1)
    {   printf("栈空!\n");
    return 0;
    }
    printf("栈顶数据为:%d\n",s->data[s->top[0]]);
    return 1;
        }
        else
        {
            if (s->top[1]==Max)
    {   printf("栈空!\n");
    return 0;
    }
    //x=s->data[s->top[1]];
    printf("栈顶数据为:%d\n",s->data[s->top[1]]);
    return 1;
        }
    }

    两栈共享连续存储空间,两个栈的栈底分别设在这个存储空间的两端的存储结构中,为了使两栈的空间能够做到互补余缺,减少溢出的可能性,两个栈的栈满溢出都不能按位置判别,仅当两栈的栈顶相遇时,才可能栈满溢出。代码最核心问题是在入栈,出栈时候判断栈满,栈空条件。

    展开全文
  • #ifndef DOUBLESTACK_H #define DOUBLESTACK_H /* (1)引入 1.如果需要两个相同类型的(顺序结构), 分别为了两个开辟存储空间。...两栈共享存储空间的好处是:节省存储空间,降低上溢的可能性。 4.适用.
    #ifndef DOUBLESTACK_H
    #define DOUBLESTACK_H
    /*
        (1)引入
            1.如果需要两个相同类型的栈(顺序结构), 分别为了两个栈开辟存储空间。
              极有可能出现的情况是栈1已经满了,而栈2还有很多空闲区域。这样就不合理。
            2.解决方法是使用一个数组来同时存储两个这两个栈,这样可以让两个顺序结构栈动态获得存储空间
            3.两栈共享存储空间的好处是:节省存储空间,降低上溢的可能性。
            4.适用场景:两个栈的空间需求有相反关系(一个需求增加会导致另一个需求下降)时使用。
    
        (2)存储结构
            数组[bottom1,1,2,3,top1,...,top2,4,9,6,bottom2]		// 数组长度为MAXSIZE
            说明:
                1.栈1在左边,栈2在右边
                2.栈1向右增长,栈2向左增长。
        (3)栈的判定条件
            1.栈1为空
                top1 == 0
            2.栈2为空
                top2 == MAXSIZE
            3.存储空间已满
                top1 +1 == top2
        (4)压栈
            1.存储空间已满就退出
            2.如果压入栈1
                top1的下项存储新元素,top1+1
            2.如果压入栈2
                top2的前项存储新元素,top1-1
    
        (5)弹栈
            2.如果弹栈1
                如果栈为空,退出。
                删除top1的那一项,top1-1.
            2.如果弹栈2
                如果栈为空,退出。
                删除top2的那一项,top1+1.
    
     */
    #define MAXSIZE 8   // 数组的最大长度
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef int DElemType;
    typedef enum StackNum{
        STACK1 = 1,
        STACK2,
    }StackNum;
    typedef struct DoubleStack{
        DElemType data[MAXSIZE];
        int top1;   // 栈1的栈顶在数组中的下标
        int top2;   // 栈2的栈顶在数组中的下标
    }DoubleStack;
    
    // 初始化双栈
    int Init_DoubleStack(DoubleStack *s)
    {
        if (!s)
            return -1;
        memset(s, 0, sizeof(DoubleStack));
        s->top1 = -1;            // 栈1的栈顶从数组最左端开始,往右增长.
        s->top2 = MAXSIZE;    // 栈2的栈顶从数组最右端开始,往左增长.
    }
    
    
    // 栈1是空的
    int Stack1Empty(DoubleStack *s)
    {
        return (s->top1 == -1);
    }
    // 栈2是空的
    int Stack2Empty(DoubleStack *s)
    {
        return (s->top2 == MAXSIZE);
    }
    // 数组满了,不可再压入元素
    int StackFull(DoubleStack *s)
    {
        return ((s->top1+1) == s->top2);
    }
    int StackEmpty(DoubleStack *s)
    {
        return (Stack1Empty(s) && Stack2Empty(s));
    }
    void DoubleStackInfo(DoubleStack *s)
    {
        if (s->top1 != -1) {
            printf("stack1:");
            for(int i=0; i<= s->top1;i++){
                printf("%d, ", s->data[i]);
            }
        }
        if (s->top2 != MAXSIZE) {
            printf("stack2:");
            for(int i=MAXSIZE-1; i>= s->top2;i--){
                printf("%d, ", s->data[i]);
            }
        }
        if (StackEmpty(s))
            printf("stack is empty");
        printf("\n");
    }
    
    
    // 新元素e放入栈num
    int DoubleStackPush(DoubleStack *s,StackNum num, DElemType e)
    {
        if (StackFull(s) || !s)
            return -1;
        if (num == STACK1) {
            s->data[++s->top1] = e;
        }
        else if (num == STACK2){
            s->data[--s->top2] = e;
        }
        return 0;
    }
    // 从栈num中弹出一个元素,而用于返回其值
    int DoubleStackPop(DoubleStack *s,StackNum num, DElemType *e)
    {
        if (!s || !e)
            return -1;
        if (num == STACK1) {
            if (Stack1Empty(s))
                return -1;
            *e = s->data[s->top1--];
        }
        else if (num == STACK2){
            if (Stack2Empty(s))
                return -1;
            *e = s->data[s->top2++];
        }
        return 0;
    }
    #endif // DOUBLESTACK_H
    

     

    展开全文
  • 共享栈

    2020-08-03 19:28:26
    一 概述 利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。...共享栈是为了更有效地利用存储空间,两个栈的空间相...
  • 栈共享存储空间,其数组大小为100,数组下标从0开始,top1和top2分别为1和2的栈顶元素下标,则1为空的条件是_______ ,2为空的条件 ______ ,1或2满的条件是 ________ 。 正确答案: (1) top1==-1 (2) ...
  • 栈共享存储空间

    2017-09-22 20:15:21
    栈共享空间就是指,当其中一个的空间用光时,可以借用另外一个的空间,这样就大大提高了空间的利用率。 一个数组有两个端点,一个起始端点,另一个是数组末尾。而两个有两个底,我们就将其中一个底作为...
  • 栈共享存储空间算法

    千次阅读 2017-12-26 07:50:37
    对于一个,我们只能经理设计出合适大小的数组进行处理,但是对于2个相同类型的,我们可以共享存储空间,最大限度的利用事先开辟的存储空间进行操作。 关键思路:他们是数组的两端,向中间靠拢。top1和...
  • 顺序存储共享栈本质上就是把一个数组两端分别当成一个栈,这两个栈共用一块存储空间。 #include <stdio.h> #include <stdlib.h> #define MaxSize 20 #define ElemType int typedef struct{ ...
  • //的顺序存储结构成为顺序(sequebtial stack). //顺序利用一组地址连的存储单元依次存放从底到 栈顶的数据元素,通常用一维数组存放的元素 //”指针”top并非指针,而是表示栈顶元素的当前位置 //top...
  • C++实现顺序之两栈共享存储空间

    千次阅读 2015-07-03 22:31:09
    如果我们有两个相同类型的,我们为他们各自开辟了数组空间,极有可能第一个已经满了,再进栈就溢出了,而另一个还有很多存储空间空闲。这时,我们完全可以用一个数组存储两个。  我们的做法如下图,数组有...
  • 双向——两个栈共享同一存储空间1. 什么是双向? 算法导论原题: 10.1-2 Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number...
  • C语言顺序栈:共享栈

    2020-05-13 13:35:03
    共享栈 个人理解:共享顺序栈栈就是普通顺序栈在存储数组的另一头加上第二个栈顶指针。从而能够更有效地利用存储空间。 而顺序栈与链栈的区别可以参考顺序表和链表的关系。 代码如下 #include<stdio.h> #...
  • 优点:存取速度比堆要快,仅次于寄存器,且栈存储的数据可以用于共享 缺点:栈存储的大小确定,不能存储过大的数据 二、栈存储 存储对象:通常为new 创建的对象和数组 优点:动态分配内存大小,灵活性高 缺点:存取...
  • 数据结构与算法之两栈共享存储空间 其实的顺序存储很方便因为它只在表尾进行操作不存在普通线性表插入与删除还需要移动元素的情况同样它也有普通线性表的缺陷即必须确定数量然而对于两个相同类型的却可以做到...
  • 栈共享空间的存储结构设计概述数据结构设计算法设计1. 入栈(需预先判断是否满)2. 出栈(需预先判断是否空) 概述 由于的插入和删除操作具有它的特殊性,用顺序存储结构表示的插入或删除数据元素时并不...
  • 一文搞懂共享栈

    千次阅读 多人点赞 2020-04-18 16:17:14
    共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间; 两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。 忘记栈的...
  • 通过上一篇博客 -特殊的线性表(),不难知道的顺序存储(数组实现)性能相对较高,因为它不存在插入和删除时移动元素的问题,但是它有一点缺陷:要实现确定数组存储容量的大小,万一不够,需要扩充容量。...
  • (2)设计两个 S1、S2 都采用顺序方式,并且共享一个存储区[0,MaxLen-1], 为了尽量利用空间,减少溢出的可能,可采用栈顶相向、迎面增长 的存储方式,如图 2-1 所示。设计一个有关...
  • 共享存储空间的顺序的基本类型定义: typedef struct{ SElemType data[StackSize]; int top1,top2; }DuSqStack; 共享存储空间的顺序的基本操作: 1、初始化操作InitStack void InitStack(DuSqStack &...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,059
精华内容 1,223
关键字:

共享栈存储