## 問題描述 利用兩個棧S1，S2來模擬一個隊列，已知棧的4的運算定義如下： Push(S,x); 元素x入棧S Pop(S,x); S出棧并將出棧的值賦給x StackEmpty(S); 判斷棧是否為空 StackOverflow(S); 判斷棧是否滿 Enqueue; 將元素x入隊 Dequeue; 出隊，并將出隊元素存儲在x中 QueueEmpty; 判斷隊列是否為空 那么如何利用棧的運算實現該隊列的3個運算？ ## 算法思想 由于棧先進后出的特性，使用兩個棧便可完成兩次先進先出的過程，即相當于先進先出。 我們設置兩個棧S1，S2。 對S2的出棧操作用作出隊，若S2為空，則現將S1中所有元素送入S2； 對S1的入棧操作用作入隊，若S1為滿，必須先保證S2為空，才能將S1中的元素全部插入S2中； ## 算法描述 ~~~ //入隊 int EnQueue(SqStack *S1,SqStack *S2,ElemType x) { if(StackOverflow(S1)!=0){ Push(S1,x); return 0; } if(StackOverflow(S1)==0&&StackEmpty(S2)!=0){ printf("The Queue is full!\n"); return -1; } if(StackOverflow(S1)==0&&StackEmpty(S2)==0){ while(StackEmpty(S1)!=0){ Pop(S1,&x); Push(S2,x); } return 0; } return -1; } //出隊 int DeQueue(SqStack *S1,SqStack *S2, ElemType* x) { if(StackEmpty(S2)!=0){ Pop(S2,x); }else if(StackEmpty(S1)==0){ printf("The queue is empty!\n"); return -1; }else{ while(StackEmpty(S1)!=0){ Pop(S1,x); Push(S2,*x); } Pop(S2,x); } return 0; } //判斷隊列是否為空 int QueueEmpty(SqStack *S1, SqStack *S2) { if(StackEmpty(S1)==0&&StackEmpty(S2)==0){ printf("The Queue is empty!\n"); return 0; }else{ return -1; } } ~~~ 具體代碼見附件。 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 10 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack*); void Push(SqStack*, ElemType); void Pop(SqStack*, ElemType*); int StackEmpty(SqStack*); int StackOverflow(SqStack*); void Print(SqStack*); int EnQueue(SqStack*,SqStack*,ElemType); int DeQueue(SqStack*,SqStack*,ElemType*); int QueueEmpty(SqStack*, SqStack*); int main(int argc,char* argv[]) { SqStack S1; SqStack S2; InitStack(&S1); InitStack(&S2); for(int i=0;i<10;i++){ EnQueue(&S1,&S2,i); } ElemType x; DeQueue(&S1,&S2,&x); printf("%4d\n",x); DeQueue(&S1,&S2,&x); printf("%4d\n",x); DeQueue(&S1,&S2,&x); printf("%4d\n",x); return 0; } //入隊 int EnQueue(SqStack *S1,SqStack *S2,ElemType x) { if(StackOverflow(S1)!=0){ Push(S1,x); return 0; } if(StackOverflow(S1)==0&&StackEmpty(S2)!=0){ printf("The Queue is full!\n"); return -1; } if(StackOverflow(S1)==0&&StackEmpty(S2)==0){ while(StackEmpty(S1)!=0){ Pop(S1,&x); Push(S2,x); } return 0; } return -1; } //出隊 int DeQueue(SqStack *S1,SqStack *S2, ElemType* x) { if(StackEmpty(S2)!=0){ Pop(S2,x); }else if(StackEmpty(S1)==0){ printf("The queue is empty!\n"); return -1; }else{ while(StackEmpty(S1)!=0){ Pop(S1,x); Push(S2,*x); } Pop(S2,x); } return 0; } //判斷隊列是否為空 int QueueEmpty(SqStack *S1, SqStack *S2) { if(StackEmpty(S1)==0&&StackEmpty(S2)==0){ printf("The Queue is empty!\n"); return 0; }else{ return -1; } } /*--------------------------------------------*/ //初始化棧 void InitStack(SqStack *S) { S->top=-1; } //入棧 void Push(SqStack *S, ElemType x) { if(S->top==MaxSize-1){ printf("The Stack is full!\n"); return; } S->data[++S->top]=x; } //出棧 void Pop(SqStack *S, ElemType *x) { if(S->top==-1){ printf("The Stack is empty!\n"); return; } *x=S->data[S->top--]; } //判斷棧是否為空 int StackEmpty(SqStack *S) { if(S->top==-1){ return 0; } return -1; } //判斷棧是否已滿 int StackOverflow(SqStack *S) { if(S->top==MaxSize-1){ return 0; } return -1; } //打印棧中所有元素 void Print(SqStack *S) { int i=S->top; while(i!=-1){ printf("%4d",S->data[i]); i--; } printf("\n"); } ~~~