3-08. 堆栈模拟队列（25）
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。
所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:
（1） int IsFull(Stack S)：判断堆栈S是否已满，返回1或0；
（2） int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0；
（3） void Push(Stack S, ElementType item )：将元素item压入堆栈S；
（4） 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行。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
2 2 A 1 A 2 D D T |
1 2 |
| 2 |
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 |
#include<stdio.h> #include<stdlib.h> #include <malloc.h> //双向链表结点 typedef struct Node { int element; struct Node *piror; struct Node *Next; }node; typedef struct stack { node *base; node *top; int length; int MAXSIZE; }Stack; //创建最大容量为N的栈，base是栈底的后一个结点，top是栈顶的前一个结点 Stack *CreateStack(Stack *newStack,int N) { newStack->base=(node*)malloc(sizeof(node)); newStack->top=(node*)malloc(sizeof(node)); newStack->length=0; newStack->MAXSIZE=N; newStack->base->piror=NULL; newStack->base->Next=newStack->top; newStack->top->piror=newStack->base; newStack->top->Next=NULL; return newStack; } //判断栈是否为空 int EmptyStack(Stack* tStack) { if(tStack->length==0)return 1; else return 0; } //判断栈是否满 int FullStack(Stack *tStack) { if(tStack->length==tStack->MAXSIZE)return 1; else return 0; } //出栈 void GetoutStack(Stack *tStack) { tStack->top->piror=tStack->top->piror->piror; tStack->top->piror->Next=tStack->top; tStack->length--; } //入栈 void GetinStack(Stack *tStack,int n) { node *newPoint=(node*)malloc(sizeof(node)); newPoint->element=n; newPoint->piror=tStack->top->piror; newPoint->Next=tStack->top; tStack->top->piror->Next=newPoint; tStack->top->piror=newPoint; tStack->length++; } //读取栈顶元素，不删除 int GetTop(Stack* tStack) { return tStack->top->piror->element; } //遍历栈 void readStack(Stack* tStack) { node* pthis=tStack->base->Next; while(pthis!=tStack->top) { printf("%d ",pthis->element); pthis=pthis->Next; } } int main() { int N1,N2; scanf("%d%d",&N1,&N2); Stack *newStack1,*newStack2; newStack1=(Stack*)malloc(sizeof(Stack)); newStack2=(Stack*)malloc(sizeof(Stack)); //Stack *newStack2; newStack1=CreateStack(newStack1,N1); newStack2=CreateStack(newStack2,N2); if(N1>N2)N1=N2; getchar(); char c; while(c=getchar(),c!='T') { if(c=='A') { int t; scanf("%d",&t); if(newStack1->length==N1) { if(newStack2->length>0) { printf("ERROR:Full "); continue; } int i; for(i=0;i<N1;++i) { GetinStack(newStack2,GetTop(newStack1)); GetoutStack(newStack1); } } if(newStack1->length<N1) GetinStack(newStack1,t); else { printf("ERROR:Full "); continue; } } else if(c=='D') { if(newStack2->length==0) { if(newStack1->length==0) { printf("ERROR:Empty "); continue; } int i,size=newStack1->length; for(i=0;i<size;++i) { GetinStack(newStack2,GetTop(newStack1)); GetoutStack(newStack1); } } printf("%d ",GetTop(newStack2)); GetoutStack(newStack2); } } /* Stack *newStack; newStack=CreateStack(newStack,5); GetinStack(newStack,1); GetinStack(newStack,2);GetinStack(newStack,3);GetinStack(newStack,4); GetinStack(newStack,5); GetoutStack(newStack); printf("%d ",GetTop(newStack)); //readStack(newStack); */ return 0; }