스택과 큐 (+ 깊이 우선 탐색, 너비 우선 탐색)

 

 

 

---

 

스택은 무엇이고
큐는 무엇인가?

 

 

---

 

 

 

 

스택 (Stack)

 

--

스택은

후입선출 (LIFO, Last In First Out) 자료 구조로

마지막으로 들어간 데이터가 맨 처음으로 나가는 구조다.

 

이때 데이터를 담는 연산(데이터 추가)을 'push', 담긴 데이터를 꺼내는 연산(데이터 삭제 후 반환)을 'pop'이라고 부른다.

 

스택의 주요 연산

• 푸시(push)  :  스택의 맨 위에 새로운 데이터 삽입
• 팝(pop)  :  스택의 맨 위에 있는 데이터 삭제 후 반환
• 피크(peek) 또는 탑(top)  :  스택의 맨 위에 있는 데이터를 삭제하지 않고 반환
• isEmpty  :  스택이 비어 있는지 확인

 

 

배열이나 연결 리스트 중 어느 쪽이든 스택을 구현할 수 있다.

 

 

배열로 스택 표현하기

 

 

리스트로 스택 표현하기

 

리스트에서는 Top이 리스트의 맨 앞쪽을 의미한다.
즉, push 또는 pop을 할 때마다 각각의 노드 포인터를 갱신하고, 스택의 Top 포인터도 갱신해야 한다.

--

 

 

 

 

큐 (queue)

 

--

큐는

선입선출(FIFO, First In First Out) 자료 구조로

먼저 들어간 데이터가 먼저 나가는 구조다.

 

이때 데이터를 담는 연산(데이터 추가)을 'enqueue', 담긴 데이터를 꺼내는 연산(데이터 삭제 후 반환)을 'depueue'이라고 부른다.

 

큐의 주요 연산

• 엔큐(enqueue)  :  큐의 맨 뒤에 새로운 데이터 삽입
• 디큐(dequeue)  :  큐의 맨 앞에 있는 데이터를 삭제 후 반환
• 피크(peek) 또는 front  :  큐의 맨 앞에 있는 데이터를 삭제하지 않고 반환
• isEmpty  :  큐가 비어 있는지 확인

 

 

배열이나 연결 리스트 중 어느 쪽이든 큐를 구현할 수 있다.

 

 

배열로 큐 표현하기

 

 

이렇게 고정된 배열에서 'dequeue'를 수행하면 배열의 앞부분에 빈 공간이 누적될 수 있다는 단점이 존재한다.

이러한 문제를 해결하기 위해서는 'Front'부터 'Back'까지의 데이터를 다시 앞으로 이동시켜야 하지만

이렇게 이동시키는 작업에는 비용이 많이 들게 된다.

그렇게 때문에 비용을 최소화 하기 위해 배열의 맨 뒤에서 다시 맨 앞으로 순환시키면서 데이터를 배열하는 방법을 사용해야 한다.

다만 순환시키는 구조를 구성할 때 'enqueue' 또는 'dequeue' 작업을 할 때 인덱스가 배열의 끝을 넘어가는 것을 주의 깊게 처리해야 한다.

 

 

위 그림처럼 배열의 맨 처음 부분에 Back이 추가된다.

이렇게 순환하는 구조를 하면 'Front'와 "back" 위치가 뒤집어지기 때문에 약간은 복잡해질 수 있지만

데이터를 이동하는 높은 비용을 피할 수 있다.

 

 

리스트로 큐 표현하기

--

 

 

 

 

깊이 우선 탐색 (DFS, Depth-First Search)

 

--

깊이 우선 탐색은

막다른 골목에 도달할 때까지 한 가지 경로를 깊이 탐색을 진행하고 막다른 골목에 도달할 때까지 목푯값을 탐색하지 못하면 마지막으로 방문했던 분기로 돌아가 다음 가능성을 확인하는 것을 계속 반복하는 방식이다.

 

이는 재귀 또는 스택을 사용하여 구현할 수 있다.

 

스택을 사용하여

앞으로 탐색해야 할 목록을 유지하면서

다음으로 시도할 대상으로 항상 최근에 삽입한 가능성을 가장 먼저 선택한다.

 

 

1. A - B - C - D 까지 깊이 탐색 후
2. 이전 분기였던 C로 돌아와 다음 탐색을 진행한다.
3. A - B - C - E 까지 탐색 후
4. 다시 C로 돌아오고 다음 탐색할 요소가 없기 때문에 C 이전인 B로 돌아간다. B 또한 다음 탐색할 요소가 없기 때문에 A로 돌아가서 다음 탐색을 진행한다.

이러한 방식을 반복하여 탐색하는 방식을 깊이 우선 탐색이라고 부른다.

--

 

 

 

 

너비 우선 탐색 (BFS, Breadth-First Search)

 

--

너비 우선 탐색은

깊이 우선 탐색과는 다르게 더 깊은 단계를 탐색하기 전에 같은 깊이의 여러 다른 방향으로 탐색을 뻗어나간다.

 

이는 큐를 사용하여 구현할 수 있다.

 

--