4강. 큐

by

학습개요

큐는 스택과 유사하게 입출력 순서를 중심으로 자료들 간의 관계가 성립되는 자료구조입니다. 입출력 순서의 관리를 통해 입력이 가장 빨랐던 자료가 가장 먼저 출력되는 관계를 표현합니다. 그렇기 때문에 큐는 줄을 서는 순서에 따라서 공평하게 서비스를 해주는 경우에 많이 사용되고, 자원의 할당을 받으려는 작업들 간의 순서를 관리하기 위해 사용되는 경우가 많습니다.

큐를 기반으로 하는 입력 연산을 수행하기 전에 정의된 큐의 크기를 항상 확인해야 합니다. 큐의 크기보다 더 많은 자료를 입력하면 에러가 발생되기 때문입니다. 그리고 큐에 대한 삭제 연산을 수행하기 전에 큐에 삭제될 자료가 남아 있는지를 확인해야 합니다. 마지막으로 큐를 이용한 CPU 할당 방법을 보여드립니다. 그리고 큐의 삭제 연산 후에 남겨지는 빈 공간을 활용할 수 있는 원형큐는 큐의 빈 공간 활용도를 높이기 위해 제안되었으며, 큐에 비해서 ‘만원 상태’를 늦출 수 있는 자료구조입니다.

학습목표

  1. 큐의 추상 자료형을 이해할 수 있다.
  2. 큐의 삭제 연산과 삽입연산에 대해서 이해할 수 있다.
  3. 큐를 이용한 CPU 할당 방법을 이해할 수 있다.
  4. 만원 상태를 늦출 수 있는 원형 큐를 이해할 수 있다.

연습문제

  1. 자료구조의 유형 중 선형 구조에 해당하는 것은 무엇인가?
    1. 큐
    2. 그래프
    3. 트리
    4. 히프
      –
  2. 큐에서 노드를 삽입할 경우의 설명으로 맞는 것은 ?
    1. rear의 위치를 감소시킨 후 원소를 삽입
    2. front의 위치를 증가시킨 후 원소를 삽입
    3. rear의 위치를 증가시킨 후 원소를 삽입
    4. front의 위치를 감소시킨 후 원소를 삽입
      –
  3.  

    1. void Add_q(element item) {
    2. if ( (가) )
    3.   {   printf(“Queue is full !!”) ;
    4.       return ;       }
    5.  queue[ (나) ] = item ;
    6.  return ;   }
    1. (가) rear == QUEUE_SIZE
      (나 ) rear++
    2. (가) rear == QUEUE_SIZE
      (나 ) ++rear
    3. (가) rear == QUEUE_SIZE-1
      (나 ) ++rear
    4. (가) rear == QUEUE_SIZE-1
      (나 ) rear++

정리하기

  1. 큐는 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트라고 합니다. 교재에서는 ‘알고리즘과 함께 사용됩니다’로 되어 있습니다. 원형큐의 경우도 있어서, 순서 리스트라는 표현보다는 자료구조라는 표현이 더욱 정확하지 않을까 싶습니다.
  2. 큐에서는 원소의 삭제 연산이 이루어지는 곳을 앞(front)이라 하고 삽입 연산이 이루어지는 끝을 뒤(rear)라고 합니다.
  3. 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면 프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다. Create_q(maxQueueSize) 함수의 매개변수인 maxQueue는 큐가 저장할 수 있는 최대 개수의 원소(element)를 의미합니다.
  4. Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다. 즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면, 그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.
  5. Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다. 만일 큐가 가득 찼다(Full)면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull’ 메시지를 출력합니다.
  6. Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다. 만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
  7. Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty’를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.
  8. 큐의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
  9. 원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다. 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자’를 사용합니다.

Leave a Comment