[자료구조] 큐 - 정리 및 연습문제

1. 큐(queue)의 개념

큐는 줄을 선 순서대로 처리되는 모습으로 표현할 수 있다.

- 큐의 스택의 공통점은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형이라는 것

- 가장 먼저 입력된 자료가 가장 먼저 출력되는 관계를 표현한다.

- FIFO(First In First Out, 선입선출)

- FCFS(First Come First Servce, 선착순 서브)

- 한쪽 끝에서는 원소의 삽입 연산만, 다른 한쪽 끝에서는 삭제 연산만 발생

- 두개의 큐 포인터 변수(일반적으로 front, rear로 명명)를 사용한다.

- front는 큐의 삭제가 발생하는 지점을 가리킨다.

- rear는 큐의 삽입이 발생하는 지점을 가리킨다.

- 삽입 시 rear를 증가시키고 삭제 시 front를 감소시킨다.

 

2. 큐의 추상 자료형(ADT)

* Object(객체)
0개 이상의 원소를 갖는 유한 순서 리스트

* Functions(연산)
queue∈Queue, item∈element, maxQueueSize∈positive interger인 모든 queue, item, maxQueueSize에 대하여 다음과 같은 연산이 정의된다. queue는 0개 이상의 원소를 갖는 큐, item은 큐에 삽입되는 원소, maxQueueSize는 큐의 최대 크기를 정의하는 정수이다.

① Queue createQueue(maxQueueSize) ::= 큐의 크기가 maxSizeQueue인 빈 큐를 생성하고 반환한다;

② Boolean isQueueFull(queue) ::=
    if((queue의 elements 개수) == maxQueueSize)
    then { 'TRUE' 반환; }
    else { 'FALSE' 반환; }

③ Queue addQueue(queue, item) ::=
    if(isQueueFull(queue))
    then { 'queueFull' 출력; }
    else { 큐의 rear에서 item을 삽입하고 큐를 반환한다; }

④ Boolean isQueueEmpty(queue) ::=
    if(rear == front)
    then { 'TRUE' 반환; }
    else { 'FALSE' 반환; }

⑤ Element deleteQueue(queue) ::=
    if(isQueueEmpty(queue))
    then { 'queueEmpty' 반환; }
    else { 큐의 front에 있는 element를 삭제하고 반환한다; }

  큐의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수 있다.

 

3. 큐 연산 수행

① createQueue(4);
② addQueue(queue, 'A');
③ addQueue(queue, 'B');
④ addQueue(queue, 'C');
⑤ deleteQueue(queue);
⑥ deleteQueue(queue);
⑦ deleteQueue(queue);
⑧ addQueue(queue, 'D');

큐 연산 수행 결과

⑦과 같이 rear 포인터와 front 포인터가 같은 장소를 가리키면(=같은 값이면) 큐는 empty 상태이다.

 

4. 배열을 이용한 큐의 구현

다음은 C언어로 구현한 int형 큐이다.

 

4-1. 큐의 생성

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

1라인: 큐의 사이즈를 5로 정의한다.

2라인: 큐의 element를 int형으로 정의한다.

3라인: element를 저장할 수 있는 큐를 QUEUE_SIZE만큼 할당받는다.

4,5라인: front와 rear를 -1로 초기화한다.

 

4-2. 큐의 삽입

삽입 전 큐의 초기 상태 예시

그림과 같이 삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동(증가)한다.

 

void addQueue(int *rear, element item) {
    if(*rear == QUEUE_SIZE-1) {
        printf("Queue is Full\n");
        return;
    }
 
    queue[++(*rear)] = item;
    return;
}

1라인: rear 변수의 주소값과 삽입할 데이터를 매개변수로 전달한다.

2라인: if(*rear == QUEUE_SIZE-1)

편의상 *rear 변수를 통해 큐가 만원 상태(full)인지 검사한다. 만원 상태이면 메시지를 출력하고 종료한다.

7라인: queue[++(*rear)] = item;

큐가 만원 상태가 아니면 *rear를 1 증가시키고 queue의 해당 인덱스에 item을 저장한다.(순서 중요)

 

삽입 연산으로 400을 저장한 결과

4-3. 큐의 삭제

삭제 연산이 발생하면 front 변수만 오른쪽으로 이동(증가)한다.

 

element deleteQueue(int *front, int rear) {
    if(*front == rear) {
        print("Queue is Empty\n");
        return;
    }
 
    return (queue[++(*front)]);
}

1라인: front 변수의 주소값과 rear 변수를 매개변수로 전달한다.

2라인: if(*front == rear)

front와 rear를 비교해 큐가 빈 상태(empty)인지 검사한다. front와 rear가 같으면 빈 상태이다. 빈 상태이면 메시지를 출력하고 종료한다.

7라인: return (queue[++(*front)]);

큐가 빈 상태가 아니면 *front를 1 증가시키고 queue의 해당 인덱스에 있는 element를 반환한다.(순서 중요)

 

삭제 연산 수행 결과

 

5. 큐의 응용 분야

FCFS 스케줄링 기법의 예

 

RR 스케줄링 기법의 예

- 큐는 대표적으로 CPU의 관리 방법에 활용된다.

- FCFS(First Com First Served) 스케줄링 기법 : FIFO(First In First Out) 스케줄링이라고도 한다. 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받는 기법이다.

- RR(Round Robin) 스케줄링 기법 : 대화형 시스템에 사용되는 스케줄링 방식이다. 도착한 순서대로 CPU가 할당되지만 CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받는다. 일정한 크기의 시간 할당량을 모든 작업에 주고 그 시간 동안 작업이 완료되지 못하면 준비 큐의 맨 뒤에 다시 배치한다.

 

6. 원형 큐(Circular Queue)

큐가 만원 상태(full)이며 메모리를 100% 사용하는 예

  배열로 구현된 사이즈 5짜리 큐이며 5개의 element가 모두 채워진 경우이다. 즉 할당된 메모리 영역을 100% 사용한다.

 

큐에 메모리 낭비가 발생한 예

  100과 200이 삭제되어 큐에 element가 모두 채워지지 않았지만 추가 element 삽입이 불가능하다. 배열로 구현된 큐는 정의된 배열의 메모리 영역을 변화시킬 수 없기 때문이다. queue[4]가 마지막 공간이고 rear가 더 이상 앞으로 증가할 수 없다. element가 삽입될 때마다 rear는 1씩 증가된다. 큐의 크기가 n이면 n-1의 위치까지 오고 더이상 저장할 수 없는 상태가 된다. 하지만 위 예시처럼 큐에 저장된 element는 n개가 아닐 수 있다.

  앞서 정의한 큐의 추상 자료형에서도 '큐의 element 개수 == maxQueueSize'를 큐의 만원 상태로 정의하고 있다. 즉 rear값으로 큐의 만원 상태를 결정하지 않는다.(배열을 이용해 구현한 큐에서는 편의상 rear값으로 판단함) 이 때문에 front부터 이전의 빈 공간에 메모리 낭비가 발생한다. 이는 큐를 배열로 구현했기 때문에 발생하는 문제점이다.

 

이러한 문제점을 해결하기 위해 원형 큐가 제안되었다.

 

원형 큐는 파이프의 입구와 출구를 연결시킨 형태이다.

 

큐와 원형 큐

앞서 본 큐와 동일한 데이터가 저장돼있는 원형 큐이다. 둘 다 rear값이 n-1인 상황이다. '600'을 삽입하려 시도하면 배열로 구현된 일반 큐에는 더 이상 삽입이 불가능하다. 하지만 원형 큐에서는 삽입이 가능하다.

 

원형 큐의 삽입 결과

  원형 큐는 공간을 재사용하여 메모리 활용도를 높일 수 있다. 이를 구현하려면 near의 위치가 n-1일 때 삽입이 발생하면 rear를 0으로 변경해야 한다.

 

나머지를 계산하는 mod(modulus) 연산자를 사용하여 rear값을 관리한다.
원형 큐에 element를 삽입할 때 'rear ← (rear + 1) mod n' 혹은 'front ← (front + 1) mod n' 연산식을 이용한다.

예:
① 배열로 구현된 사이즈 5 원형 큐의 rear가 3인 상태에서 삽입이 발생한다.
② '(3+1) mod 5'의 결과인 4를 rear 값으로 갖는다. → rear = n-1
③ 값을 저장한다.
④ 다시 삽입이 발생한다.
⑤ '(4+1) mod 5'의 결과인 0을 rear 값으로 갖는다. → rear = 0

 

7. 연습문제

1. 자료구조의 유형 중 선형 구조에 해당하는 것은 무엇인가?
① 큐
② 그래프
③ 트리
④ 힢

2. 큐에서 element를 삽입할 경우의 설명으로 맞는 것은?
① rear의 위치를 감소시킨 후 element를 삽입
② front의 위치를 증가시킨 후 element를 삽입
③ rear의 위치를 증가시킨 후 element를 삽입
④ front의 위치를 감소시킨 후 element를 삽입

3. 다음은 큐에 원소를 삽입하는 알고리즘이다. (가)와 (나)에 알맞은 것은?

① (가) *rear == QUEUE_SIZE, (나) (*rear)++
② (가) *rear == QUEUE_SIZE, (나) ++(*rear)
③ (가) *rear == QUEUE_SIZE-1, (나) ++(*rear)
④ (가) *rear == QUEUE_SIZE-1, (나) (*rear)++

4. 파이프의 입구와 출구를 연결시킨 형태의 큐로 기억장소의 낭비를 줄이기 위한 자료구조는 무엇인가?
① 연결 큐
② 이중 큐
③ 원형 큐
④ 데 큐

5. 다음 큐에 대한 설명으로 틀린 것을 모두 고르시오.
① 원형 큐는 입구(rear 변수)와 출구(front 변수)를 연결하여 데이터 공간을 연속적으로 사용하기 위해 제안되었다.
② 큐는 서로 다른 부분에서 삽입과 삭제가 발생하는 FIFO 특성을 갖는 순서 리스트이다.
③ 큐가 가득 찬 상태는 삽입되는 부분의 rear 변수와 삭제되는 부분의 front 변수를 이용하여 알 수 있다.
④ 삽입되는 부분의 rear 변수가 마지막을 가리키면 큐에 포함된 원소의 갯수는 큐의 크기와 같고 큐가 가득 찬 상태이다.

6. 큐의 운용과 유사하게 운영되는 것이 아닌 것은 무엇인가?
① 문서 출력을 위해 프린터기를 이용할 때 여러 개의 문서를 출력해도 먼저 인쇄버튼을 누른 문서부터 차례로 출력된다.
② 은행에서 번호표를 뽑고 창구에 가기를 기다린다.
③ 택시 승강장에 줄을 서서 택시를 기다린다.
④ 웹브라우저에서 방금 전 방문했던 사이트 기록 저장 후 '이전 페이지로 돌아가기'를 클릭한다.

7. 다음은 큐에 대한 연산이다. ⑧ 연산 수행 후 큐의 모습은 무엇인가?

 

정답 ▼

1 : ①
2 : ③
3 : ③
4 : ③
5 : ③,④
6 : ④
7 : ④