[자료구조] Stack

✅ 스택 (Stack)

❕ 기본 개념 

- 데이터를 1열로 나열하는 데이터 구조

- 나중에 넣은 것을 먼저 꺼내는 Last In First Out (LIFO) 구조

- 즉, 새롭게 추가한 데이터에만 접근할 수 있음

 

마치 책을 차곡차곡 쌓아놓거나, 팬케이크를 겹겹이 쌓아놨을 때 맨 위의 것부터 집을 수 있는 것과 같은 구조

 

 

❓ 리스트나 배열도 마찬가지로 1열로 나열한 데이터 구조인데? 

- 리스트/배열과 다르게 스택은 데이터 추가나 삭제가 단방향으로만 가능함

- 데이터 접근도 스택의 가장 위에 있는 데이터만 가능함 (indexing 불가)

- 그래서 중간에 있는 데이터가 필요하다면 해당 데이터가 제일 위로 올 때까지 데이터를 pop 해야함

✔ 활용 예시 

단방향 조작만 가능하기 때문에 불편하다고 생각할 수 있지만,

항상 최신 데이터만 접근해야 하는 상황에서는 편리하게 사용된다.

 

- 웹 브라우저 뒤로가기, 문서 작업 Ctrl + Z

- 깊이 우선 탐색(DFS)에서 탐색 후보 관리에 스택 사용 가능

- 후위표기식 계산 (참고: 후위표기식 변환 계산기)

 

✔ 문제 예시 

ex. (AB (C (DE) F) (G ((H) IJ) K)) 라는 문자열의 괄호 대응 관계 계산

☞ 왼쪽부터 문자열을 읽어서 왼쪽 괄호가 나올 때마다 그 위치를 스택에 푸시

☞ 오른쪽 괄호가 나오면 pop해서 해당 괄호에 대응하는 왼쪽 괄호 위치 파악

 

 

참고자료

「알고리즘 도감」 中 1-4 스택

https://colab.research.google.com/drive/1ufsEvPZovKdUcW-_-4-VkbfBjAFRGzJv