[자료구조]CH6. 큐

참조 : C로 배우는 쉬운 자료구조 (이지영 저)

공부날짜 : 2021.02.07

 

<Section1> 큐의 이해

 

1. 큐의 개념과 구조

 

 큐는 삽입과 삭제가 위치와 방법이 제한된 유한 순서 리스트라는 점은 스택과 같지만, 리스트의 한 쪽 끝에서는 삽입 작업만 이루어지고 반대쪽 끝에서는 삭제 작업만 이루어진다는 점이 스택과 다르다. 

먼저 삽입된 데이터가 먼저 삭제되는 선입선출(First In First Out) 구조로 운영된다. 

 한쪽 끝을 front(머리)라고 하고 삭제 연산만 수행하고, 다른 한 쪽은 rear(꼬리)로 삽입 연산만 이루어진다. 

front는 가장 먼저 큐에 삽입된 첫 번째 원소이고 rear는 가장 늦게 삽입된 마지막 원소이다. 

 

2. 큐의 추상 자료형

 

front와 rear를 -1로 초기 상태를 설정한다.

front=rear이면 공백 상태이며, front=rear=-1이면 초기 상태이다.

 

<Section2> 큐의 구현

 

1. 순차 자료구조를 이용한 큐의 구현

 

 1.1 순차 큐

  1차원 배열을 Q[n]을 이용하여 순차 큐를 구현한다. n은 배열의 크기, 큐의 크기가 된다. 

front와 rear를 초기에 -1로 설정한다. 

 

  1.1.1 공백 순차 큐 생성

   creatQueue()

       Q[n];

       front ← -1;

       rear ← -1;

   end creatQueue()

 

  1.1.2 순차 큐 공백 상태 검사

   isEmpty(Q)

       if (front = rear) then return  true;

       else  return false;

   end isEmpty()

 

  1.1.3 순차 큐의 포화 상태 검사

   isFull(Q)

       if (rear = n - 1) then return true; // rear가 마지막 인덱스 n-1이면 포화상태

       else return false;

   end isFull()

 

  1.1.4 순차 큐의 원소 삽입

   enQueue(Q , item)

        if (isFull(Q)) then Queue_Full();

        else {

                rear = rear + 1;

                Q[rear] ← item;

              }

   end enQueue()

 

   1.1.5 순차 큐의 원소 삭제

   deQueue(Q)

        if (isEmpty(Q)) then Queue_Empty();

        else {

                front ← front + 1; // front는 가장 앞에 있는 원소의 앞 쪽을 가리키고 있으므로 +1을 해준다.

                return Q[front];

              }

   end deQueue()

 

  1.1.6 순차 큐의 원소 검색

   peek(Q)

        if (isEmpty(Q)) then Queue_Empty();

        else return Q[front + 1];

   end peek()

 

2. 원형 큐의 구현

 

 순차 큐에서의 삽입과 삭제 연산을 해주면 앞 부분에 빈자리가 있음에도 포화 상태로 인식하여 더 이상 삽입 연산을 진행할 수 없다. 자리이동으로 해결할 수 있지만 순차 자료구조에서 자리 이동은 오버헤드가 커서 큐의 효율을 떨어뜨린다.

 이러한 문제를 해결하기 위해 원형 큐를 사용한다. 1차원 배열이지만 처음과 끝이 연결되어 있는 원형 구조로 가장하고 사용한다.

 front와 rear를 0으로 설정하고, 공백 상태와 포화 상태를 쉽게 확인하기 위해서 자리는 항상 하나를 비워둔다.

공백상태에는 front=rear이고 인덱스는 나머지 연산자 mod를 사용한다. 

 

 2.1 공백 원형 큐 생성

  creatQueue()

      cQ[n];

      front ← 0;

      rear ← 0;

  end creatQueue()

 

 2.2 원형 큐의 공백 상태 검사

  isEmpty(cQ)

      if (front = rear) then return true;

      else return false;

  end isEmpty()

 

 2.3 원형 큐의 포화 상태 검사

  isFull(cQ)

      if (((rear + 1) mod n) = front) then return true;

      else return false;

  end isFull()

 

 2.4 원형 큐의 원소 삽입

  enQueue(cQ , item)

      if (isFull(cQ)) then Queue_Full();

      else {

             rear ← (rear + 1) mod n;

             cQ[rear] ← item;

            }

  end enQueue()

 

 2.5 원형 큐의 원소 삭제

  deQueue(cQ)

      if (isEmpty(cQ)) then Queue_Empty();

      else {

             front ← (front + 1) mod n;

             return cQ[front];

            }

  end deQueue()

 

3. 연결 자료구조를 이용한 큐의 구현

 

 3.1 연결 큐

  배열의 크기가 제한 되는 문제를 해결하기 위해 연결 큐를 사용한다. 

데이터 필드와 링크 필드를 가진 노드로 구성되고, front와 rear를 NULL 포인터로 설정한다.

 

  3.1.1 공백 연결 큐 생성

   creatLinkedQueue()

        front ← NULL;

        rear ← NULL;

   end creatLinkedQueue()

 

  3.1.2 연결 큐의 공백 상태 검사 

   isEmpty(LQ)

         if (front = NULL) then return true;

         else return false;

   end isEmpty()

 

  3.1.3 연결 큐의 원소 삽입

   enQueue(LQ , item)

         new ← getNode();

         new.data ← item;

         new.link ← NULL;

         if (front = NULL) then {

             rear ← new;

             front ← new;

         }

         else {

             rear.link ← new;

             rear ← new;

         }

   end enQueue()

 

  3.1.4 연결 큐의 원소 삭제

   deQueue(LQ)

         if (isEmpty(LQ)) then Queue_Empty();

         else {

             old ← front;

             item ← front.data;

             front ← front.link;

             if (isEmpty(LQ)) then rear ← NULL;

             returnNode(old)

             return item;

               }

   end deQueue()

 

  3.1.5 연결 큐의 원소 검색

   peek(LQ)

         if (isEmpty(LQ)) then Queue_Empty()

         else return (front.data);

   end peek()

 

<Section3> 데크

 

 데크는 큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조로, 큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있는 자료구조이다. 

원소의 삭제와 삽입이 front에서 이루어질 때는 front를 top이라고 생각했을 때 pop()과 push()와 같으며.

rear에서 이루어질 때는 rear를 top으로 생각하고 pop()과 push()와 같다. 

front에서의 삭제 연산, rear에서의 삽입 연산은 enQueue(), deQueue()와 같다.

 

<Section4> 큐의 응용

 

1. 운영체제의 작업 큐

 큐는 각기 다른 속도로 실행되는 작업의 처리 시간을 적절히 조절할 때 사용할 수 있다. 

CPU가 실행할 데이터를 버퍼 큐에 저장하고, 버퍼 큐에 있는 작업을 순서대로 처리하고 처리가 완료되면 버퍼 큐에서 삭제한다. 

 CPU를 사용할 프로세스에 대해 CPU사용 스케쥴을 관리하기 위해 스케쥴링 큐를 사용한다. 

사용할 프로세스를 준비 큐에 삽입하면 순서대로 준비 큐에서 꺼내 CPU에서 사용한다. 사용 중 인터럽트가 와서 대기 상태가 되면 대기 큐에 삽입하여 관리한다. 

 

2. 시뮬레이션에서의 큐잉 시스템

 수학적 모델링에 사용되는 통계적인 이론이 큐잉 이론이다.

큐잉 이론에서는 서비스를 받기 위해 기다리는 대기 행렬과 대기 시간을 실험하는데 큐를 사용한다. 모든 서비스가 끝나서 대기 행렬 큐가 공백이 될 때 까지 평균 대기 시간을 여러 상황에 대해 시뮬레이션하여 최적의 시스템을 설계한다.