자료구조 — 스택(Stack) 개념 정리

---

1. 스택이란?

스택(Stack) 은 가장 나중에 들어온 데이터가 가장 먼저 나간다 자료구조이다.

이를 선입후출 또는 LIFO(Last In First Out) 라고 한다.

나중에 들어온 데이터
        ↓
      [ C ] ← 가장 먼저 나감
      [ B ]
      [ A ]
        ↑
먼저 들어온 데이터

쉽게 생각하면 박스를 차곡차곡 쌓는 구조와 비슷하다.

박스를 여러 개 쌓았다면 가장 위에 있는 박스부터 꺼내야 한다.

---

2. 스택의 핵심 연산

스택의 기본 연산은 두 가지이다.

Push

데이터를 스택의 가장 위에 넣는다.

삽입

Pop

스택의 가장 위에 있는 데이터를 꺼낸다.

삭제

즉, 데이터를 넣는 위치와 꺼내는 위치가 같다.

---

3. Python에서 스택 사용하기

Python에서는 별도의 스택 자료구조를 만들 필요 없이 list를 이용하면 된다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

데이터를 꺼낼 때는 pop()을 사용한다.

stack.pop()

가장 마지막에 들어온 데이터가 먼저 제거된다.

append() → 가장 뒤에 데이터 추가
pop()    → 가장 뒤의 데이터 제거

---

4. 스택의 특징

스택은 가장 최근에 저장한 데이터를 먼저 처리해야 하는 상황에서 유용하다.

핵심은 다음 한 문장으로 기억하면 된다.

가장 나중에 들어온 것이 가장 먼저 나온다.

---

5. 스택과 함수 호출

함수가 다른 함수를 호출하면 현재 함수의 실행 정보가 메모리에 저장된다.

함수 A 실행
↓
함수 B 호출
↓
A의 실행 상태 저장
↓
B 실행
↓
B 종료
↓
A로 복귀

가장 마지막에 호출된 함수가 가장 먼저 종료된다.

이 구조는 스택의 LIFO와 동일하다.

그래서 재귀 함수와 DFS를 이해할 때 스택 개념이 중요하다.

---

6. 스택과 DFS의 관계

DFS는 한 방향으로 최대한 깊게 탐색한다.

더 이상 갈 곳이 없으면 가장 최근에 방문했던 위치로 돌아와야 한다.

현재 노드
↓
다음 노드
↓
다음 노드
↓
막힘
↓
가장 최근 노드로 되돌아감

즉,

최근에 방문한 곳을 먼저 다시 확인

해야 하기 때문에 스택 구조와 잘 맞는다.

---

핵심 정리

Stack
=
LIFO
=
Last In First Out
=
가장 나중에 들어온 데이터가 먼저 나감

Python

append()
pop()

주요 연관 개념

스택
├── 함수 호출
├── 재귀 함수
└── DFS

---

한 줄 요약

스택은 가장 최근에 들어온 데이터를 가장 먼저 처리하는 LIFO 자료구조이다.