[자료구조] 12. 큐(Queue)

큐 (Queue)

▶ 줄 서기.

▶ 특징 : First In First Out (FIFO). First Come First Served.

▶ 정의 : Insert가 한쪽 끝(Rear)에서 발생하고, Remove가 다른 한 쪽 끝(Front)에서 발생하는 제한 조건(constraint)을 갖는 리스트형 구조.

    ▷ (초기화를 -1로 하는 방식으로 구현하는 경우) front와 rear가 동일한 인덱스를 가리키면, 배열에 남은 값은 하나이다. (구현 방식에 따라 차이가 있을 수 있음.)

 

백신을 맞기 위해 줄을 서는 상황과 큐의 유사성

▶ 선형 큐 vs. 원형 큐

  ▷ 선형 큐의 경우, 실제 배열에 값이 가득 차있지 않고 배열 인덱스 마지막 칸에만 값이 있어도 rear값이 배열의 끝에 도달하면 Full이라고 처리된다. 이 단점을 보완해주는 것이 원형 큐이다. 원형 큐는 실제로 배열에 값들이 가득 차있어야 Full이라고 처리 된다. 구현 측면에서 다시 설명하자면, 선형 큐에서는 rear + 1가 front와 같을 때 가득 찼다고 처리하지만, 원형 큐에서는 (rear + 1) % (배열의 크기)를 한 값이 front와 같아야 가득 찼다고 처리한다.

 

---

선형 큐 (Linear Queue)의 동작 (Operations)

▶ 1. Enqueue(Q , x) 또는  Push(Q , x)

▶ 2. Dequeue(Q) 또는  Pop(Q)

▶ 3. Front(Q) 또는  Peek(Q)

▶ 4. Is Empty(Q)

▶ 5. Is Full(Q)

 

≫ 배열로 Queue의 Operation을 구현했을 때의 시간 복잡도는 모두 O(1)이다.

 

▶ 동작 예시

큐 동작 예시

▶ 구현 (수도 코드)

수도 코드로 구현한 선형 큐 동작들

---

원형 큐 (Circular Queue)의 동작 (Operations)

▶ 1. Enqueue(Q , x) 또는  Push(Q , x)

▶ 2. Dequeue(Q) 또는  Pop(Q)

▶ 3. Front(Q) 또는  Peek(Q)

▶ 4. Is Empty(Q)

▶ 5. Is Full(Q)

   ▷원형 큐의 경우, 실제 배열에 값이 가득 차있어야 Full이라고 처리한다. 

▶ 6. print Queue(Q)

 

▶선형 큐의 동작과 달라지는 부분