자료구조 - 큐

큐

큐의 개념

• 한쪽에서는 삽입이 발생하고, 다른 한쪽에서는 삭제가 발생하도록 정의되어있는 자료구조.
• 먼저 삽입되는 원소가 먼저 삭제되는 FIFO(First-In-First-Out) 알고리즘과 함께 사용됨.
• front(큐의 앞) : 원소의 삭제 연산이 이루어지는 곳
• rear(큐의 뒤) : 원소의 삽입 연산이 이루어지는 곳

큐의 응용

(1) CPU 의 관리 방법 : FCFS(First-Coms-First-Serverd) 스케줄링 - 준비 큐에 도착한 순서대로 프로그램이 CPU를 할당받고 작업이 완료될 때까지 CPU를 사용하는 기법.

(2) CPU 의 관리 방법 : RR(Round Robin) 스케줄링 - 준비 큐에 도착한 순서대로 프로그램이 CPU를 할당받고, 일정 시간(time slice)만 CPU를 사용하고 반환하는 방식. 반환때까지 작업을 완료하지 못한 프로그램은 다시 준비 큐에 들어가게 된다.

큐의 추상 자료형과 구현

큐의 추상 자료형

ADT
1. 큐 객체에 대한 정의
- 큐 객체 : 0개 이상의 원소를 갖는 유한 순서 리스트
- 연산의 위치 : enqueue(add) 와 dequeue(delete) 연산이 각각 다른 곳 (rear, front) 에서 발생하는 자료구조

2. 큐의 연산
- queue : 0개 이상의 원소를 갖는 큐
- item : 큐에 삽입되는 원소  
- maxQueueSize : 큐의 최대 크기를 정의하는 정수  
- queue ∈ Queue, item ∈ element, maxQueueSize ∈ positive integer
(1) Queue Create_q(maxQueueSize) ::=
    큐의 크기가 maxQueueSize 인 빈 큐를 생성하고 반환한다;
(2) Boolean IsFull_q(queue, maxQueueSize) ::=
    if((queue의 element 개수) == maxQueueSize)
        then {'True' 값을 반환한다;}
        else {'False' 값을 반환한다;}
(3) Queue Enqueue_q(queue, item) ::=
    if(IsFull_q(queue, maxQueueSize))
        then {'queueFull'을 출력한다;}
        else {큐의 rear에서 item을 삽입하고 큐을 반환한다;}
(4) Boolean IsEmpty_q(queue) ::=
    if(rear == front) // rear 와 프론트가 같다면 == 비어있는 큐라면
        then {'True'를 반환한다.;}
        else {'False'를 반환한다.;}
(5) Element Dequeue_q(queue) ::=
    if(IsEmpty_q(queue))
        then {'queueEmpty'을 출력한다.;}
        else {큐의 front에서 원소를 삭제하고 큐을 반환한다.;}

배열을 이용한 큐의 구현

• 배열을 이용해 구현할 때 rear의 초기값은 공백상태를 나타내는 -1로 시작함
• 배열을 이용해 구현할 때 front의 초기값 또한 삭제가 일어나지 않았다는 -1로 시작함
• 삽입, 삭제가 일어날 때에는 먼저 front 와 rear 값을 이동시킨 다음 삽입, 삭제 연산이 일어난다.

(1) 큐의 생성

#define QUEUE_SIZE 5
typedef int element;
element queue[QUEUE_SIZE];
int front = -1;
int rear = -1;

(2) 큐의 삽입 연산

void enqueue(element item) {
    if(rear == QUEUE_SIZE-1) // 삽입된 원소의 개수가 큐의 크기와 같을 경우
    {
        printf("QUEUE is full !!");
        return;
    }
    queue[++rear] = item; // 큐의 크기와 다를 경우엔 rear를 1 증가시키고, 큐의 rear 인덱스에 원소를 저장
    return ;
}

(3) 큐의 삭제 연산

element dequeue() {  // 연산자 반환값으로 element 가 있음
    if(front == rear) { // front == rear 라면 >> 비어있는 큐라면
        printf("QUEUE is empty !!");
        return; }
    return queue[++front]; // 큐의 front 를 하나 증가시키고, queue의 증가시킨 front 인덱스에 있는 원소를 반환
}

전통적인 큐에서는 원소를 실제로 제거하지 않고, 단순히 front를 이동시켜 다음 원소를 가리키는 방식을 취한다.

원형 큐

기존 큐의 문제점

공간 낭비의 문제

• (1) rear 가 배열의 끝에 도달했을 경우, 앞쪽 원소들을 삭제하더라도 더 이상 데이터를 삽입할 수 없다.
• (2) 비어 있는 공간이 있음에도 불구하고, 큐의 앞쪽 (개념적으로) 빈 공간을 재사용하지 못한다. 따라서 새로운 큐를 만들거나 확장해야할 수도 있다.

원형 큐의 개념

• Circular Queue
• 큐의 입구와 출구 즉, 양 끝을 연결시켜 개념적으로는 원의 형태로 만든 큐
• 유연한 큐 공간 사용을 위해 front 와 rear 간의 위치 차이 측정을 위해 mod(모듈러) 연산을 활용한다.
• 삽입을 위한 rear 위치 계산을 (++rear) % QUEUE_SIZE 와 같이 수행한다.

Reference

자료구조 (강태원, 정광식 공저)