기말준비-큐(Queue)

Queue 는 First In-First Out(FIFO) 규칙이 지켜지는 자료 구조이다.

 

구현방식

 1. SLL (Single-Linked List) - 그냥 SLL

 2. Linear Array - 그냥 선형 배열

  문제점 : 제한된 공간 내에서 data가 한 쪽으로만 이동하므로 한계에 도달하면 Drifting(표류)현상이 일어날 수 있음.

  해결법 : Circular Array 사용

 3. Circular Array

  Head - Output data (초기 key : 0) / Tail - Input data (초기 key : 0)

 문제점 : 삽입, 삭제를 아무리 해도 Head와 Tail의 key값이 똑같음.

 해결법 :

    - 1) Counter 도입. (FULL : Count = n) (EMPTY : Count = 0) / the worst

    - 2) Buffer를 한칸 덜 사용함. (FULL : 'Head == Tail + 1') (EMPTY : 'Head == Tail') / not best

    - 3) Head, Tail의 위치 정보는 유지하되, 값을 다르게 표시 - Producer Consumer Problem / the best

     in = 0 (Input, Head) // out = 0 (Output, Tail) // Size = N 일 때,

     Producer는 Buffer[in%N] 에 데이터를 입력하고 `in = in + 1 + N` 을 함. (입력 작업이 끝나면 in >= N)

     Consumer는 Buffer[out]의 데이터를 출력하고 `in = in%N` 을 함. (출력 작업이 끝나면  in < N)

     그러므로

       FULL = `out == (in%N) && in >= N` // 입력이 끝난 후 Head == Tail이면 FULL

       EMPTY = `out == (in%N) && in < N` // 출력이 끝난 후 Head == Tail이면 EMPTY