스택 (Stack)

1. 스택이란?

스택은 데이터를 쌓아 올리는 형태의 자료구조입니다. 가장 중요한 특징은 LIFO (Last-In, First-Out), 우리말로 '후입선출'이라는 점입니다. 즉, "가장 나중에 들어온 데이터가 가장 먼저 나간다"는 규칙을 따릅니다.

 

이러한 특징으로 인해 스택의 모든 데이터 입출력은 꼭대기인 top에서만 이루어집니다.

• push : 스택의 top에 새로운 데이터를 쌓는(삽입하는) 작업입니다.
• pop : 스택의 top에서 데이터를 꺼내는(삭제하는) 작업입니다.

2. 스택의 구현

스택은 두 가지 방식으로 구현할 수 있으며 장단점이 뚜렷합니다.

1. 배열을 이용한 구현 (순차 스택)
   배열을 사용하면 구현이 매우 간단하고 직관적입니다. top이라는 변수가 배열의 마지막 데이터 인덱스를 가리키도록 관리하면 됩니다. 하지만 처음에 정해놓은 배열의 크기를 넘어서면 데이터를 더 이상 저장할 수 없는 '오버플로우'가 발생한다는 한계가 있습니다.
2. 연결 리스트를 이용한 구현 (연결 스택)
   연결 리스트로 구현하면 필요할 때마다 새로운 노드를 만들어 연결하므로, 메모리가 허용하는 한 계속해서 데이터를 저장할 수 있습니다. 크기 제한이 없는 '동적 스택'을 만들 수 있다는 것이 가장 큰 장점입니다.

3. 스택의 활용

스택의 LIFO 규칙은 컴퓨터 과학의 여러 문제를 해결하기 위해 사용됩니다.

• 웹 브라우저의 뒤로 가기 : 우리가 방문한 페이지 주소를 순서대로 스택에 push합니다. '뒤로 가기' 버튼을 누르면 스택에서 pop하여 바로 이전 페이지로 돌아갈 수 있습니다.
• 프로그램의 함수 호출 (시스템 스택) : main 함수가 A 함수를, A 함수가 B 함수를 호출하면, 컴퓨터는 main, A, B의 실행 정보를 순서대로 시스템 스택에 쌓습니다. B 함수가 끝나면 pop하여 A로, A가 끝나면 pop하여 main으로 돌아옵니다. LIFO 구조가 아니면 프로그램 실행 순서가 엉망이 될 것입니다.
• 수식 계산 및 괄호 검사 : { ( [ ] ) } 와 같은 복잡한 수식의 괄호 짝이 맞는지 검사할 때 스택을 유용하게 사용할 수 있습니다. 여는 괄호를 만나면 push, 닫는 괄호를 만나면 pop해서 짝이 맞는지 확인하는 간단한 로직으로 해결할 수 있습니다. 또한, 컴퓨터가 수식을 계산하기 쉬운 '후위 표기법'으로 변환하고 계산하는 과정에서도 스택은 핵심적인 역할을 수행합니다.