우리가 컴퓨터를 사용하면서 하루에도 수십 번씩 누르는 단축키가 있습니다. 바로 실수를 되돌려주는 마법의 키, 'Ctrl + Z (실행 취소)'입니다. 또한 웹 서핑을 하다가 이전 페이지로 돌아가고 싶을 때 누르는 '뒤로 가기' 버튼도 있습니다. 이처럼 가장 최근에 했던 작업을 기억하고, 역순으로 되돌가는 기능들은 어떤 원리로 작동하는 걸까요? 그 이면에는 컴퓨터 과학에서 가장 기초적이면서도 핵심적인 자료구조인 스택(Stack)이 숨어 있습니다. 오늘은 스택의 작동 원리를 누구나 아는 과자, '프링글스'에 빗대어 완벽하게 이해해 보겠습니다.
1. 스택(Stack)이란 무엇인가?
스택(Stack)은 사전적 의미로 '무더기', '쌓아 올리다'라는 뜻을 가지고 있습니다. 데이터를 순서대로 차곡차곡 쌓아 올리는 형태의 선형 자료구조(Linear Data Structure)입니다. 스택의 가장 큰 특징은 바닥이 막혀있고 천장만 뚫려있는 구조라는 점입니다. 따라서 데이터를 넣거나 뺄 수 있는 통로가 오직 한 곳(Top)뿐입니다.
1-1. LIFO (Last In, First Out) 원리
스택을 관통하는 절대적인 규칙은 바로 후입선출(LIFO)입니다. "가장 나중에 들어온 놈이 가장 먼저 나간다"는 뜻입니다. 이 개념이 어렵게 느껴진다면 편의점에서 파는 원통형 감자칩, 프링글스를 상상해 보세요.
- 입력: 공장에서 감자칩을 통에 넣을 때, 가장 먼저 넣은 칩은 통의 맨 밑바닥에 깔리게 됩니다. 그리고 마지막에 넣은 칩이 맨 위에 위치합니다.
- 출력: 우리가 뚜껑을 열고 감자칩을 먹을 때, 맨 밑에 있는(가장 먼저 들어간) 칩을 바로 꺼낼 수 있나요? 불가능합니다. 반드시 맨 위에 있는(가장 나중에 들어간) 칩부터 순서대로 꺼내 먹어야 합니다.
이것이 바로 스택의 LIFO 원리입니다. 입구와 출구가 동일하기 때문에 데이터의 순서가 자연스럽게 뒤집히는 효과가 있습니다.
2. 스택의 핵심 기능과 시간 복잡도
스택을 프로그래밍적으로 구현할 때 사용되는 주요 명령어는 다음과 같습니다.
2-1. 주요 연산 (Operations)
- Push(푸시): 스택의 맨 위(Top)에 새로운 데이터를 추가하는 작업입니다. 데이터가 꽉 차 있는데 계속 넣으려 하면 넘치게 되는데, 이를 스택 오버플로우(Stack Overflow)라고 합니다.
- Pop(팝): 스택의 맨 위에 있는 데이터를 꺼내서 제거하는 작업입니다. 비어있는 스택에서 꺼내려 하면 스택 언더플로우(Stack Underflow)가 발생합니다.
- Peek(피크): 데이터를 꺼내지는 않고, 맨 위에 무엇이 있는지 확인만 하는 작업입니다.
2-2. 압도적인 효율성: O(1)
스택은 데이터의 삽입과 삭제가 오직 '맨 위(Top)'에서만 일어납니다. 배열처럼 중간에 있는 데이터를 건드리기 위해 다른 데이터들을 밀거나 당길 필요가 전혀 없습니다. 따라서 Push와 Pop 연산 모두 O(1)이라는 아주 빠른 상수 시간 복잡도를 가집니다. 데이터가 100만 개 쌓여 있어도, 맨 위의 데이터를 가져오는 속도는 즉시 이루어집니다.
3. 개발자가 스택을 반드시 알아야 하는 이유 (활용 사례)
스택은 단순한 이론이 아닙니다. 프로그래밍 언어의 작동 방식 그 자체를 지탱하고 있습니다.
3-1. 함수 호출 스택 (Call Stack)
우리가 프로그래밍을 할 때 함수 A가 함수 B를 호출하고, 함수 B가 함수 C를 호출했다고 가정해 봅시다. 함수 C의 작업이 끝나면 컴퓨터는 어떻게 정확하게 함수 B로 다시 돌아갈까요? 컴퓨터는 함수를 호출할 때마다 복귀 주소와 지역 변수를 '스택' 메모리 영역에 쌓아둡니다(Push). 그리고 함수가 종료되면 스택에서 제거(Pop)하며 이전 위치로 돌아갑니다. 이 구조 덕분에 복잡한 프로그램이 순서대로 실행될 수 있는 것입니다.
3-2. 문자열 역순 출력 및 괄호 검사
"Hello"라는 단어를 뒤집어 "olleH"로 만들고 싶을 때, 스택에 H, e, l, l, o 순서대로 넣었다가 다시 하나씩 꺼내면 자연스럽게 역순이 됩니다. 또한, 코딩할 때 `(( ))` 처럼 괄호의 짝이 맞는지 검사하는 알고리즘도 스택을 이용해 여는 괄호를 넣고 닫는 괄호를 만날 때마다 빼는 방식으로 구현합니다.
3-3. 웹 브라우저의 방문 기록
여러분이 이 글을 보다가 다른 링크를 클릭하면 현재 페이지 주소가 스택에 저장(Push)됩니다. 그리고 '뒤로 가기' 버튼을 누르면 스택에서 가장 최근 주소를 꺼내(Pop) 그곳으로 이동합니다. 앞으로 가기, 뒤로 가기 모두 스택을 활용한 대표적인 기능입니다.
1. 스택은 한쪽 끝으로만 입출력이 가능한 LIFO(후입선출) 구조입니다.
2. 데이터의 삽입(Push)과 삭제(Pop)가 매우 빠르며(O(1)), 순서를 역순으로 처리할 때 유용합니다.
3. 실행 취소(Ctrl+Z), 웹 브라우저 뒤로 가기, 함수 호출 관리 등 '되돌리기'가 필요한 모든 곳에 사용됩니다.