首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >共享栈

共享栈

作者头像
用户1154259
发布2018-01-18 10:41:31
1.1K0
发布2018-01-18 10:41:31
举报

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

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

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

运行结果

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2014-01-27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据结构
  • 出栈操作
  • 入栈操作
  • 示例代码
  • 运行结果
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档