큐(Queue)

큐(Queue)

큐(Queue)란?

• 큐는 매표소에서 표를 사기 위해서 줄을 서는 것처럼 먼저 들어온 데이터가 먼저 삭제되는 구조이다. 이런 입출력 방식을 FIFO(First In First Out)이라고 한다.

큐 추상자료형(Queue Abstract Data Type)

• IsFull(): 큐가 다 찼을때, true를 반환한다.
• IsEmpty(): 큐가 비어있을때, true를 반환한다.
• enqueue(): 큐의 끝에 item을 추가한다.
• dequeue(): 큐의 맨 앞에 item을 제거해서 반환한다.
• peek(): 스택의 맨 앞에 원소를 제거하지 않고 반환한다.

큐(Queue) 알고리즘 (1)

• 큐는 연결리스트(Linked List)로 구현할 수 있다.

  Node *Head, *Tail, *p, *q;
  
  enQ(Node *p){
    p <- Next = NULL;
    if(Tail != NULL){
        Tail -> Next = p;
        Tail = p;
    }
    else{
        Head = Tail = p;
    }
  }
  Node* deQ(){
    if(Head == NULL) return NULL;
    else{
        q = Head
        Head = Head -> Next
        return q;
    }
  }
  

  선형 큐(Linear Queue)

• 선형 큐로도 구현할 수 있다. 하지만 삭제와 삽입을 반복하다보면 계속 사용할 수 없는 인덱스가 발생하게 된다. 이것을 표류(Drifting)현상이라고 한다.

  

원형 큐(Circular Queue)

• 이것은 원형 큐를 사용하면 간단하게 해결 할 수 있다.

  

• 원형 큐는 실제로 원형이 아니라 선형 큐를 이용해서 구현한다.
• 초기값 = Head = Tail = 0

  큐(Queue) 알고리즘 (2)

  enQ(item){
    if(Full) return;
    Q[Tail] = item;
    Tail = (Tail + 1) % N;
  }
  deQ(){
    if(Empty) return;
    p = Q[Head];
    Head = (Head + 1) % N;
    return p;
  }
  

• 이때 Full <-> Head == Tail, Empty <-> Head == Tail이라는 문제가 있다.
• 해결방법
  1. Counter 도입
     • Full <-> Counter = N
     • Empty <-> Counter = 0
  2. Buffer(Q)를 한 칸 덜 사용
     -> size N인 Q에 N-1개까지 채우면 FULL로 간주
     • Full <-> Head == (Tail+1) % N
     • Empty <-> Tail == Head
  3. Head, Tail의 위치정보를 유지하면서 값을 다르게 하는 방법
     • Full <-> Out == (in % N) && in >= N
     • Empty <-> Out == (in % N) && in < N
     • 생산자/소비자 문제(Producer/Consumer problem)에 적용

      // Producer(상대적으로 Fast)
      while(1){
          produce an item
          while(Full); // busy loop으로 Not Full 조건 획득해야 함
          B[in % N];
          in <- ((in + 1) % N) + N // N만큼 떨어진 곳에 저장
      }
      // Consumer(상대적으로 Slow)
      while(1){
          while(Empty); // busy loop
          item <- B[out];
          out <- (out + 1) % N;
          in <- in % N // in < N
          return item;
      }