2-5 Two Stacks In One Array (20 分)
2-5 Two Stacks In One Array (20 分)
韩旭051
发布于 2019-11-08 00:46:24
发布于 2019-11-08 00:46:24
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://cloud.tencent.com/developer/article/1534994
2-5 Two Stacks In One Array (20 分)
Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used.
Format of functions:
Stack CreateStack( int MaxElements );
int IsEmpty( Stack S, int Stacknum );
int IsFull( Stack S );
int Push( ElementType X, Stack S, int Stacknum );
ElementType Top_Pop( Stack S, int Stacknum );where int Stacknum is the index of a stack which is either 1 or 2; int MaxElements is the size of the stack array; and Stack is defined as the following:
typedef struct StackRecord *Stack;
struct StackRecord {
int Capacity; /* maximum size of the stack array */
int Top1; /* top pointer for Stack 1 */
int Top2; /* top pointer for Stack 2 */
ElementType *Array; /* space for the two stacks */
}Note: Push is supposed to return 1 if the operation can be done successfully, or 0 if fails. If the stack is empty, Top_Pop must return ERROR which is defined by the judge program.
Sample program of judge:
#include <stdio.h>
#include <stdlib.h>
#define ERROR 1e8
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef struct StackRecord *Stack;
struct StackRecord {
int Capacity; /* maximum size of the stack array */
int Top1; /* top pointer for Stack 1 */
int Top2; /* top pointer for Stack 2 */
ElementType *Array; /* space for the two stacks */
};
Stack CreateStack( int MaxElements );
int IsEmpty( Stack S, int Stacknum );
int IsFull( Stack S );
int Push( ElementType X, Stack S, int Stacknum );
ElementType Top_Pop( Stack S, int Stacknum );
Operation GetOp(); /* details omitted */
void PrintStack( Stack S, int Stacknum ); /* details omitted */
int main()
{
int N, Sn, X;
Stack S;
int done = 0;
scanf("%d", &N);
S = CreateStack(N);
while ( !done ) {
switch( GetOp() ) {
case push:
scanf("%d %d", &Sn, &X);
if (!Push(X, S, Sn)) printf("Stack %d is Full!\n", Sn);
break;
case pop:
scanf("%d", &Sn);
X = Top_Pop(S, Sn);
if ( X==ERROR ) printf("Stack %d is Empty!\n", Sn);
break;
case end:
PrintStack(S, 1);
PrintStack(S, 2);
done = 1;
break;
}
}
return 0;
}
/* Your function will be put here */Sample Input:
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
EndSample Output:
Stack 2 is Empty!
Stack 1 is Full!
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11说了一大堆英文其实就五个函数
Stack CreateStack( int MaxElements );
申请内存整一个空的栈
int IsEmpty( Stack S, int Stacknum );
看看是不是没东西是空的
返回成功与否
int IsFull( Stack S );
看看大小是不是满了
返回成功与否
int Push( ElementType X, Stack S, int Stacknum );
把新的数据压入进去
看看成功与否
ElementType Top_Pop( Stack S, int Stacknum );
把顶部的数据弹出返回出来
返回弹的元素
Stack CreateStack(int MaxElements){
Stack p=(Stack)malloc(sizeof(struct StackRecord));
p->Array=(int*)malloc(MaxElements*sizeof(int));
p->Top1=-1;
p->Top2=MaxElements;
p->Capacity=MaxElements;
return p;
}
int IsEmpty(Stack S,int Stacknum){
if(Stacknum==1){if(S->Top1==-1) return 1;}
else if(S->Top2==S->Capacity) return 1;
return 0;
}
int IsFull(Stack S){
if(S->Top2-S->Top1==1) return 1;
return 0;
}
int Push(ElementType X, Stack S, int Stacknum){
if(IsFull(S)) return 0;
if(Stacknum==1) S->Array[++(S->Top1)]=X;
else S->Array[--(S->Top2)]=X;
return 1;
}
ElementType Top_Pop(Stack S,int Stacknum){
if(IsEmpty(S,Stacknum)) return ERROR;
if(Stacknum==1) return S->Array[(S->Top1)--];
else return S->Array[(S->Top2)++];
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录