[Algorithm] 자료구조 - 스택 (Stack)

 

스택 (Stack)

---

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조

후입 선출(LIFO, Last-In-First-Out) 전략을 따르므로, 마지막에 추가한 원소가 먼저 제거된다

 

 

스택의 사용

---

1. 재귀(recursion) 호출

2. 후위 표현식(postfix expression)의 계산

3. 스택으로 구현하는 백트래킹(backtracking)

4. 트리와 그래프의 깊이 우선 탐색(DFS, Depth-First Search)

5. 10진수를 2진수로 변환하기

 

 

스택의 API와 시간 복잡도

---

- Push(k) : 스택의 맨 위에 값 k를 추가

- Pop() : 스택의 맨 위 원소 값을 반환한 뒤 제거

- Top() : 스택 맨위 원소의 값을 반환

- Size() : 스택의 원소 개수를 반환

- IsEmpty() : 스택이 비었으면 1을 반환

> 스택의 모든 연산의 시간 복잡도는 O(1)

 

 

💡 자료 구조 : codesyun.tistory.com/106

[Algorithm] 자료 구조(Data Structure) 란?