스택(Stack)

스택은 데이터를 저장하는 방식 중 하나로, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 구조(LIFO: Last In, First Out)를 갖는다. 일상에서 가장 비슷한 예를 들자면, 책을 한 권씩 쌓아 올린 모습과 같다. 위에 올린 책이 가장 먼저 손에 잡히듯, 스택에서는 마지막에 들어온 데이터가 가장 먼저 빠져나온다. 이 단순한 규칙 덕분에 스택은 다양한 알고리즘과 시스템 동작 속에서 중요한 역할을 한다.

스택은 크게 두 연산으로 구성된다. 데이터를 추가하는 push, 데이터를 꺼내는 pop. push는 스택의 가장 위에 데이터를 올려놓는 동작이며, pop은 그 위에서 데이터를 하나 꺼내는 동작이다. 이때 pop은 스택이 비어 있으면 수행할 수 없다. 스택은 오직 한쪽 끝(“top”)에서만 삽입과 삭제가 이루어지기 때문에 구조적으로 매우 단순하고 예측 가능하다.

스택이 많이 쓰이는 이유는 이 LIFO 구조가 특정 상황에서 매우 자연스럽게 맞아떨어지기 때문이다. 예를 들어 함수 호출이 중첩되는 상황을 생각해보면 이해가 쉽다. A 함수가 B 함수를 호출하고, B 함수가 C 함수를 호출하면, 프로그램은 C → B → A 순으로 복귀한다. 가장 마지막에 호출된 함수가 가장 먼저 종료되기 때문이다. 실제로 프로그래밍 언어의 함수 호출 기록을 저장하는 공간도 ‘스택 프레임(stack frame)’이라고 부르며, 내부적으로 스택 구조로 관리된다.

또한 스택은 괄호 검증 같은 알고리즘 문제에서도 핵심적으로 등장한다. 여는 괄호 ‘(’를 만나면 push, 닫는 괄호 ‘)’를 만나면 pop을 수행하며, 스택이 정확히 비어 있는지를 확인하는 방식으로 괄호 구조의 올바름을 판단한다. 브라우저의 뒤로 가기 버튼 역시 스택 개념으로 동작한다. 사용자가 방문한 페이지를 차곡차곡 쌓아두고(pop), 뒤로 갈 때는 가장 마지막 페이지부터 되돌아가는 것이다.

스택의 시간 복잡도는 매우 효율적이다. push와 pop 모두 스택의 최상단에서만 이루어지기 때문에 O(1), 즉 상수 시간 안에 처리된다. 하지만 중간 요소를 직접 접근하지는 못한다. 무조건 top부터 꺼내야 하기 때문에 스택은 “순차적 접근만 가능한 구조”라는 한계가 있다. 이런 점 때문에 스택은 단독으로 대량의 데이터 탐색에 사용되기보다는, 흐름 제어, 중첩된 작업 처리, 임시 저장, 역순 처리(reverse) 등 특정 목적에 적합한 도구로 활용된다.

스택의 본질은 단순함이다. 구조는 매우 간단하지만, 프로그램의 흐름을 제어하거나 알고리즘의 과정을 관리하는 데 자주 등장하며, 실제 운영체제와 언어 내부에서도 필수적으로 사용된다. 스택을 확실하게 이해해두면 재귀 함수, DFS 탐색, 함수 호출, 계산기 알고리즘 같은 여러 개념을 자연스럽게 따라갈 수 있게 된다.