PTA 6-7 在一个数组中实现两个堆栈

本题要求在一个数组中实现两个堆栈。

函数接口定义：

Stack CreateStack( int MaxSize ); bool Push( Stack S, ElementType X, int Tag ); ElementType Pop( Stack S, int Tag );

其中Tag是堆栈编号，取1或2；MaxSize堆栈数组的规模；Stack结构定义如下：

typedef int Position; struct SNode { ElementType *Data; Position Top1, Top2; int MaxSize; }; typedef struct SNode *Stack;

注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则Pop函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。

裁判测试程序样例：

#include <stdio.h> #include <stdlib.h> #define ERROR 1e8 typedef int ElementType; typedef enum { push, pop, end } Operation; typedef enum { false, true } bool; typedef int Position; struct SNode { ElementType *Data; Position Top1, Top2; int MaxSize; }; typedef struct SNode *Stack; Stack CreateStack( int MaxSize ); bool Push( Stack S, ElementType X, int Tag ); ElementType Pop( Stack S, int Tag ); Operation GetOp(); /* details omitted */ void PrintStack( Stack S, int Tag ); /* details omitted */ int main() { int N, Tag, X; Stack S; int done = 0; scanf("%d", &N); S = CreateStack(N); while ( !done ) { switch( GetOp() ) { case push: scanf("%d %d", &Tag, &X); if (!Push(S, X, Tag)) printf("Stack %d is Full!\n", Tag); break; case pop: scanf("%d", &Tag); X = Pop(S, Tag); if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag); break; case end: PrintStack(S, 1); PrintStack(S, 2); done = 1; break; } } return 0; } /* 你的代码将被嵌在这里 */

输入样式：

5 Push 1 1 Pop 2 Push 2 11 Push 1 2 Push 2 12 Pop 1 Push 2 13 Push 2 14 Push 1 3 Pop 2 End

输出样式：

Stack 2 Empty Stack 2 is Empty! Stack Full Stack 1 is Full! Pop from Stack 1: 1 Pop from Stack 2: 13 12 11

代码：

//创建栈 Stack CreateStack( int MaxSize ){ Stack res = (Stack)malloc(sizeof(Stack)); res -> Data = (int *)malloc(sizeof(int) * MaxSize); res -> Top1 = -1; res -> Top2 = MaxSize; res -> MaxSize = MaxSize; return res; } //输入数据 bool Push( Stack S, ElementType X, int Tag ){ if(S->Top1 + 1 == S->Top2){ printf("Stack Full\n"); return false; } if(Tag == 1){ S->Data[++S->Top1] = X; }else if(Tag==2){ S->Data[--S->Top2] = X; } return true; } //输出数据 ElementType Pop( Stack S, int Tag ){ if(Tag == 1){ if(S->Top1 == -1){ printf("Stack %d Empty\n",Tag); return ERROR; } return S->Data[S->Top1--]; } if(Tag == 2){ if(S->Top2 == S->MaxSize){ printf("Stack %d Empty\n",Tag); return ERROR; } return S->Data[S->Top2++]; } }