문재 해결을 위한 기본적 접근 방법 - 큐(Queue)

먼저 들어온 자료가 먼저 나가는 (First In First Out: FIFO) 특성을 가지는 자료 구조.

큐의 기본 개념

큐에 자료를 넣을 때에는 넣는 자료가 가장 뒤쪽에 놓이게 되고,
자료를 꺼낼 때에는 가장 앞쪽에 위치하고 있는 자료가 꺼내 진다.

 

*큐(Queue) - FIFO구조 - enQueue 작업 절차

Queue에 자료를 넣을 공간이 없을 경우에는 자료 저장이 불가능하다.
Queue에 자료를 넣을 공간이 있을 경우, Queue의 가장 뒤(back)에 자료를 넣는 작업과정이 진행된다.

  ① 큐에 자료를 넣을 공간이 있는지 확인한다.

  ② (큐에 공간이 있을 경우) 큐의 가장 뒤(back) 위치 번호를 1 증가시킨다.

  ③ (큐에 공간이 있을 경우) 큐의 back위치 번호 위치에 자료를 넣는다.

*큐(Queue) - enQueue 예

기능(function) : //큐의 후위(back)에 자료를 넣음 입력(input) : 큐 q, 자료 x 출력(output) : 없음 enQueue(q, x) begin    if( isFull(s) is equal “false”)      { q.back := q.back + 1;        q.back[q.back] := x;      }    else    {        ERROR(“큐에 빈 공간이 없어 자료를 넣을 수 없습니다.”)    }    end;

*큐(Queue) - FIFO구조 - deQueue 작업 절차

Queue에 자료가 없을 경우 큐에 자료가 없음을 사용자에게 알려준다. Queue에 자료가 있을 경우,
큐의 가장 앞(front)의 자료를 꺼내는 후속작업이 진행된다. front 위치 번호는 항상 가장 앞에
있는 자료의 위치 번호를 가지고 있다.

  ① 큐가 비어 있는지 확인한다.

  ② (큐가 비어 있지 않은 경우) 큐의 front 위치 번호에 위치한 자료를 꺼낸다.

  ③ (큐가 비어 있지 않은 경우) front 위치 번호를 1 증가시킨다.

*큐(Queue) - deQueue 예

기능(function) : //큐의 앞(front)에 자료를 꺼냄 입력(input) : 큐 q 출력(output) : 자료 x x deQueue(q) begin    if( isEmpty(s) is equal “false”) //큐에 꺼낼 자료가 있는지 확인      { x := q.data[q.front]; //큐로부터 자료를 꺼내어 자료 변수에 저장        q.front := q.front + 1; //front 위치 번호 증가        return x; //자료변수 건네줌      }    else    {      ERROR(“큐가 비어 있어 자료를 꺼낼 수 없습니다.”)    }    end;

*큐(Queue) 예 - 은행 창고 큐

은행창구에서 고객들이 대기표를 받을 땜마다 큐에 고객이 대기 번호를 넣으며(enQueue).
은행원이 업무를 볼 수 있을 때 큐의 가장 앞에 있는 고객을 호출(deQueue)한다.

10번 고객이 대기표를 발급받고 호출되어 업무를 보고, 이후에 11번 12번 2명의 고객이 대기표를 발급받고 차례대로 업무를 보는 상황을 가정하였다. 이러한 상황에서 고객의 대기열을 관리하는 Queue 내부의 변화과정을 살펴보면 다음과 같다.