개발자 면접이나 전공 시험에서 가장 단골로 등장하는 자료구조 중 하나가 바로 스택(Stack)입니다. 이름부터가 '무더기', '쌓아 올리다'라는 뜻을 가진 스택은 컴퓨터의 동작 원리를 이해하는 데 있어 필수적인 개념입니다. 복잡한 수식이나 코드로 배우기 전에, 편의점에 가면 흔히 볼 수 있는 '프링글스 감자칩'을 떠올려 보세요. 스택의 모든 원리가 그 통 안에 담겨 있습니다.
1. 스택의 대원칙: 후입선출 (LIFO)
스택을 정의하는 단 하나의 규칙은 LIFO(Last In, First Out)입니다. 우리말로는 '후입선출', 즉 "가장 나중에 들어온 것이 가장 먼저 나간다"는 뜻입니다.
1-1. 프링글스 통의 비유
프링글스 통은 바닥이 막혀 있고 입구는 위쪽 하나뿐입니다. 1. Push (넣기): 공장에서 감자칩을 넣을 때, 가장 먼저 넣은 칩은 통의 맨 밑바닥에 깔립니다. 2. Pop (꺼내기): 우리가 먹으려고 뚜껑을 열면, 가장 맨 위에 있는 칩부터 꺼낼 수 있습니다. 이 칩은 공장에서 가장 나중에 넣은 칩입니다. 맨 밑바닥에 있는(가장 먼저 들어온) 칩을 먹으려면, 위에 쌓인 칩들을 다 먹어치워야만 가능합니다. 이것이 스택의 완벽한 예시입니다.
2. 스택, 도대체 어디에 쓸까?
"감자칩 꺼내는 순서가 뭐가 중요해?"라고 생각할 수 있지만, 컴퓨터 세계에서 '순서를 뒤집어야 하는 상황'이나 '가던 길을 되돌아가는 상황'에서는 스택이 신과 같은 존재입니다.
2-1. 웹 브라우저의 '뒤로 가기'
인터넷 서핑을 하다가 '뒤로 가기' 버튼을 누르면 바로 직전에 보던 페이지가 나옵니다. 브라우저는 여러분이 방문한 페이지 주소를 스택에 차곡차곡 쌓아둡니다(Push). 그리고 뒤로 가기를 누르면 가장 최근에 쌓인 주소를 꺼내서(Pop) 보여줍니다. 스택이 없다면 우리는 인터넷 미아가 될지도 모릅니다.
2-2. 문서 작업의 '실행 취소 (Ctrl+Z)'
보고서를 쓰다가 실수를 했을 때 Ctrl+Z를 누르면 마법처럼 이전 상태로 돌아갑니다. 워드 프로세서는 사용자의 키보드 입력 하나하나를 스택에 기록합니다. '취소' 명령이 떨어지면 스택의 맨 위(가장 최근 작업)를 제거하고 문서를 이전 상태로 되돌립니다.
2-3. 함수 호출 (Call Stack)
프로그래밍에서 함수 A가 함수 B를 호출하고, B가 C를 호출하는 경우를 생각해 봅시다. C가 끝나면 다시 B로, B가 끝나면 A로 정확히 돌아가야 합니다. 컴퓨터는 이 복귀 주소를 스택 메모리에 저장하여 관리합니다. 우리가 흔히 보는 에러 메시지 'Stack Overflow'는 이 스택 메모리가 꽉 찰 정도로 함수가 너무 많이(주로 무한 재귀) 호출되었을 때 터지는 비명입니다.
3. 스택의 시간 복잡도
스택은 데이터의 삽입과 삭제가 오직 맨 위(Top) 한 군데서만 일어납니다. 배열처럼 중간에 데이터를 끼워 넣기 위해 자리를 만들 필요가 없습니다. 따라서 데이터 넣기(Push)와 빼기(Pop) 모두 O(1)이라는 엄청나게 빠른 속도를 자랑합니다. 데이터가 100만 개 쌓여 있어도 속도는 똑같습니다.
1. 스택(Stack)은 입구가 하나뿐인 통과 같아서 LIFO(후입선출) 규칙을 따릅니다.
2. 데이터의 삽입(Push)과 삭제(Pop)가 O(1)로 매우 빠르며 효율적입니다.
3. 뒤로 가기, 실행 취소, 함수 호출 등 역순으로 되돌아가야 하는 기능 구현에 필수적입니다.