All
큐의 개념
•
선입선출(FIFO, First In First Out) 구조 - 먼저 들어온 데이터가 먼저 나감
•
front: 큐의 맨 앞, 삭제만 일어남
•
rear: 큐의 맨 뒤, 삽입만 일어남
•
큐는 0개 이상의 원소를 갖는 유한 순서 리스트
•
삽입(enqueue), 삭제(dequeue) 연산 모두 O(1) 시간 복잡도
큐의 응용
•
프로세스 관리: 운영체제에서 CPU 스케줄링 (준비 큐, 대기 큐)
◦
예: 라운드 로빈(Round Robin) 스케줄링은 큐를 이용해 순서대로 CPU 할당
•
입출력 관리: 프린터 대기열
•
네트워크 패킷 처리: 패킷 전송 순서 관리
•
탐색 알고리즘: BFS (너비 우선 탐색) 구현 시 큐 사용
•
시뮬레이션 시스템: 은행, 콜센터, 병원 접수 등 대기열 시뮬레이션
큐의 추상자료형
•
Queue: 0개 이상의 원소를 갖는 집합
•
Element(item): 큐에 삽입되는 원소
•
maxQueueSize: 큐의 최대 크기를 정의하는 정수
CreateQueue 연산
•
크기가 maxQueueSize인 빈 큐를 생성하여 반환
Queue CreateQueue(maxQueueSize)
C
복사
삽입(Enqueue) 연산
•
item을 rear에 삽입
•
큐가 가득 차 있으면 가득참 출력
Queue Enqueue(queue, item)
if (IsFull(queue))
then {queueFull 출력;}
else {rear 위치에 item 삽입 후 큐 반환 }
C
복사
삭제(Dequeue) 연산
•
front 원소를 제거하고 반환
•
큐가 비어있으면 비었음 출력
Element Dequeue(queue)
if (QueueIsEmpty(queue))
then {queueEmpty 출력;}
else {front 원소 삭제 후 큐 반환}
C
복사
빈 큐 검사 (QueueIsEmpty) 연산
Boolean QueueIsEmpty(queue)
if (front == rear)
then {True 반환;}
else {False 반환;}
C
복사
큐 만원 검사 (QueueIsFull) 연산
Boolean QueueIsFull(queue, maxQueueSize)
if (rear == maxQueueSize - 1)
then {True 반환;}
else {False 반환;}
C
복사
배열을 이용한 큐의 구현
생성
•
변수 rear 초기값은 큐의 공백 상태를 나타내는 -1 로 시작
#define QUEUE_SIZE 10
typedef int element;
element queue[QUEUE_SIZE]; // 큐 저장 공간
int front = -1;
int rear = -1;
C
복사
삽입 (enqueue)
•
삽입 연산 발생 시 rear 변수만 오른쪽으로 이동
•
삭제 연산 발생 시 front 변수만 오른쪽으로 이동
void enqueue(int item) {
if (rear >= QUEUE_SIZE - 1) {
printf("Queue is Full");
} else {
queue[++rear] = item;
}
}
C
복사
삭제 (dequeue)
•
삭제 연산의 수행 결과로 삭제된 원소를 반환
•
front는 삭제 직전 원소를 가리키는 위치로 실제 첫 번째 원소보다 하나 앞 인덱스를 유지
•
따라서 삭제 시에는 ++front 해주고, 그 위치의 값을 반환
element Delete_q() {
if (front == rear) {
printf("Queue is empty");
return;
}
return (queue[++front]);
}
C
복사
원형 큐 (Circular Queue)
문제점 (선형 큐의 한계)
•
배열로 큐를 구현하면, 삭제를 반복할수록 앞쪽 공간이 비어도 재사용 불가능
해결책: 원형 큐
•
큐를 원형 배열(circular array) 로 간주
•
rear가 배열 끝에 도달하면 다시 맨 앞으로 이동 (mod 연산 이용)
rear = (rear + 1) % QUEUE_SIZE;
front = (front + 1) % QUEUE_SIZE;
C
복사