2-5 Two Stacks In One Array
in Array One two
2023-09-14 09:01:32 时间
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
End
Sample Output:
Stack 2 is Empty!
Stack 1 is Full!
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C (gcc)
思路:
实现四个函数:
创建空栈
判断是否为空
判断是否满栈
入栈
出
代码样例:
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)++];
}
相关文章
- 解决Vue多次点击同一个路由的Uncaught (in promise)问题
- a javascript error occurred in_in from of是什么意思
- Dockerfile中 RUN yum -y install vim失败Cannot prepare internal mirrorlist: No URLs in mirrorlist
- ORA-29321: too many datafiles added since the point-in-time ORACLE 报错 故障修复 远程处理
- ORA-29981: Cannot register query: conflicting DDL in progress ORACLE 报错 故障修复 远程处理
- ORA-53046: tag: string collides with existing tag: string in document: string ORACLE 报错 故障修复 远程处理
- ORA-00447: fatal error in background process ORACLE 报错 故障修复 远程处理
- ORA-14297: Index block size mismatch in ALTER TABLE EXCHANGE [SUB]PARTITION ORACLE 报错 故障修复 远程处理
- ORA-15504: cannot start workload capture because instance string not present in RESTRICTED SESSION mode ORACLE 报错 故障修复 远程处理
- PostgreSQL 55006: object_in_use 报错 故障修复 远程处理
- Invalid character found in method name. HTTP method names must be tokens详解编程语言
- Find Minimum in Rotated Sorted Array II详解编程语言
- Search in Rotated Sorted Array详解编程语言
- 查询Oracle中执行多列IN查询的技巧(oracle多列in)
- 子查询MySQL联表IN子查询:实现跨表快速查询(mysql联表in)
- 如何有效运用SQL Server的IN语句(sqlserver用in)
- MySQL中使用IN类型参数(mysql中in类型参数)
- MySQL中IN语句的限制详解(mysql中in的限制)
- MySQL中IN操作符的用法与注意事项(mysql中in的写法)
- MySQL中IN查询的使用及效率优化(mysql中in的0)
- MySQL中使用IN子句出现重复值问题的解决方法(mysql中in有重复值)
- MySQL中的IN查询的性能优化(mysql中in性能)
- MySQL中使用IN操作符查询字符串(mysql中in字符串)
- MySQL中IN语句的参数化使用方法(mysql中in参数化)
- MySQL IN函数的使用方法和注意事项(mysql 中in函数)
- 中利用IN语句检索Oracle数据库中的数据(in在oracle数据库)
- Oracle IN查询双重优势一步搞定复杂任务(oracle两个in查询)
- in用Oracle中Like和In实现模糊查询(oracle like和)
- 使用js判断数组中是否包含某一元素(类似于php中的in_array())
- php中in_array函数用法分析