[JAVA] 스택(Stack) 이란?

💡스택이란?

스택(Stack)은 한쪽(top)에서만 원소의 삽입과 삭제가 이루어지는 자료구조입니다.
특징적으로 LIFO(Last-In-First-Out), 즉 후입선출 구조를 가집니다.

예시:

push A
push B
push C
pop → C

💡 가장 먼저 들어간 A는 가장 마지막에 꺼내질 수 있다.

---

※ 스택의 주요 연산

연산	설명
push	스택 top에 데이터를 삽입
pop	top 데이터를 꺼내고 삭제
peek	top 데이터를 확인만
isEmpty	스택이 비었는지 확인
remove	삭제만 수행(pop과 다르게 값 반환 x)

※ ADT 형식 예시

createStack()
push(item)
pop()
peek()
isEmpty()
remove()

---

※ 스택의 구현 방식

① 배열(Array)을 이용한 순차적 구현

• top 값으로 가장 위를 가리킨다.

• 초기 top = -1

• push 시 top++

• pop 시 top--

구조:

Stack[0] [1] [2] ... [n]
   ↑
  top

- 장점: 간단함
- 단점: 크기 제한 존재

② 연결리스트(Linked List)를 이용한 구현

• 메모리 동적 할당 가능

• top이 연결 리스트의 head 역할

구조:

top → Node(data, link) → Node → ...

• push: 새 노드를 top 앞에 삽입
• pop: top을 삭제 후 link를 top으로 변경
  
  - 장점: 크기 제한 없음
  - 단점: 구현 약간 복잡

---

※ 스택의 대표적 활용

✔ 수식의 괄호 검사

{ [ ( ) ] }

• 여는 괄호 push

• 닫는 괄호 pop으로 비교

• empty & mismatch 판별

---

✔ 후위 표기법(Postfix) 계산

중위: A + B C
후위: A B C +

스택 단계:

1. 피연산자 push

2. 연산자 만나면 pop 두 번 → 연산 → push

---

✔ 실행 시간 스택 (추가 응용)

함수 호출 → 스택 push
함수 종료 → pop

• 활성화 레코드 관리

• 재귀 호출 시 스택 증가

---

✔ 미로 탐색 (DFS 방식)

좌표, 방향을 스택에 저장하며 백트래킹

---

📗 스택의 특징 정리

특징	설명
LIFO	후입선출
top	한쪽 끝에서 삽입/삭제
push/pop	주 연산
구현	배열 / 연결리스트
활용	수식, 괄호, 후위 계산, 재귀, 미로