[자료구조] 스택의 응용

[자료구조] 스택의 응용

스택은 알고 보면, 상당히 활용 할 곳이 많은 자료구조이다.

몇가지 스택을 응용하여 사용하는 것을 알아보자.

1. 역순 문자열 만들기.

스택의 LIFO 성질을 이용하여 문자열에 대한 역순 문자열을 간단히 만들 수 있

다. 문자열을 처음부터 순서대로 스택에 삽입한다. 
 
그 후 스택에 있는 원소들을 공백 스택이 될 때 까지 삭제하면서 반환된 문자를
나열하면 원래 문자열의 역순 문자열이 된다.

2. 시스템 스택

프로그램간의 호출과 복귀에 따른 수행 순서를 보면 호출한 순서와 복귀하는

순서는 반대기 때문에 가장 나중(last)에 호출된 함수가 가장 먼저(First) 실행

을 완료하고 복귀한다. 따라서 함수의 호출과 복귀 순서는 스택의 구조를 응용

하여 관리할 수 있다. 이 때 사용하는 스택을 시스템 스택이라 한다.

함수나 서브프로그램이 호출되면 일단 호출한 함수 수행에 필요한 지역변수,

매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템

스택에 삽입한다. 시스템 스택의 top은 항상 현재 실행중인 함수에 대한 스택

프레임이 된다. 함수의 실행이 끝나면 시스템 스택의 top원소를 삭제하면서 프

레임에 저장되어 있던 복귀 주소를 확인하고 복귀한다. 함수 호출과 복귀에 따

라 이 과정을 반복하여, 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스

택이 된다.

3. 수식의 괄호 검사.

수식은 일반적으로 연산자와 피연산자로 구성되어 있으며, 왼쪽에서 오른쪽 순

서로 처리한다. 수식에 사용한 연산자의 우선순위가 다를경우에는 우선순위가

높은 연산자를 먼저 처리하는데, 괄호를 사용하여 우선순위를 표현하기도 한

다. 이 때 괄호는 일반괄호, 중괄호, 대괄호 를 사용한다. 괄호는 왼쪽 괄호와

오른쪽 괄호가 반드시 쌍을 이루어야 하며, 여러 개의 괄호가 중첩된 경우에는

가장 안쪽의 괄호를 먼저 처리한다.

괄호가 포함된 수식에서 괄호의 쌍이 제대로 사용되었는지를 검사하기 위해서

스택을 사용할 수 있다. 수식을 읽으면서 왼쪽 괄호를 만나면 스택에 push하고
오른쪽 괄호를 만나면 스택을 pop한다. 현재의 오른쪽 괄호와 pop한 왼쪽 괄호

가 같은 종류의 괄호면 괄호의 쌍이 맞는 것이고, 수식의 처리가 모두 끝났을

때 스택이공백 스택이 되면 왼쪽 괄호와 오른쪽 괄호의 갯수가 맞는 것이다.

4. 수식의 후위 표기법 변환.

연산자와 피연산자로 구성된 수식을 표기하는 방법은 연산자의 위치에 따라 다

음의 세가지로 나눌 수 있다.

◀ 전위 표기법
 
연산자를 앞에 표기하고 그 다음에 피 연산자를 표기하는 방법 예) +AB

◀ 중위 표기법

연산자를 피연산자의 가운데에 표기하는 방법 예) A+B

◀ 후위 표기법

연산자를 피연산자 뒤에 표기하는 방법 예) AB+

중위표기법의 수식을 후위표기법으로 변환하는 방법을 알아보자.

수식 A*B-C/D를 후위 표기법으로 변환하면,

1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

((A*B)-(C/D)

2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

((AB)*(CD)/)-

3) 괄호를 제거한다..

AB*CD/-

우리가 일반적으로 사용하는 표기법은 중위 표기법이지만, 컴퓨터 내부에서 수

식을 처리하기에 가장 효율적인 방법은 후위 표기법이다. 후위 표기법을 사용

하면 괄호나 연산자 우선순위를 따로 처리하지 않고 왼쪽에서 오른쪽으로 표기

된 순서대로 처리할 수 있다. 우리가 컴퓨터에 중위 표기법 형태의 수식을 입력

하면 컴퓨터 내부에서는 효율적인 처리를 위해 스택을 사용하여 입력된 수식을
후위 표기법으로 변환하게 된다.

5. 후위 표기 수식의 연산.

컴퓨터 내부에서 후위 표기법의 수식을 연산할 때도 스택을 사용할 수 있다. 스

택을 사용하여 수식을 계산하는 방법은,

1) 피연산자를 만나면 스택에 삽입한다.

(2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고,

연산 결과를 다시 스택에 삽입한다.

(3) 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.