스택(Stack)과 큐(Queue)

스택과 큐는 가장 기본적인 자료구조이다. 

 

dfs, bfs를 구현하는데에도 쓰이며, 여러가지 알고리즘 기법이나 개념등에 적용되는 자료구조이다.

 

 

선입후출의 자료구조, 스택(Stack)

스택의 동작 과정 

 

스택은 바닥이 막혀있고 윗부분이 뚫려있는 자료구조 라고 생각하면 된다.

그래서 스택은 뚫려있는 위로만 데이터가 들어올 수 있다. 

 

그렇다면 데이터를 뺄때는??

똑같이 위로만 데이터가 나갈수가 있다. 

 

따라서 먼저 들어온 데이터들은 들어온 순서대로 아래로 깔리게 되고 

나중에 들어올수록 먼저 나가게된다. 

때문에 스택은 "선입후출"의 자료구조라고 부른다.

 

이러한 스택의 특성을 이용하여 대표적으로 이용되는 알고리즘이 dfs구현이다. 

 

물론 저러한 모양은 추상적으로 표현한 것일 뿐이며,

stack의 내부 구현을 타고 들어가면 배열로 구현이 되어있다. 

 

 

 

---

 

 

선입선출의 자료구조, 큐(Queue)

 

 

큐의 동작방식

 

 

스택과 달리 큐는 양쪽이 뚫려 있는 자료구조 라고 생각하면 된다. 

그래서 한쪽에서는 데이터가 입력만 되고 다른 한쪽에서는 데이터를 빼오기만 한다. 

 

그럼 데이터의 입력된 순서에 따라 출력은 어떻게 될까?

스택과 달리, 먼저 들어온 데이터가 먼저 나오게 된다. 

따라서 큐를 선입선출의 자료구조라고 부른다. 

 

큐의 이러한 특성을 이용하여 구현한 대표적인 알고리즘이 bfs이다.