目录

1 题目要求2 样例3 分析4 代码5 总结

1 题目要求

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

函数接口定义：

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; } /* 你的代码将被嵌在这里 */

2 样例

输入样例： 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

3 分析

对栈内元素进出，遵循从栈顶操作的原则。同一个数组包含两个栈，为了最大程度地利用数组空间，两个栈的栈顶索引下标在增加元素时应当是相向而行的。栈满即数组内没有空间再存放元素，使用两个栈的栈顶下标来进行判断。即 Top2-1=Top1栈空，即该栈的栈顶下标在初始位置。整个内存结构如图所示：

4 代码

Stack CreateStack( int MaxSize ) { Stack S=(Stack)malloc(sizeof(Stack)); S->Data = (int *)malloc(sizeof(ElementType)*MaxSize); S->MaxSize=MaxSize; S->Top1=-1;//0; S->Top2=MaxSize;//-1; return S; } bool Push( Stack S, ElementType X, int Tag ) { if(S->Top2-S->Top1==1) { printf("Stack Full\n"); return false; } if(Tag == 1) { S->Data[++S->Top1]=X; return true; } if(Tag == 2) { S->Data[--S->Top2]=X; return true; } } ElementType Pop( Stack S, int Tag ) { ElementType X; if((Tag ==1 && S->Top1 == -1) ||(Tag ==2 && S->Top2 == S->MaxSize)) { printf("Stack %d Empty\n",Tag); return ERROR; } /* if(tag ==2 && S->Top1 == MaxSize-1) { print("Stack %d Empty",Tag); return ERROR; } */ if(Tag == 1) { X=S->Data[S->Top1--]; } else if(Tag == 2) { X=S->Data[S->Top2++]; } return X; }

5 总结

注意：指针都是int型，存放的是指向的内存空间的起始地址。