本题要求在一个数组中实现两个堆栈。函数接口定义:
其中Stack CreateStack( int MaxSize ); bool Push( Stack S, ElementType X, int Tag ); ElementType Pop( Stack S, int Tag );
是堆栈编号,取1或2;
Tag
堆栈数组的规模;
MaxSize
结构定义如下:
Stack
注意:如果堆栈已满,typedef int Position; struct SNode { ElementType *Data; Position Top1, Top2; int MaxSize; }; typedef struct SNode *Stack;
函数必须输出“Stack Full”并且返回false;如果某堆栈是空的,则
Push
函数必须输出“Stack Tag Empty”(其中Tag是该堆栈的编号),并且返回ERROR。
Pop
裁判测试程序样例:
#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
分析:
PrintStack函数不知道是什么,不知道怎么输出,所以只能试,最后试出来,简直是浪费时间;
方法如下:
(1)Data指针是一维的,所以要用数组实现两个堆栈;
(2)申请一个MaxSize大小的数组,从两边开始分别加减实现两个栈;
(3)Top1控制左边的栈,初始值为-1,Top2控制右边的栈,初始值为MaxSize;
实现代码:Stack CreateStack( int MaxSize ){ Stack s; s=(Stack)malloc(sizeof(struct SNode)); s->MaxSize=MaxSize; s->Data=(int *)malloc(sizeof(int)*MaxSize); s->Top1=-1; s->Top2=MaxSize; return s; } bool Push( Stack S, ElementType X, int Tag ){ if(S->Top1==S->Top2-1){ printf("Stack Full\n"); return false; } if(Tag==1) S->Data[++S->Top1]=X; else S->Data[--S->Top2]=X; return true; } ElementType Pop( Stack S, int Tag ){ if(Tag==1){ if(S->Top1==-1){ printf("Stack 1 Empty\n"); return ERROR; } return S->Data[S->Top1--]; } else{ if(S->Top2==S->MaxSize){ printf("Stack 2 Empty\n"); return ERROR; } return S->Data[S->Top2++]; } }