_[6.1] 큐(Queue)의 개념

[문교식]

[6.1] 큐(Queue)의 개념

<<<<   목 차   >>>>

큐(Queue)의 개념

큐(Queue)의 정의

 AddQ()와 DelQ()

===================  

큐(Queue)의 개념

은행의 창구, 매표소에 가면 대기표를 받고 기다렸다가
먼저 온 고객이 먼저 서비스를 받는 상황을 생각해 보자.
대기표는 먼저 온 순서대로 순번이 부여되고,
고객들은 그 순서대로 서비스를 받는다.
즉, 먼저 도착한 고객이 먼저 서비스를 받는 경우이다.
이러한 대기 현상을 자료구조로 나타낸 것이 큐(Queue)이다.

대기행렬에 고객들이 들어와서 서비스를 받고 나가는 예를 살펴보자.
그림은 대기행렬의 상황을 보여준다.
(서비스는 대기행렬 밖에 있으므로 대기행렬 안에 표현하지 않는다.
서비스를 위한 공간은 생략한다)
     

고객이 들어와서 서비스를 받고 나가는 과정을 보여준다. 
   

A가 들어온다;    

   

A가 나가고 B가 들어온다;

  

C가 들어온다;

B가 나간다. D가들어온다;

고객C가 나간다. 이 때 E가 들어와서 대기한다.

큐(Queue)의 정의

큐(Queue)를 정의하면,
모든 삽입은 rear라고 부르는 한 쪽 끝에서 이루어지고,
모든 삭제는 front라 부르는 다른 쪽 끝에서 이루어지는
순서 있는 리스트(ordered list)이다.

큐는 FIFO라고도 말한다. (First In First Out; 보통 “피포” 또는 “파이포”로 읽는다);

rear에서 데이터를 하나씩 차례로 삽입하고

front라는 다른 쪽 끝에서 하나씩 순서대로 나간다.

따라서 먼저 들어온 데이터가 먼저 나가게 된다.

Rear와 front의 방향은 중요치 않다.

다만, 일관성 있게 방향을 유지하면 된다.

이 그림은 rear가 왼쪽, front가 오른쪽이지만, 방향이 반대가 될 수 있다.

그러나 rear에서 들어가고 front에서 나간다는 규칙은 지켜져야 한다.

(queuing theory의 큐 개념과는 무관하다. 유사하지만 서로 연관성 없이 정의되었다)

AddQ()와 DelQ()

큐에 데이터를 넣는 명령을 AddQ라 하자(교재에 따라 유사한 명칭이 사용된다).

큐에서 데이터를 삭제하는 명령을 DelQ라 하자.

AddQ는 삽입되는 데이터를 명시한다.

삽입하는 데이터를 X라 하면, 삽입 명령은 AddQ(X)이다.

AddQ(X)의 결과로 X가 큐의 rear에서 들어간다.

DelQ명령은 DelQ()로 표현하고,

DelQ()의 결과로 front에서 데이터가 하나 큐를 빠져 나간다.

DelQ()에서 받은 데이터를 수식이나 배정문에 사용할 수 있다.

[예제] 큐(Q라 하자)에 아래의 명령을 차례로 수행할 때,

         변수 res의 최종 결과와 rear에서 front방향으로 큐의 내용을 열거하시오.

    1) 큐에 ’28’이 저장되어 있다.  Q=[→ 28 →]

    2) AddQ(35);  Q=[→ 35 28 →]

    3) AddQ(77);  Q=[→ 77 35 28 →]

    4) res = DelQ(); res=28  Q=[→ 77 35 →]

    5) res = res + DelQ();  res=28+35=63  Q=[→ 77 →]

    결과; res=63  Q=[→ 77 →]

[연습문제] 큐(Q라 하자)에 아래의 명령을 차례로 수행할 때, 변수 res의 최종 결과는?

    1) 큐에 ’81’이 저장되어 있다.  Q= ?

    2) AddQ(36);  Q= ?

    3) AddQ(27);  Q= ? 

    4) res = DelQ()/9 + DelQ/4 + DelQ/3;  res= ?   Q= ?

//