[자료구조] Stack 개념

스택(Stack)이란?

• 가장 마지막에 삽입된 데이터가 가장 처음으로 출력되기 때문에 Last In First Out으로 LIFO(리포) 구조라고 하며 후입선출 형태의 선형 자료 구조
• 데이터가 삽입되면 가장 안쪽부터 차곡차곡 쌓여, 꺼낼 때는 역순으로 꺼내지게 됨

---

스택의 특징

• 스택의 데이터는 top을 통해서만 접근 가능
• 스택에 데이터를 삽입할 때는 top 위에 데이터를 추가(push)하고, top의 위치를 한칸 위로 변경

• 스택에 데이터를 삭제할 때는 top에 위치한 데이터를 삭제(pop)하고, top의 위치를 한칸 아래로 변경

---

스택 주의 사항

• 스택의 데이터가 꽉 찼을 때 데이터를 삽입(push)하게 되면, 스택 오버플로우(Stack Overflow)가 발생
• 스택이 비어있는 상태일 때 데이터를 삭제(pop)하게 되면, 스택 언더플로우(Stack Underflow)가 발생

 

스택 오버플로우 해결책

• 스택이 고정된 크기일 경우 push를 하게 되면 Stack Overflow가 발생
• 이것을 해결하기 위해서는 스택의 크기를 동적으로 확장시키면 됨
• 예를들어 ArrayList처럼 스택이 가득 찼을 때 1.5배 ~ 2배로 늘리고 기존 요소를 새 배열로 복사
• 단, 동적 크기 조정은 메모리와 시간 비용이 발생하기 때문에 스택이 무한히 커지지 않도록 유의

 

 

스택 언더플로우 해결책

• 스택이 비어있을 때 pop 또는 peek을 하게 되면 Stack Underflow가 발생
• 이를 해결하기 위해서는 pop 또는 peek 연산을 하기 전 스택이 비어있는 지 확인하고, 비어있을 경우 예외를 발생하거나 사용자에게 알림
  • isEmpty() 메서드를 사용하여 스택이 비어있는지 확인 가능

---

스택의 활용 예시

• 웹 브라우저 방문 기록(뒤로 가기)
• 실행 취소(undo, Ctrl + Z)
• 역순 문자열 만들기
• 후위 표기법 계산
• 수식의 괄호 검사(연산자 우선 순위 표현을 위한 괄호 검사)