- 큐의 스택의 공통점은객체와 그객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형이라는 것
-가장 먼저 입력된 자료가 가장 먼저 출력되는 관계를 표현한다.
-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을삽입하고 큐를 반환한다; }
⑤ 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. 큐의 운용과 유사하게 운영되는 것이 아닌 것은 무엇인가? ① 문서 출력을 위해 프린터기를 이용할 때 여러 개의 문서를 출력해도 먼저 인쇄버튼을 누른 문서부터 차례로 출력된다. ② 은행에서 번호표를 뽑고 창구에 가기를 기다린다. ③ 택시 승강장에 줄을 서서 택시를 기다린다. ④ 웹브라우저에서 방금 전 방문했던 사이트 기록 저장 후 '이전 페이지로 돌아가기'를 클릭한다.
