스택 응용 문제들

스택은 데이터의 순서를 뒤집어야 하는 경우에 유용하게 쓰인다. 스택을 임시 메모리로 사용하면 코드가 간결해진다.

(1) 문자열 뒤집기

문자열의 글자 순서를 뒤집는 문제는 스택을 이용하여 다음과 같이 해결할 수 있다. (널문자는 그대로 있음)

void reverse(char* word)
{
	stack_t stack;
	int i;
	for (i = 0; i < strlen(word); i++)
		push(&stack, word[i]);
	i = 0;
	while (!is_empty(&stack))
		word[i++] = pop(&stack);
}

(2) 2진수로 바꾸기

2진수로 바꾸는 문제는 2로 나눈 나머지를 거꾸로 이어 붙여서 2진수를 만들 수 있다. 이 문제도 스택을 이용해서 다음과 같이 간단하게 바꿀 수 있다.

void print_binary(int n)
{
	stack_t stack;
	while (n > 0) {
		push(&stack, n % 2);
		n /= 2;
	}
	while (!is_empty(&stack))
		printf("%d", pop(&stack));
}

(3) 주어진 단어가 거울문자열인지 검사하기

거울문자열인지 검사하는 문제도 스택을 이용하여 해결할 수 있다. (여기서는 typedef char element;여야 함)

int palindrome(char* word)
{
	stack_t stack;
	int i;
	init_stack(&stack);
	for (i = 0; i < strlen(word) / 2; i++)
		push(&stack, word[i]);
	if (strlen(word) % 2 > 0)
		i++;
	while (!is_empty(&stack))
		if (word[i++] != pop(&stack))
			return 0;
	return 1;
}

(4) 괄호 짝 검사

괄호 짝 검사도 스택을 이용하기에 적합한 문제다. 여는 괄호는 푸시하고 닫는 괄호에서는 팝해서 짝이 맞나 확인한다. 괄호가 아닌 경우는 그냥 넘어가면 된다.

int paren(char* word)
{
	stack_t stack;
	int i;
	init_stack(&stack);
	for (i = 0; i < strlen(word); i++) {
		if (word[i] == '(')
			push(&stack, word[i]);
		else if (word[i] == ')')
			if (pop(&stack) != '(')
				return 0;
	}
	return is_empty(&stack);
}

이런 문제 해결에 스택을 쓰면 코드가 간결하면서도 이해하기 쉬워진다는 점에서 큰 장점을 가진다.