## 問題描述 > 設有兩個棧s1,s2都采用順序棧方式，并且共享一個存儲區[0,…,MaxSize-1]，為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的方式。試設計s1,s2有關入棧和出棧的操作算法。 ## 算法思想 > 因為兩個棧公用一個空間，假設一個棧為0#，規定其為空時top[0]==-1；另一個棧為1#規定其為空時，top[1]==MaxSize； 入棧時，先確定棧號是否合法，然后查看是對0#棧還是1#棧進行操作，入棧操作和順序棧的入棧操作并無太大不同。選定之后進行入棧操作。這里應該注意此共享棧是否已滿，如果已滿則不能進行入棧操作。如若入棧成功則返回0；入棧失敗則返回-1； 出棧時，先確定棧號是否合法，然后查看是對0#棧還是1#棧進行操作，出棧操作和順序棧的出棧操作并無太大不同。選定之后進行出棧操作。如果出棧成功返回0；出棧失敗返回-1； 綜上，算法描述如下： ## 算法描述 ~~~ //共享棧的入棧操作 int Push(SqStack*s, ElemType x, int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } if(s->top[1]-s->top[0]==1){ printf("The stack is full!\n"); return -1; } switch(n){ case 0:s->data[++s->top[0]]=x;break; case 1:s->data[--s->top[1]]=x;break; } return 0; } //共享棧的出棧操作 int Pop(SqStack *s, ElemType* x,int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } switch(n){ case 0: if(s->top[0]==-1){ printf("The stack[0] is empty!\n"); } *x=s->data[s->top[0]--]; break; case 1: if(s->top[1]==MaxSize){ printf("The stack[1] is empty!\n"); } *x=s->data[s->top[1]++]; break; } return 0; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 100 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; int top[2]; }SqStack; void InitStack(SqStack*); int Push(SqStack*,ElemType,int); int Pop(SqStack*,ElemType*,int); int main(int argc,char* argv[]) { SqStack s; InitStack(&s); ElemType x=5; int n=0; int flagPush; flagPush=Push(&s,x,n); if(flagPush){ printf("Push false!\n"); }else{ printf("Push %d success!\n",x); } int flagPop; flagPop=Pop(&s,&x,n); if(flagPop){ printf("Pop false!\n"); }else{ printf("Pop %d success!\n",x); } return 0; } //初始化共享棧 void InitStack(SqStack *s) { s->top[0]=-1; s->top[1]=MaxSize; } //入棧操作 int Push(SqStack*s, ElemType x, int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } if(s->top[1]-s->top[0]==1){ printf("The stack is full!\n"); return -1; } switch(n){ case 0:s->data[++s->top[0]]=x;break; case 1:s->data[--s->top[1]]=x;break; } return 0; } //出棧操作 int Pop(SqStack *s, ElemType* x,int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } switch(n){ case 0: if(s->top[0]==-1){ printf("The stack[0] is empty!\n"); } *x=s->data[s->top[0]--]; break; case 1: if(s->top[1]==MaxSize){ printf("The stack[1] is empty!\n"); } *x=s->data[s->top[1]++]; break; } return 0; } ~~~