共享栈，即是两个栈使用同一段存储空间。
第一个栈从数组头开始存储，第二个栈从数组尾开始，两个栈向中间拓展。
当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 }
运行结果
本文转自博客园xingoo的博客，原文链接：共享栈，如需转载请自行联系原博主。
