BOJ 10828 : 스택

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/10828

 

 

스택 기본 구현 문제이다.

push, pop, size, empty, top을 구현해야 한다.

 

명령의 수가 최대 10000이므로 10000보다 큰 배열을 잡고, index 하나만 추가하면 stack이 완성된다.

즉 push할 때는 index = stack pointer = sp를 증가 시키고, pop할 때는 sp를 감소시킨다.

 

배열에 값을 넣고, sp를 증가시키면 들어오는 순서대로 값을 저장할 수 있다.

 

stack[sp] = input, sp++;

→ stack[sp++] = input;

 

값을 입력하고 sp를 증가시켰기 때문에 바로 이전 값은 sp - 1에 있다.

 

output = stack[sp - 1], sp--;

→  output = stack[--sp];

 

이렇게 구현하면 sp = stack의 size, sp - 1은 top이 되고, sp가 0인지 확인하면 empty인지도 확인 가능하다.

 

크기를 넉넉하게 잡았으니, push를 check할 필요는 없지만,

빈 stack에 pop을 하면 sp가 -1이 되므로,

if(sp)를 추가해서 보완하면 된다.

 

#include <stdio.h>

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

int main()
{
	int in, N;	
	int stack[10000 + 500] = { 0 };
	int sp = 0; /* stack pointer */

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		char input[10];
        
		scanf("%s", input);

		if (mystrcmp(input, "push") == 0)
		{
			scanf("%d", &in);
			stack[sp++] = in;
		}
		else if (mystrcmp(input, "pop") == 0)
		{
			if (sp) printf("%d\n", stack[--sp]);
			else printf("-1\n");
		}
		else if (mystrcmp(input, "size") == 0) printf("%d\n", sp);
		else if (mystrcmp(input, "empty") == 0) printf("%d\n", sp ? 0 : 1);
		else if (mystrcmp(input, "top") == 0) printf("%d\n", sp ? stack[sp - 1] : -1);
	}
    
    return 0;
}