스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 대표적인 데이터 구조입니다. 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 이 특성 덕분에, 스택은 컴퓨터 공학 전반에서 다양한 중요한 용도로 활용됩니다. 아래에서 그 대표적인 응용 분야를 살펴보겠습니다.
1. 수식(Expression) 처리
중위 표기법 → 후위·전위 표기법 변환
스택은 중위 표기법(Infix)으로 작성된 수식을 후위 표기법(Postfix) 또는 전위 표기법(Prefix) 형태로 변환하는 데 활용됩니다. 컴퓨터는 사람이 익숙하게 사용하는 중위 표기법보다 후위나 전위 표기법으로 표현된 수식을 훨씬 효율적으로 처리할 수 있습니다.
이러한 표기법의 가장 큰 장점은 연산자의 우선순위 규칙이나 괄호를 유지할 필요가 없다는 점입니다. 연산 순서가 이미 표기 자체에 반영되어 있기 때문에, 컴퓨터는 단순한 규칙만으로 수식을 처리할 수 있습니다.
후위·전위 표기식의 계산(Evaluation)
수식을 후위 또는 전위 표기법으로 변환한 후에는 실제 결과값을 얻기 위한 계산 과정이 필요합니다. 이 계산 역시 스택을 활용하여 수행합니다. 피연산자를 차례로 스택에 저장하고, 연산자를 만날 때마다 스택에서 값을 꺼내 연산한 뒤 결과를 다시 저장하는 방식으로 진행됩니다.
2. 백트래킹(Backtracking) 절차
백트래킹은 대표적인 알고리즘 설계 기법 중 하나입니다. 문제를 해결하기 위해 한 경로를 탐색하다가, 해당 경로가 유효하지 않거나 비효율적이라고 판단되면 이전 상태로 되돌아가 다른 경로를 시도하는 방식입니다.
현재 상태에서 이전 상태로 돌아가려면 지나온 경로의 상태 정보를 저장해 두어야 하는데, 이때 스택이 사용됩니다. 마지막에 저장된 상태부터 순서대로 꺼내어 되돌아갈 수 있기 때문입니다.
백트래킹의 대표적인 예로는 나이트 투어(Knight Tour) 문제, N-Queen 문제, 미로 찾기 등이 있습니다.
3. 함수 호출(Function Call)과 복귀 처리
스택의 또 다른 중요한 용도는 프로그램 실행 중 발생하는 함수 호출과 복귀 과정입니다. 어떤 함수 내부에서 다른 함수를 호출할 때, 그 호출문은 반드시 함수의 첫 번째 문장일 필요가 없습니다.
함수 호출이 끝난 후에는 프로그램이 처음부터 다시 시작하는 것이 아니라, 제어권이 떠났던 위치로 돌아가 중단된 작업을 이어서 재개(resume)해야 합니다. 이를 위해 호출이 발생하면 현재 프로그램 카운터(PC, Program Counter)의 주소, 즉 복귀 주소를 스택에 저장(push)한 뒤 함수 본문으로 이동하여 실행을 진행합니다.
함수의 실행이 완료되면 스택에서 복귀 주소를 꺼내(pop) 프로그램 카운터에 다시 설정함으로써, 중단되었던 지점부터 작업을 원활하게 이어갈 수 있습니다. 실제로 운영체제와 프로그래밍 언어 런타임은 이러한 목적으로 호출 스택(Call Stack)을 사용하며, 여기에는 복귀 주소뿐만 아니라 매개변수와 지역 변수까지 함께 저장됩니다.