Stack 알고리즘.

스택(Stack) 알고리즘.

흔희들 스택(Stack) 알고리즘을 가장 단순한 것으로 생각한다. 아니 다시말해서 가장 단순한 것으로 생각한 나머지 별 할일 없는 알고리즘으로까지 치부하는게 문제다. 하지만 스택 알고리즘은 가장 단순하면서 그 단순함으로 인해서 가장 강력하고 널리쓰이는 알고리즘이다.

스택(Stack) 을 말할때에 가장 먼저 떠오르는 것이 LIFO 다. Last-In First-Out. 가장 나중에 들어간 데이터가 가정 먼저 나온다는 것을 영어로 표현한 것인데, 이것을 다른 관점에서 생각해보면 역정렬 알고리즘에 일종이기도 하다.

스택에 넣었다 꺼내면 역정렬된 상태가 된다.

이를 잘 활용할 수 있는 것이 있는데, 진수 변환이다. 10진수를 2진수로 진수 변환할때를 보자.

중학교때 배웠던 10진수를 2진수로 만드는 수학 방법이다. 이것을 자세히 보면 나머지로 나오는 것들을 스택에쌓아두고 역으로 뽑아내면 그것이 바로 이진수가 된다는 사실을 알 수 있다.

스택의 또 다른 용법에는 체커(Checker) 도 있다.

위는 간단한 PHP문법이다. PHP는 함수를 사용하거나 조건문과 같은 문법을 사용할때에 ‘{‘ 를 사용한다. ‘{‘ 로 열고 ‘}’로 닫는 식이다. 그래서 항상 쌍으로 존재하는데, PHP 컴파일러는 이러한 것이 오류가 없는지를 어떻게 체크를 할까?

다음과 같이 스택을 이용하면 간단히 체크할 수 있다.

처음에 ‘{‘ 를 만나면 스택에 넣는다. 그리고 ‘}’를 만나면 스택에서 제거한다. 최종적으로 더 이상 빼내야할 ‘{‘ 이 없고 스택이 텅 비어있다면 PHP 컴파일러는 문법으로 쓰이는 ‘{‘ 가 제대로 사용되었다라고 판단한다. 그래서 위 PHP의 예제를 스택을 이용해서 체크해보면 ‘{‘ 가 스택에 하나 남게되어 PHP 문법에 오류가 있다는 것을 알 수 있다.