[자료구조] Chapter 06. 큐 (Queue)

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

Queue : FIFO (First-In, First-Out)

1. Linked List로 구현

enQ(p)
{   
    p->Next = NULL
    if(Tail != NULL){ // 맨 뒤에
    	Tail->Next = p;
        Tail = p
    }else {
    	Head = Tail = p;
    }
}
deQ(){/*맨 앞 삭제 후 반환*/}

2. 배열로 구현

• 문제점 : 제한된 공간에서 data가 한 쪽으로만 이동하여 한계에 이르는 Drifting(표류) 현상 발생함
  

3. 원형 배열 (Circular Array)로 구현

🚨 주의!!
FULL <-> Head == Tail
EMPTY <-> Head == Tail
둘의 조건식이 동일하다!! -> Head, Tail의 초기치 변경으로는 해결 불가

• 해결책
  • 새로운 변수 : counter(= #of elements) 도입 -> 추천 x (운영체제 입장에서 변수의 추가는 부담일 수 있음)
    FULL <-> counter = N
    EMPTY <-> counter = 0
  • Buffer(Q)를 한 칸 덜 사용 -> size가 N인 Q에 N-1개 까지 채우면 FULL로 간주
    
  • Head, Tail의 위치 정보를 유지하면서 값을 다르게 하는 방법 -> Producer / Consumer Problem (생산자 소비자 문제)
    • 생산자 소비자 문제 (Producer / Consumer Problem)