共享栈

共享栈,即是两个栈使用同一段存储空间。

第一个栈从数组头开始存储,第二个栈从数组尾开始,两个栈向中间拓展。

当top1+1==top2或者top1==top2-1时,即staock overflow!.

与普通栈一样,共享栈出栈入栈的时间复杂度仍为O(1).

数据结构

typedef struct shareStack{
    int data[MAXSIZE];
    int top1;
    int top2;
}shareStack;

出栈操作

该数据,仅存的是非负数,因此如果想要存储更复杂的操作,可以在判断栈空时,换一种方式,即可。

int Pop(shareStack *ss,int flag){
    if(flag == 1){
        if(ss->top1 == -1)
            return -1;
        return ss->data[ss->top1--];
    }else if(flag == 2){
        if(ss->top2 == MAXSIZE)
            return -1;
        return ss->data[ss->top2++];
    }
    return -1;
}

入栈操作

int Push(shareStack *ss,int num,int flag){
    if(ss->top1+1 == ss->top2)
        return 0;
    if(flag == 1){
        ss->data[++ss->top1] = num;
        return 1;
    }else if( flag == 2){
        ss->data[--ss->top2] = num;
        return 1;
    }
    return 0;
}

示例代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define MAXSIZE 20
  4 
  5 typedef struct shareStack{
  6     int data[MAXSIZE];
  7     int top1;
  8     int top2;
  9 }shareStack;
 10 
 11 void createStack(shareStack * ss,int n,int m);
 12 void showStack(shareStack *ss);
 13 int Push(shareStack *ss,int num,int flag);
 14 int Pop(shareStack *ss,int flag);
 15 
 16 int main()
 17 {
 18     shareStack * ss = (shareStack *)malloc(sizeof(shareStack));
 19 
 20     createStack(ss,3,4);
 21     showStack(ss);
 22 
 23     if(Push(ss,6,1))
 24         showStack(ss);
 25 
 26     if(Push(ss,4,2))
 27         showStack(ss);
 28 
 29     int n;
 30     n=Pop(ss,1);
 31     if(n>=0)
 32         printf("the pop num is:%d\n",n);
 33     n=Pop(ss,2);
 34     if(n>=0)
 35         printf("the pop num is:%d\n",n);
 36     n=Pop(ss,1);
 37     if(n>=0)
 38         printf("the pop num is:%d\n",n);
 39     n=Pop(ss,1);
 40     if(n>=0)
 41         printf("the pop num is:%d\n",n);
 42     n=Pop(ss,1);
 43     if(n>=0)
 44         printf("the pop num is:%d\n",n);
 45     n=Pop(ss,1);
 46     if(n>=0)
 47         printf("the pop num is:%d\n",n);
 48     n=Pop(ss,1);
 49     if(n>=0)
 50         printf("the pop num is:%d\n",n);
 51 
 52     showStack(ss);
 53 
 54     return 0;
 55 }
 56 
 57 void createStack(shareStack * ss,int n,int m){
 58     int i;
 59     ss->top1 = -1;
 60     ss->top2 = MAXSIZE;
 61     for(i=0;i<n;i++){
 62         ss->top1++;
 63         ss->data[ss->top1] = 2*i+1;
 64     }
 65     for(i=0;i<m;i++){
 66         ss->top2--;
 67         ss->data[ss->top2] = 2*i+1;
 68     }
 69 }
 70 
 71 void showStack(shareStack *ss){
 72     int i;
 73     for(i=0;i<ss->top1+1;i++){
 74         printf("%d->",ss->data[i]);
 75     }
 76     printf("top1-----top2");
 77     for(i=ss->top2;i<MAXSIZE;i++){
 78         printf("<-%d",ss->data[i]);
 79     }
 80     printf("\n");
 81 }
 82 
 83 int Push(shareStack *ss,int num,int flag){
 84     if(ss->top1+1 == ss->top2)
 85         return 0;
 86     if(flag == 1){
 87         ss->data[++ss->top1] = num;
 88         return 1;
 89     }else if( flag == 2){
 90         ss->data[--ss->top2] = num;
 91         return 1;
 92     }
 93     return 0;
 94 }
 95 
 96 int Pop(shareStack *ss,int flag){
 97     if(flag == 1){
 98         if(ss->top1 == -1)
 99             return -1;
100         return ss->data[ss->top1--];
101     }else if(flag == 2){
102         if(ss->top2 == MAXSIZE)
103             return -1;
104         return ss->data[ss->top2++];
105     }
106     return -1;
107 }

运行结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

textFile构建RDD的分区及compute计算策略

1,textFile A),第一点,就是输入格式,key,value类型及并行度的意义。 def textFile( path: String, mi...

2557
来自专栏码匠的流水账

聊聊eureka server的response cache

eureka-core-1.8.8-sources.jar!/com/netflix/eureka/resources/ApplicationResource....

1143
来自专栏iOS开发

iOS开发之 Method Swizzling 深入浅出

如果产品经理突然说:"在所有页面添加统计功能,也就是用户进入这个页面就统计一次"。我们会想到下面的一些方法:

4857
来自专栏jeremy的技术点滴

JVM的Finalization Delay引起的OOM

4068
来自专栏我杨某人的青春满是悔恨

走进 RxSwift 之观察者模式

RxSwift 是 ReactiveX 系列的 Swift 版本,如果你之前用过 ReactiveCocoa(RAC) 的话,想必对 Functional Re...

2092
来自专栏岑玉海

MD5鉴定文件是否相同

由于诸多安全因素,需要对网上下载的一些文件进行完整性校验。比如,由于工作需要我下载了一个EMOS_1.5_i386.iso镜像文件(extmail邮件系统),需...

4505
来自专栏码匠的流水账

聊聊sentinel的DegradeSlot

com/alibaba/csp/sentinel/slots/block/degrade/DegradeSlot.java

1451
来自专栏清晨我上码

异步任务执行的设计模式

2573
来自专栏wannshan(javaer,RPC)

dubbo消费方服务调用过程源码分析

dubbo PRC服务调用过程很复杂,这里准备通过分析一个典型rpc方法调用的调用栈来说明调用过程。说它典型,是因为本次分析的调用场景很典型简单 先定义一个接...

2.7K8
来自专栏码匠的流水账

聊聊sentinel的SimpleHttpCommandCenter

sentinel-transport-simple-http-0.1.1-sources.jar!/com/alibaba/csp/sentinel/trans...

911

扫码关注云+社区

领取腾讯云代金券