스택(Stack)의 핵심, LIFO 원리 이해하기 (맛있는 프링글스 비유)
우리가 컴퓨터나 스마트폰을 사용하면서 무언가 실수를 했을 때, 가장 본능적으로 누르는 단축키가 있습니다. 바로 '실행 취소'를 뜻하는 Ctrl + Z입니다. 문서를 작성하다가 실수로 글자를 지웠을 때, 이 마법의 단축키를 누르면 방금 지웠던 글자가 마치 시간을 되돌린 것처럼 다시 나타납니다. 웹 브라우저에서 '뒤로 가기' 버튼을 누를 때도 마찬가지입니다. 컴퓨터는 도대체 어떻게 우리가 가장 최근에 했던 행동들을 순서대로 기억하고, 또 역순으로 되돌려주는 것일까요? 그 비밀의 열쇠를 쥐고 있는 것이 바로 컴퓨터 과학의 가장 위대한 발명품 중 하나인 '스택(Stack)'이라는 자료구조입니다. 복잡한 프로그래밍 이론을 꺼내기 전에, 우리에게 아주 친숙한 간식인 '프링글스' 감자칩 통을 통해 스택의 놀라운 원리를 아주 쉽고 직관적으로 파헤쳐 보겠습니다.
1. 스택(Stack)이란 무엇인가?
스택은 사전적인 의미로 '무더기', '더미', '쌓아 올리다'라는 뜻을 가지고 있습니다. 컴퓨터 공학에서는 데이터를 순서대로 차곡차곡 쌓아 올리는 형태의 선형 자료구조(Linear Data Structure)를 의미합니다. 스택 구조가 가진 가장 치명적이고도 중요한 특징은 바로 데이터가 들어가고 나가는 입구가 단 하나뿐이라는 사실입니다. 바닥이 꽉 막혀 있고, 오직 위쪽으로만 구멍이 뚫려 있는 깊은 원통을 상상하시면 정확합니다.
1-1. LIFO (Last-In, First-Out) 원리: 프링글스의 법칙
스택을 지배하는 단 하나의 절대적인 규칙은 바로 후입선출(LIFO)입니다. 우리말로 직역하면 "가장 나중에 들어온 놈이 가장 먼저 나간다"는 뜻입니다. 이 개념이 조금 낯설게 느껴지신다면, 편의점에서 흔히 볼 수 있는 원통형 감자칩 '프링글스'를 떠올려 보십시오.
- 데이터를 넣을 때 (공장의 입장): 감자칩 공장에서 빈 프링글스 통에 감자칩을 채워 넣습니다. 가장 먼저 튀겨진 감자칩은 통의 맨 밑바닥에 깔리게 됩니다. 그리고 그 위로 두 번째, 세 번째 칩이 차곡차곡 쌓여, 가장 마지막에 튀겨진 칩이 통의 맨 꼭대기에 위치하게 됩니다.
- 데이터를 꺼낼 때 (소비자의 입장): 우리가 뚜껑을 열고 감자칩을 먹으려고 합니다. 맨 밑바닥에 있는(가장 먼저 들어간) 칩을 먼저 꺼내 먹을 수 있나요? 불가능합니다. 우리는 반드시 맨 위에 있는, 즉 공장에서 가장 마지막(나중에) 들어간 칩부터 순서대로 꺼내 먹어야만 합니다.
이것이 바로 완벽한 스택의 원리입니다. 입구와 출구가 동일한 하나의 통로로 이루어져 있기 때문에, 데이터의 순서가 자연스럽게 뒤집히는(Reverse) 효과를 가져오게 됩니다.
2. 스택을 조작하는 핵심 명령어 (Operations)
스택을 프로그래밍 코드로 구현하고 다룰 때 사용되는 국제 표준과도 같은 세 가지 주요 명령어가 있습니다.
2-1. Push (푸시)와 Pop (팝)
스택에 데이터를 조작하는 행위는 매우 직관적입니다. 1. Push (밀어 넣기): 스택의 맨 위(Top)에 새로운 데이터를 추가하는 작업입니다. 프링글스 통에 새로운 감자칩을 하나 얹는 행위와 같습니다. 만약 스택의 용량이 꽉 차 있는데 데이터를 억지로 더 밀어 넣으려고 하면 내용물이 밖으로 넘쳐흐르는데, 이 에러를 개발자들이 가장 두려워하는 '스택 오버플로우(Stack Overflow)'라고 부릅니다. 2. Pop (꺼내기): 스택의 맨 위에 있는 데이터를 완전히 꺼내서 제거하는 작업입니다. 우리가 맨 위의 감자칩을 꺼내 먹는 행위입니다. 만약 통이 텅 비어있는데 칩을 꺼내려고 시도하면 '스택 언더플로우(Stack Underflow)'라는 오류가 발생합니다.
2-2. Peek (피크)
가끔은 데이터를 밖으로 꺼내서(Pop) 없애버리지 않고, 단순히 "지금 맨 위에 무슨 데이터가 있지?" 하고 살짝 들여다보기만 해야 할 때가 있습니다. 이처럼 스택의 최상단(Top) 데이터를 훼손하지 않고 확인만 하는 안전한 명령어를 Peek라고 부릅니다.
3. 스택은 언제, 어디에 쓰일까? (실무 활용 사례)
스택은 단순히 이론적인 개념에 머물지 않고, 우리가 사용하는 모든 운영체제와 소프트웨어의 가장 깊은 곳에서 핵심 엔진으로 동작하고 있습니다.
3-1. 함수 호출의 관리 (Call Stack)
여러분이 작성한 프로그램은 여러 개의 함수(기능)가 꼬리에 꼬리를 물고 실행됩니다. A 함수가 실행되다가 B 함수를 부르고, B 함수가 다시 C 함수를 부릅니다. 이때 C 함수의 작업이 끝나면 컴퓨터는 귀신같이 B 함수로 다시 돌아갑니다. 어떻게 길을 잃지 않는 걸까요? 컴퓨터는 함수를 부를 때마다 "내가 나중에 돌아와야 할 원래 위치(복귀 주소)"를 콜 스택(Call Stack)이라는 메모리 공간에 Push 해둡니다. 작업이 끝나면 스택에서 주소를 Pop 하여 정확한 위치로 되돌아가는 것입니다. 스택 구조가 없었다면 현대의 모든 프로그래밍 언어는 붕괴했을 것입니다.
3-2. 깊이 우선 탐색 (DFS) 알고리즘
복잡한 미로 찾기 게임을 할 때, 갈림길이 나오면 일단 막다른 길이 나올 때까지 한쪽 방향으로 끝까지 파고들어 가는 전략을 깊이 우선 탐색(DFS)이라고 합니다. 막다른 길에 부딪히면 가장 최근에 지나온 갈림길로 되돌아가야 하는데, 이때 '가장 최근의 방문 기록'을 저장하고 꺼내어 쓰는 데 스택이 완벽하게 활용됩니다.
1. 스택(Stack)은 데이터의 입구와 출구가 하나로 통일된 선형 자료구조입니다.
2. 가장 나중에 들어온 데이터가 가장 먼저 나가는 LIFO(후입선출)의 철저한 원칙을 따릅니다.
3. 데이터 삽입(Push)과 삭제(Pop)가 매우 빠르며, 뒤로 가기, 실행 취소, 콜 스택 등 상태를 되돌리는 기능에 필수적입니다.