[SCTF][C] FILO 스택 구현 문제

교내 해킹대회 SCTF에서 CODING문제로 출제 된 FILO 문제 write up

언어 & IDE

Lang: C

IDE: DEV C++

 

1. 문제 파악

제공된 문제 파일을 보자. 총 구현해야하는 기능은 push, pop, size, empty, top이다.

2. 구현

1. main 

int main(void){
	char command[10];
	int i;
	int* stack;
	int stack_size;
	int stack_data;
	int ESP = 0;
	
	scanf("%d", &stack_size);
	stack = (int *)malloc(sizeof(int)*stack_size);
	
	for(i=0;i<stack_size;i++){
		scanf("%s", command);
		
		if(!strcmp(command, "push")){
			scanf("%d", &stack_data);
			push(stack, &ESP, stack_size, stack_data);
		}
	
		else if(!strcmp(command, "pop")){
			pop(stack, &ESP);
		}
		
		else if(!strcmp(command, "size")){
			size(&ESP);
		}
		
		else if(!strcmp(command, "empty")){
			empty(&ESP);
		}
		
		else if(!strcmp(command, "top")){
			top(stack, &ESP);
		}	
	}
	
	free(stack);
	return 0;
}

먼저, 명령의 수와 명령을 입력 받고 함수를 호출할 수 있도록 main함수를 구성했다.

그리고 스택에 관련된 변수(*stack, stack_size, stack_data)를 선언하고 스택을 동적할당을 사용하여 생성함.

2. push X

void push(int* stack, int* ESP, int stack_size, int data){
	if(stack_size == *ESP){
		printf("stack overflow!\n");
	}
	else{
		stack[(*ESP)++] = data;
	}	
	return ;
}

push를 구현하기 위해서는 먼저 필요한 값( *stack, ESP의 주소값, stack에 넣을 data)가 필요하다.

* ESP는 스택의 가장 위를 가르킴.

 

ESP와 stack_size 똑같다면, 더 이상 스택에는 공간이 없으므로, stack overflow를 출력한다.

stack에 데이터를 저장하고, *ESP의 값을 1 높혀준다

3. pop

void pop(int* stack, int* ESP){
	if(*ESP == 0){
		printf("-1\n");
	}
	else{
		printf("%d\n" ,stack[--(*ESP)]);
		stack[*ESP] = 0;
	}
	return ;
}

pop을 구현하기 위해서는 필요한 값은 (*stack, ESP의 주소값)이 필요하다.

 

pop은 push와 반대로 *ESP의 값이 0이라면 stack underflow인 -1을 출력한다.

*ESP 값을 먼저 1 감소 시키고, stack에 0(NULL)을 삽입한다.

4. size

void size(int *ESP){
	printf("%d\n",*ESP);
	return ;
}

현재 stack에 들어있는 데이터의 개수를 출력하는 함수로 필요한 값은 *ESP 이다.

 

간단하게 *ESP의 값이 stack에 들어가있는 데이터의 개수이다.

5. empty

void empty(int *ESP){
	if(*ESP == 0){
		printf("1\n");
	}
	else{
		printf("0\n");
	}
	return ;
}

pop을 구현할 때 *ESP가 0 인지 비교하는 조건문이 있었는데, 그와 아주 유사하다. 

필요한 값은 *ESP뿐이다.

 

6. top

void top(int* stack, int* ESP){
	if(*ESP == 0){
		printf("-1\n");
	}
	else{
		printf("%d\n", stack[*ESP-1]);
	}
	return ;
}

empty와 상당히 유사하다. 하지만 출력값의 약간의 차이는 있다. stack의 최상단에 있는 데이터를 출력하는 함수이다.

필요한 값은 *stack과 *ESP이다. 간단하게 최상단에 있는 데이터를 출력할 수 있다. 

 

3. 테스트

제공 해준 예제 입력으로 테스트

올바르게 출력이 되는것을 알 수 있다. FILO 문제 구현 끝.

 

4. 전체코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void push(int* stack, int* ESP, int stack_size, int data);
void pop(int* stack, int* ESP);
void size(int *ESP);
void empty(int *ESP);
void top(int* stack, int* ESP);

int main(void){
	char command[10];
	int i;
	int* stack;
	int stack_size;
	int stack_data;
	int ESP = 0;
	
	scanf("%d", &stack_size);
	stack = (int *)malloc(sizeof(int)*stack_size);
	
	for(i=0;i<stack_size;i++){
		scanf("%s", command);
		
		if(!strcmp(command, "push")){
			scanf("%d", &stack_data);
			push(stack, &ESP, stack_size, stack_data);
		}
	
		else if(!strcmp(command, "pop")){
			pop(stack, &ESP);
		}
		
		else if(!strcmp(command, "size")){
			size(&ESP);
		}
		
		else if(!strcmp(command, "empty")){
			empty(&ESP);
		}
		
		else if(!strcmp(command, "top")){
			top(stack, &ESP);
		}	
	}
	
	free(stack);
	return 0;
}


void push(int* stack, int* ESP, int stack_size, int data){
	if(stack_size == *ESP){
		printf("stack overflow!\n");
	}
	else{
		stack[(*ESP)++] = data;
	}	
	return ;
}

void pop(int* stack, int* ESP){
	if(*ESP == 0){
		printf("-1\n");
	}
	else{
		printf("%d\n" ,stack[--(*ESP)]);
		stack[*ESP] = 0;
	}
	return ;
}

void size(int *ESP){
	printf("%d\n",*ESP);
	return ;
}

void empty(int *ESP){
	if(*ESP == 0){
		printf("1\n");
	}
	else{
		printf("0\n");
	}
	return ;
}

void top(int* stack, int* ESP){
	if(*ESP == 0){
		printf("-1\n");
	}
	else{
		printf("%d\n", stack[*ESP-1]);
	}
	return ;
}