[자료구조] 스택(Stack)이란?

개요

---

Stack 자료구조란 요소들이 후입선출(Last-In First-Out)되는 방식의 자료구조이다.

말 그대로 가장 늦게 들어온 요소가 가장 처음으로 나간다.

---

구조

---

사진 1

스택은 기본적으로 사진 1과 같은 구조를 가진다.

아래에서부터 요소가 쌓이며 Top 포인터는 가장 위에 있는 요소를 가르킨다.

 

operation으로는 대표적으로 Push와 Pop이 있다.

사진 2

Push operation은 스택에 아이템을 추가한다.

사진 2는 사진 1에서 5를 push했을 때의 예시 사진이다.

 

사진 3

Pop operation은 스택에서 아이템을 제거한다.

사진 3은 사진 2에서 5를 pop하는 예시이다.

 

사진 2와 3에서, Top 포인터가 가르키는 위치는 항상 스택의 맨 위 임을 알 수 있다.

---

어디에서 사용하는가?

---

사진 4

위 사진은 VS code에서의 괄호이다.

스택을 사용해서 괄호 매칭 문제를 해결할 수 있다.

현재 사진에서 괄호의 문자열은 { { { } } } 이다.

이제 여는 괄호는 스택에 Push하고 닫는 괄호 문자열을 만날 시 여는 괄호를 스택에서 하나씩 Pop을 하면서 괄호 매칭에 대해 알아볼 것이다.

사진 5

사진 4의 괄호들을 스택을 이용해서 표현해 보았다.

여는 괄호 문자열을 받을 시 스택에 Push하고, 닫는 괄호를 받을 시 여는 괄호 문자를 하나씩 Pop한다.

 

결과적으로 마지막에 스택이 비어있다면 괄호가 잘 맞는것이고 스택이 비어있지 않다면 괄호가 맞지 않는 것이다.