[뇌를 자극하는 알고리즘] 3. 큐

큐?

입력과 출력 창구가 따로 존재

먼저 들어가면 먼저 나오는 FIFO(First In First Out) 즉 선입선출

밀려드는 데이터를 '보관할 장소', '기다리는 줄'

입력 데이터가 폭주시 먼저 처리하는 데이터 작업이 끝나면 큐에 보관되어 있던 데이터를 하나씩 꺼내 처리해 데이터의 유실을 막음.(Buffer) 

 

3.2 큐의 주요 기능: 삽입과 제거

큐의 가장 앞 요소: 전단(Front) - 노드 제거(Dequeue) 

가장 마지막 요소: 후단(Rear)- 노드 삽입(Enqueue)

제거

삽입

3.3 끝은 새로운 시작이다: 순환 큐 

순환 큐를 소개합니다.

위와 같은 큐 배열은 전단을 제거한 후 나머지 요소들을 한 칸씩 앞으로 옮기는데 비용이 든다.

위와 같은 큐 배열은 배열 내의 요소를 옯기는 대신 변경된 전단의 위치만 관리, 후단을 가리키는 변수도 도입해서 삽입이 일어날 때마다 변경되는 후단의 위치를 관리한 것. 후단을 가리키는 변수에 실제 후단의 위치보다 1을 더한 값을 가짐.

제거 연산을 수행할수록 큐의 가용 용량도 줄어든다는 문제가 있음.

 

위와 같은 큐의 문제를 해결하기 위해 순환 큐를 사용.

순환 큐(Circular Queue): 시작과 끝을 연결해서 순환하는 큐. (후단은 실제후단에 1을 더한 값을 가짐)

 

비어 있거나 또는 가득 차 있거나

순환 큐는 비어 있는 상태와 가득 차 있는 상태를 구분할 수 없음. 

일반적인 해법은 큐 배열 생성시 실제의 용량보다 1만큼 더 크게 만들어서 전단과 후단(실제의 후단) 사이를 비움.

그러면 큐가 비어 있을때 전단과 후단이 같은 곳을 가리키게 되고, 큐가 차 있을 때는 후단이 전단보다 1 작은 값을 갖게 됨.

 

3.4 링크드 큐

순환 큐 VS 링크드 큐

링크드 큐의 각 노드는 앞 노드에 대한 포인터를 이용해 구성되어 있음. 또 큐가 가득 차 있는 상태인지 확인을 할 필요가 없음. 일반적으로는 한계 용량의 제한이 없어서 '가득찬다'의 개념이 성립되지 않음.

삽입: 새 노드의 포인터에 후단을 연결

제거: 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두어 들이는 것.