자료구조 : 큐와 덱

이번 포스팅에서는 중요한 자료구조인 큐와 덱에 대해 정리를 하려고 한다. 단, 이 게시글은 비전공자가 따로 공부하고 정리한 내용이기 때문에 틀린 내용이 있을 수 있다.

 

큐(Que)란?

---

큐는 먼저 들어온 데이터가 먼저 나가는 자료구조를 가리킨다. 실생활에서 가장 보기 쉬운 형태의 자료구조이며, 간단한 예로는 줄 서는 것을 볼 수 있다. 지하철에서 먼저 줄을 서는 사람이 먼저 타는 것처럼 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조로 보면 된다.

 

배열기반 큐 구현1( Two Pointer)

---

큐는 데이터의 가장 앞부분을 알려주는 First Index, 가장 뒷부분을 알려주는 Last Index가 있다. 이 두 Index의 이동을 이용해서 큐를 구현한다. 그렇다면 큐에서 각 쿼리가 발생했을 때, 이 Index들은 어떻게 움직이는 것이 효율적일까?

위의 이미지는 Que에서 데이터를 하나 빼는 연산을 수행한 후의 결과를 보여준다. 선입선출이기 때문에 가장 앞에 있던 A가 빠져나간 상황이다. 그런데 F는 그대로, L은 1칸씩 줄어들었다. 이게 의미하는 게 무엇일까? A라는 데이터를 삭제하고 뒤에 있던 B,C,D를 각각 한 칸씩 옮긴 셈이 되는 것이다. 이 경우, 큐를 할 때 마다 연산의 복잡도는 O(N)이 된다. 

성능 개선을 위해 큐에서 값을 뺄 경우, F가 움직이는 방식으로 큐의 인덱스를 관리해준다. 이 때는 데이터를 삭제 및 옮기기만 하면 되기 때문에 연산에 필요한 시간 복잡도는 O(1)로 표현할 수 있다.

 

배열기반 큐 구현2 (원형 큐)

---

배열기반의 큐를 구현할 때, 또 고려해야하는 부분은 데이터가 꽉 찼을 때 큐에 또 다른 데이터를 넣으면 어떻게 처리를 해야하는지에 대한 것이다. 이 때는 위처럼 원형 큐 형태로 큐를 구현하는 방법으로 해결한다. 즉, L이 배열의 전체 길이와 동일할 때 값이 들어온다면 저장될 위치를 0으로 바꿔주는 것이다. 

좌 : 큐가 꽉 참 / 우 : 큐가 비워짐

그런데 위처럼 원형으로 큐를 구현할 경우 문제점이 하나 발생한다. 바로 큐와 비었을 때와, 꽉 찼을 때를 구분할 수 없다는 것이다. 큐가 비었을 때와 꽉 찼을 때, F와 L의 상태가 동일하기 때문에 발생한다. 이 해결을 위한 방법은 큐에 할당된 배열을 꽉 채우지 않는다는 것이다. 

좌 : 큐가 꽉 참 / 우 : 큐가 비워짐

위의 이미지를 보면 바로 이해가 가능하다. 큐가 꽉 찼는지, 비워졌는지를 구별하기 위한 용도로 한 곳을 비워두는 것이다. 꽉 찼을 때는 F와 L이 다른 곳을 가리키고 있고, 비어져 있을 때는 F와 L이 같은 곳을 가리키고 있다. 

꽉 채운 후, 큐에서 데이터를 쫙 뽑아서 Empty 상태로 만들 경우, 다시 한번 F와 L이 같은 곳을 가리키는 것을 볼 수 있다. 즉, 배열 기반의 큐는 다음과 같은 논리로 만들 수 있다.

1. 배열 기반의 큐는 원형 큐 형태로 자료구조를 구현하되, 꽉 찬 것과 빈 것을 구별하기 위해 전체 배열 중 한 군데를 비워둔다.
2. 큐에 데이터를 넣을 때는, L이 가리키는 값을 하나 증가시키고, 그 위치에 데이터를 저장한다.
3. 큐에서 데이터를 뽑을 때는, F가 가리키는 값을 하나 증가시키고, 그 위치의 데이터를 삭제한다.
4. Index를 증가 시켰을 때, 배열의 길이보다 큰 값이 들어오면 시작점으로 초기화 시켜준다. 

링크드 리스트 기반의 큐 구현

---

링크드 리스트 기반의 장점은 앞서 배열 기반의 큐 구현 시 신경 썼던 원형 큐 부분을 신경쓰지 않아도 된다는 장점이 있다. 또한, 동적 메모리 할당 덕분에 메모리 관점에서도 이득이 있는 편이다. 

링크드 리스트로 큐를 구현할 때도 마찬가지로 F, L Index는 관리가 필요하다. 큐에 아무 것도 없을 때는 F가 Null을 가리킨다. 그리고 큐에 'A'라는 값이 처음으로 들어오면 F와 L은 모두 'A'를 가리킨다. 그리고 'B'라는 데이터가 들어오게 되면 F는 그대로 A를 가리키고, L은 B를 가리킨다. 배열 기반의 큐에서 F,L이 했던 역할을 여기서 동일하게 수행해준다. 

큐에서 데이터를 뽑을 때는 F가 현재 가리키고 있는 값의 다음 노드를 가리키게 하고, 가리키던 노드를 삭제해준다. 이렇게 데이터를 다 뽑아서 큐에 데이터가 없게 되면 F는 확정적으로 'Null'을 가리키고, L은 어떤 값을 가리키는지 알 수 없어진다. 그렇지만 아무 문제가 없다. 처음부터 F가 Null을 가리키는 상태가 큐가 빈 상태이기 때문에 아무 문제가 없다. 

 

 

덱 자료구조

---

Deque은 큐와 스택의 특성을 모두 가지고 있는 자료구조다. 즉, 앞에서 데이터를 넣고 뺄 수도 있고, 뒤에서 데이터를 넣고 뺄 수도 있다. 양방향 In/Out 특성을 가지는 덱의 특성은 당연한 이야기지만 양방향 링크드 리스트를 활용하여 구현하는 것이 가장 적절한 것으로 알려져 있다. 

위의 이미지처럼 Deque은 Head와 Tail이 이 자료구조의 시작과 끝을 가리켜주고, 그리고 각 노드가 서로를 가리키는 방식으로 표현할 수 있다. 예를 들어 끝에 자료를 넣는다면, 새 노드를 선언해주고 Tail이 가리키고 있던 뒷쪽 방향의 노드를 Null에서 새 노드로 수정해주고, Tail이 새 노드를 가리키는 방식으로 처리할 수 있다.