共享栈,即是两个栈使用同一段存储空间。
第一个栈从数组头开始存储,第二个栈从数组尾开始,两个栈向中间拓展。
当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 }