자료구조 - 스택(Stack)

🎁 스택(Stack) 완전 정복

"책을 한 권씩 쌓았다가, 위에서부터 하나씩 꺼내본 적 있죠?"
스택은 바로 그런 구조예요.

📌 스택이란?

스택(Stack)은 데이터를 한쪽 방향으로만 넣고 꺼내는
선형 자료구조(linear data structure) 입니다.

가장 마지막에 넣은 데이터가
가장 먼저 나오는 구조

🔁 LIFO 구조

용어	뜻
LIFO	Last In, First Out – 나중에 들어온 게 먼저 나감

🎯 이렇게 생각하면 쉬워요

🥔 프링글스 통

👀 프링글스 과자 아시나요? 원통 모양의 뚜껑이 있는 통이랍니다 🥫

• 과자는 한 방향(위에서)으로만 꺼낼 수 있어요
• 가장 나중에 넣은 과자가 제일 먼저 나와요
• 통 아래에 있는 과자를 꺼내려면?
  👉 윗 과자들을 먼저 다 먹어야 해요!

🍟 그래서 프링글스는 스택이에요: Last In, First Out

---

🧱 스택의 기본 동작

연산	설명
Push	스택의 맨 위에 데이터를 추가
Pop	스택의 맨 위 데이터를 꺼냄 (삭제됨)
Peek 또는 Top	가장 위에 있는 데이터를 확인만 (삭제 ❌)
isEmpty	스택이 비어 있는지 확인

---

📤 Pop 할 때 인덱스는?

✅ 스택의 구현 방식에 따라 다릅니다.

구현 방식	인덱스 처리 방식
배열 기반	top 포인터가 한 칸 줄어듦 (데이터는 있어도 무시됨)
연결 리스트 기반	노드를 제거하며 연결을 끊음

즉, pop() 시 인덱스 자체가 사라지는 게 아니라,
top 위치가 변경되면서 더 이상 접근하지 않게 되는 거예요.

---

🧮 인덱스와 메모리 상의 변화(배열기반, 크기5)

▶️ 실행 1: Push(5) → Push(8) → Push(10)

🔽 실행 2: Pop() → top 감소

• 10은 물리적으로 삭제되지 않았지만, top이 줄면서 무시됩니다.
• 즉, "접근할 수 없는 상태"가 된 거예요!
• 이후 Push하면 index 2부터 다시 채워지게 돼요.

🔆 배열 기반 스택의 핵심 특징 정리

구분	설명
고정된 크기	배열은 크기를 미리 정해둬야 해요. 다 채우면 더 이상 push() 불가!
빠른 접근	인덱스를 통해 직접 접근하므로, 조회는 매우 빠릅니다. (O(1))
top 인덱스	배열의 어느 칸까지 데이터가 있는지를 나타냄. 새로운 값은 top + 1에 쌓여요.
데이터 삭제	pop() 시 실제 메모리는 지워지지 않고, 단순히 top 인덱스만 감소돼요.
메모리 낭비 가능성	배열을 너무 크게 만들면 낭비, 너무 작게 만들면 초과(push 불가) 문제가 생겨요.
오버헤드 없음	연결 리스트처럼 포인터(next)가 없기 때문에 상대적으로 가볍고 구조가 단순해요.

---

🪢 연결 리스트 기반 스택, 어떻게 생겼나요?

배열 기반 스택은 공간이 고정되어 있죠?
하지만 연결 리스트는 필요한 만큼 동적으로 공간을 연결해가며 스택을 만들 수 있어요.

▶️ 실행 1: Push(5) → Push(8) → Push(10)

• 각각의 노드는 데이터(data) 와 다음 노드를 가리키는 참조(next:주소값) 를 가지고 있어요.

• 가장 최근에 추가된 10이 top을 가리킵니다.

🔽 실행 2: Pop() → top 이동

• top이 아래로 이동하면서 10번 노드와의 연결이 끊겨요.

• 10은 다시 참조되지 않기 때문에 '더 이상 사용되지 않는 상태'가 됩니다.

💡 자바나 파이썬 같은 언어에서는 이런 노드를 가비지 컬렉터(GC)가 나중에 정리해줘요.

🔆 연결 리스트 스택의 핵심 특징 정리

구분	설명
유연한 크기	배열처럼 정해진 크기가 없고, 필요한 만큼 동적으로 늘어납니다.
빠른 삽입/삭제	항상 top에서 삽입/삭제가 일어나기 때문에, 시간 복잡도는 O(1)입니다.
top 포인터	스택의 가장 위를 가리키며, 마지막으로 추가된 노드를 참조합니다.
메모리 구조	각 노드는 자기 다음 노드의 주소만 알고 있어요 (next)

---

💡 스택은 어디에 쓰일까?

활용 분야	설명
함수 호출 관리	호출 스택(Call Stack) (재귀함수 등)
실행 취소(Undo)	이전 상태를 순서대로 저장 후 되돌림
괄호 짝 검사	여는 괄호 Push, 닫는 괄호 Pop
DFS 알고리즘	깊이 우선 탐색(Depth First Search)

---

🎀 요약!

스택은 후입선출(LIFO) 구조로
나중에 넣은 데이터가 먼저 나오는 자료구조예요.

실생활의 "쌓기 → 꺼내기" 개념과 매우 닮아 있어서
초보자도 쉽게 이해할 수 있는 구조랍니다 😊