[알고리즘/이론]큐

원소를 삽입할 때 Enqueue, 원소를 제거할 때 Dequeue를 한다. 큐는 FIFO(first in, first out, 선입선출)의 특성을 같는다. 큐는 머리(head)와 꼬리(tail)을 갖는 데, 원소는 꼬리로 삽입되고 머리에서 제거된다.

tail은 원소가 삽입될 위치를 가리키며 head는 삭제될 원소를 가리킨다. 따라서 head=tail이면 큐는 비어있으며, 이때 원소를 삭제하려고 하면 underflow가 발생한다. head=tail+1 또는 head=1일 때 tail이 배열의 마지막 원소를 가리키는 상태이면 큐가 가득찬 상태이며, 이때 원소를 삽입하려고 하면 overflow가 발생한다.

수행시간

Enqueue와 Dequeue에는 O(1)만큼의 시간이 걸린다.