[자료구조] 스택(Stack)

1️⃣ 스택이란?

‘쌓아놓은 더미’를 의미하는 스택은 가장 최근에 들어온 데이터가 가장 최근에 들어온 데이터가 가장 먼저나가는 후입선출(LIFO: Last-In First-Out)구조를 가진 자료구조이다. 가장 가까운 예로, 스마트폰 뒤로 가기 키를 눌렀을 때 일어나는 동작을 수행하기 위해 스택이라는 자료구조를 사용한다.

2️⃣ 스택의 사용

스택은 입력 순서의 역순으로 출력이 될 때 효율적인 자료구조이다.
사용하는 예로는 undo 기능(ctrl + z), 재귀적 알고리즘, 웹브라우저 방문기록, 수식의 괄호 검사 등이 있다.

3️⃣ 스택의 ADT

• push : 스택에 데이터 삽입
• pop: 스택에서 데이터를 반환 후 삭제
• peek : 스택 맨 위에 있는 데이터 값 반환
• is_empty : 스택이 비었는지 확인
• is_full : 스택이 가득 차 있는지 확인

4️⃣ 스택의 시간복잡도

1. 검색 : 스택은 가장 위에 있는 데이터를 꺼낼 때 사용하기 용이한 자료구조로 검색이나 탐색은 잘 하지 않는다. 검색을 하면 처음부터 원하는 데이터를 찾을 때까지 탐색해야하므로 O(n)의 시간복잡도가 걸린다.
2. 삽입 : 스택은 들어온 자료구조는 가장 위에 올라가야하므로 O(1)의 시간복잡도가 걸린다.
3. 삭제 : 스택에서 삭제는 가장 위에 있는 자료구조이므로 삭제는 O(1)의 시간복잡도가 걸린다.