[Queue]15. Queue 종류

목차

1. Array-base Queue(배열 기반 큐)

2. Array-base Circular Queue(배열 기반 원형 큐)

3. Linked list-base Queue(연결 리스트 기반 큐)

 

1. Array-base Queue(배열 기반 큐)

 Array-base Queue(배열 기반 큐)는 제목과 같이, queue를 array에 저장하는 방식을 말합니다. 위의 그림과 같이 배열의 앞부분을 front, 뒷부분을 rear로 놓고 사용합니다. 일반 배열 기반 큐의 특징은 값을 계속 enqueue할 경우, 앞의 메모리 공간이 비어있는 상태로 방치된다는 단점이 있습니다. 물론 파이썬을 기반으로 구현하면 그렇지 않지만, c++, java 등 array를 선언할 시 배열의 크기가 정해지는 경우, 이는 심각한 메모리 손실로 이어집니다.

 

2. Array-base Circular Queue(배열 기반 원형 큐)

 1번의 방식은 메모리 손실이 심하다는 단점이 있었습니다. 이러한 단점을 보완한 방식이 위의 그림과 같은 Array-base Circular Queue(배열 기반 원형 큐)입니다. 배열 기반 원형 큐의 특징은, rear가 배열의 마지막에 도달하였으며, front앞에 dequeue로 인해 삭제되어 비어있는 메모리가 남아있을 경우, 다시 배열의 앞으로 돌아와서 element를 삽입한다는 점입니다. 이는 마치 배열의 시작과 끝을 서로 연결한 원형과 같기 때문에, 이를 배열기반 원형 큐라고 부릅니다.

 

3. Linked list-base Queue(연결 리스트 기반 큐)

 Linked list-base Queue(연결 리스트 기반 큐)는 이름 그대로, queue를 linked list에 저장하는 방법을 말합니다. Linked list는 tail에서의 삭제가 효율적이지 않기 때문에, 주로 head를 front, tail을 rear로 둔 후 사용하는 편입니다. Linked list로 queue를 구현할 시, 별도의 비어있는 메모리가 생기지 않는다는 것이 장점입니다.