设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。
所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:
int IsFull(Stack S)：判断堆栈S是否已满，返回1或0； int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0； void Push(Stack S, ElementType item )：将元素item压入堆栈S； ElementType Pop(Stack S )：删除并返回S的栈顶元素。 实现队列的操作，即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。
输入格式: 输入首先给出两个正整数N1和N2，表示堆栈S1和S2的最大容量。随后给出一系列的队列操作：A item表示将item入列（这里假设item为整型数字）；D表示出队操作；T表示输入结束。
输出格式: 对输入中的每个D操作，输出相应出队的数字，或者错误信息ERROR:Empty。如果入队操作无法执行，也需要输出ERROR:Full。每个输出占1行。
输入样例: 3 2 A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T 输出样例: ERROR:Full 1 ERROR:Full 2 3 4 7 8 ERROR:Empty
本题要用两个堆栈模仿队列，首先要弄清楚如何模仿，两个堆栈S1, S2, 容量分别为n1 和 n2，不妨令(n1<n2)，则我们把输入和数据先存入 S1 ,当存入的数据达到 n1 个时，把 S1 中的元素依次弹出并存入 S2 中，这时 S2 中的元素已经是按照队列的输出顺序排列的了，当 S2 中已经有 n1 个元素， 而且S1 已满时我们认为队列已满。且 只有把 S2 中的元素全部弹出后，才能重新把 S1 中的元素弹出放入 S2（S2中最多同时放 n1个元素）。
#include<stdio.h> #include<stdlib.h> /* 建立一个结构表示堆栈 */ typedef struct SNode *Stack; struct SNode{ int *data; int Last; int MaxSize; }; /* 建立堆栈的函数 */ Stack Create(int X){ Stack S = (Stack)malloc(sizeof(struct SNode)); S->data = (int*)malloc(sizeof(int)*X); S->MaxSize = X; S->Last = -1; return S; } /* 判断栈是否已满 */ int IsFull(Stack S){ return (S->MaxSize-1)==S->Last; } /* 判断栈是否为空 */ int IsEmpty(Stack S){ return S->Last==-1; } /* 入栈函数 */ void Push(Stack S, int X){ S->data[++(S->Last)] = X; } /* 出栈函数 */ int Pop(Stack S){ if(IsEmpty(S)){ //栈空的话输出错误信息 printf("ERROR:Empty\n"); return -1; //返回非法下标表示栈空 }else{ return S->data[(S->Last)--]; } } /* 队列的入队函数 */ void AddQ(Stack S1,Stack S2, int X){ //S1是容量小的栈，S2是容量大的栈 if((!IsFull(S1))){ //当 S1 未满时把元素压入 S1 中 Push(S1,X); }else if((IsFull(S1))&&(IsEmpty(S2))){ /* 当 S1 已满但 S2 为空时，把 S1 中的全部元素弹出并压入 S2 中 ，然后再把元素压入 S1 */ int i = S1->Last; for( ;i>=0;i--){ Push(S2,Pop(S1)); } Push(S1, X); } /* 当 S1 已经满了， 但 S2 中还有元素时， 表示队列已满 */ else if(IsFull(S1)&&(!IsEmpty(S2))){ printf("ERROR:Full\n"); //按题目要求输出错误信息 } } /* 出队函数 */ int DeleteQ(Stack S1, Stack S2){ if(!IsEmpty(S2)){ //S2 不空时把S2 中的元素出队 return Pop(S2); } /* 当S1不为空且 S2 为空时，把S1中的元素弹出并压入 S2 */ if((!IsEmpty(S1))&&IsEmpty(S2)){ int i = S1->Last; for( ;i>=0;i--){ Push(S2,Pop(S1)); } } return Pop(S2); //返回出队元素 } int main(void){ int N1,N2,X; char ch; scanf("%d %d",&N1,&N2); /* 选择两个数字中较小的一个作为 S1 （默认S1 是容量小的堆栈） */ if(N1>N2){ int temp; temp = N2; N2 = N1; N1 = temp; } Stack S1 = Create(N1); Stack S2 = Create(N2); getchar( ); while((ch=getchar())!='T'){ if(ch=='A'){ getchar( ); //处理空格 scanf("%d",&X); getchar( ); //处理空格 AddQ(S1,S2,X); } if(ch=='D'){ int l = DeleteQ(S1,S2); if(l!=-1) printf("%d\n",l); getchar( ); //处理空格 } } return 0; }