[자료구조] Queue

Queue란?

FIFO (First In First Out), 선입선출의 원칙을 따르는 자료구조이고 아래와 같이 두가지 중요한 작업이 있다.

• Enqueue : 큐의 끝에 항목 추가
• Dequeue : 큐의 앞쪽에서 항목 제거 후 반환

즉, 큐에서는 가장 먼저 enqueue된 항목이 가장 먼저 dequeue 된다.

Queue의 종류

• 선형 큐 (Queue)
• 원형 큐 (Circular Queue)
• 우선순위 큐 (Priority Queue)
• 덱 (Deque; Double Ended Queue)

선형 큐 (Queue)

• 일반적인 선형 큐로 enqueue 와 dequeue의 기능만을 가지고 있다
• 시간복잡도 : O(1)

원형 큐 (Circular Queue)

• 원형으로 이루어진 큐로 첫 요소와 마지막 요소가 연결되어 있다
• 원형으로 순환하며, 값이 추가되거나 삭제되어도 포인터값이 바뀌기 때문에 작업 수행 가능
• 시간복잡도 : O(1)

우선순위 큐 (Priority Queue)

• 선형 큐와 같은 기능을 가지고 있지만 추가적으로 수선순위가 배정되어 있다
• 일반적으로 Heap으로 구현된다
• 시간복잡도 : O(log n)

덱 (Deque; Double Ended Queue)

• 양쪽에서 삽입, 삭제가 가능한 구조
• 스택과 큐의 연산 모두 지원
• 시간복잡도 : O(1)