[자료구조] 큐(2)
큐의 응용
FIFO의 구조, 즉 먼저 요청한 작업에 대해 먼저 처리해주는 형태로 동작하는 큐의 특징을 직간접적으로 다양한 분야에 응용할 수 있음
- 컴퓨터 운영체제에서 실행을 요청한 작업들을 순서 대로 처리하기 위해서 큐(버퍼 큐와 프로세스 스케줄링 큐)를 사용함
- 산업공학분야에서 최적의 시스템을 설계하기 위한 시뮬레이션에서 대기행렬 큐를 사용함
- 공항에서 비행기들의 이륙, 은행에서 고객의 대기열
- 실시간 시스템에서 인터럽트를 제어(first come first served)하는데 사용함
- 통신에서 데이터 패킷들의 모델링, 콜센터의 고객응대 시스템 등에서 사용함
- 프로그래머의 도구 및 많은 알고리즘에서 사용함
운영체제 작업 큐
프린터 버퍼 큐(buffer queue)
인쇄작업에서 CPU에 비해 프린터의 느린 인쇄 작업이 진행 중일 때 기다리지 않고 다음 데이터를 버퍼 큐(주기억장치 내)에 삽입하여 버퍼큐에 있는 데이터를 순서대로 출력하게 함
- CPU에서 프린터로 보낸 데이터를 순서대로(선입선출) 프린터에서 출력
스케쥴링 큐(scheduling queue)
스케쥴링 정책 - 메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가에 대한 순서를 결정하는 것 => CPU와 같은 자원의 효율적인 사용
CPU를 사용하고자 (요청)하는 프로세스들에 대한 CPU 사용 스케줄을 관리(자원의 할당과 회수, 스케쥴러 역할)하기 위해 사용되는 큐를 말함
- 준비 큐와 대기 큐로 구성되어 있음
- 사용하고자 하는 프로세스를 순서대로 준비 큐에 삽입하면 그 순서대로 준비 큐에서 꺼내어 CPU를 사용함
- CPU를 사용하던 프로세스가 다른 처리를 기다리는 대기 상태가 되면 대기 큐에 삽입하여 대기 상태의 프로세스들을 순서대로 관리함
메시지 큐(message queue)
메시지 형태의 데이터를 넣어두고 FIO(선입선출) 방식으로 메시지를 추출하여 대상 시스템의 데이터베이스, 파일저장, 응용프로그램 입력 값으로 처리하기 위해 사용된 큐를 말함
- 메시지 큐는 윈도우즈 시스템의 모든 스레드(프로세스 내에서 실행되는 흐름의 단위)에 존재함
- 사용자가 윈도우즈에서 어떤 조작을 수행하면 해당 입력은 메시지로 전달되며 프로세스가 메시지 큐에서 해당 입력에 대응하는 메시지를 읽어서 처리함
- 예를 들어, 사용자가 마우스를 움직이는 경우(사용자가 취한 행동)에 마우스 움직임을 의미하는 메시지인 WM_MOUSEMOVE가 메시지 큐에 저장되며 프로그램은 메시지 루프(메시지를 받아들이는 부분)를 통해 이에 대응하는 처리를 함
대기행렬 이론(queueing theory)
시뮬레이션(simulation)
- 실제로 실행하기 어려운 실험을 간단히 행하는 모의실험을 뜻함
- 특히 컴퓨터를 이용하여 모의실험을 할 때는 컴퓨터 시뮬레이션이라고 함
대기행렬(queue, waiting line)
- 은행의 창구, 마트의 계산대, 공항의 입국심사 창구의 수 등에서와 같이 대기행렬에 도착하는 것과 대기하는 것 그리고 서비스되는 일련의 프로세스들에 대한 모델링에 사용되는 통계적인 이론으로 수학적, 확률적 분석을 가능하게 해줌
- 즉, 시스템의 평균 대기시간, 서비스의 예측 등을 현재 상태를 기반으로 한 시스템의 확률을 기반으로 하여 성능을 측정하는데 유용하게 활용할수 있음
대기행렬 큐
여러 상황에 대해 최적의 시스템을 설계하기 위한 시뮬레이션에서 사용하는 큐로서 서비스를 받기 위해 기다리는 대기행렬과 대기시간을 모델링하는데 사용됨
- 예를 들어, 공항에 도착하는 입국자는 큐로 만든 대기행렬에 순서대로 들어가고, 입국 심사관은 큐에 있는 입국자들을 순서대로 처리하게 됨
우선순위(다중) 큐(priority queue)
다중큐(multi-queue)는 여러 개의 큐(multiple queue)들로 구성된 자료구조라 할 수 있음
우선순위 큐는 삽입된 순서에 상관없이 일정한 순서(우선순위)에 의해 삭제되는 자료구조로서 각각의 우선순위에 따라 여러 개의 큐로 구성할 수 있음
- 원소마다 우선순위(priority)가 존재 => 보통 key값으로 우선순위를 표현함
- 원소의 우선순위 연산
- 큐에 있는 가장 낮은(높은) 우선순위를 갖는 원소를 먼저 처리(삭제)함 - Min Priority Queue, Max priority Queue
- 동일한 우선순위를 갖는 요소가 두 개 이상 => FIFO 방식으로 처리함
- 스택과 큐도 우선순위 큐의 일종
- 스택 - 삽입시간이 가장 짧은 원소에 가장 높은 우선순위를 부여한 우선순위 큐
- 큐 - 삽입시간이 가장 오래된 원소에 가장 높은 우선순위를 부여한 우선순위 큐
- 우선순위 큐의 구현
- 배열 - 간단하게 구현이 가능하지만, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 이동해야 하는 연산이 필요하며, 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 함
시간복잡도 - 정렬된 배열 : 삽입 - O(n), 삭제 - O(1) 비 정렬된 배열 : 삽입 - O(1), 삭제 - O(n) - 연결리스트 - 삽입의 위치를 찾기 위해 첫 번째 노드부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행할 필요가 있음(성능 저하 초래)
- 힙(heap) - 구현이 어렵지만 연산이 가장 효율적임
- 배열 - 간단하게 구현이 가능하지만, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 이동해야 하는 연산이 필요하며, 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 함
힙 구조의 우선순위 큐
힙 구조의 성질
- 삽입할 원소는 원전 이진트리를 유지하는 형태로 순차적으로 삽입됨
- 삽입 이후에는 근노드까지 거슬러 올라가면서 최대 힙을 구성함 - 부모노드와 비교를 해서 부모노드가 삽입한 노드의 값보다 작다면 교체해야 함
- 시간복잡도 - O(log N)
우선순위 큐(priority queue)의 비교 연산
우선순위 큐에 있는 원소들의 순서쌍 관계
우선순위 큐의 전체순서(total order) 관계가 성립할 경우 => 우선순위 큐의 모든 원소들은 우선순위에 따라 정렬이 됨
- 완전순서관계 - 집합 A에 대한 부분순서관계 R에서 집합 A의 모든 원소들의 순서쌍을 비교할 수 있을 때
- 반사적(reflexive) 성질 = ki <= ki
- 반대칭(antisymmetric) 성질: k1 <= k2 이고, k2 <= k1 이면 k1 = k2
- 이행적(transitive) 성질 k1 <= k2 이고 k2 <= k3 이면 k1 <= k3
- 집합 A={1, 2, 3, 4}에 대해
- 비반사 - 관계 R1={(1, 1), (1, 2), (2, 1)}
- 반사 - 관계 R2={(1,1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
- 대칭 - 관계 R3={(1, 1), (1, 2), (2, 1)}
- 반대칭 - 관계 R4={(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
- 이행 - 관계 R5={(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
우선순위 큐(priority queue)의 구현
배열을 이용한 구현
1차원 배열을 이용한 우선순위 큐의 생성/삽입/삭제 프로그램
#include <stdio.h>
#define N 20
int Q[N], Pr[N]; // 독립된 우선순위 큐와 우선순위 값 20개를 저장할 수 있는
// 2개의 배열 선언
int r = -1, f = -1; //f와 r값을 -1로 초기화
void enqueue(int data, int p){ // 큐에 원소와 원소의 우선순위 값을 입력
int i;
if((f==0)&&(r==N-1))// 큐의 오버플로우를 검사
printf("큐에 원소를 삽입할 공간 없음");
else{
if(f==-1){ //큐가 비었는지 검사
f = r = 0; // 큐의 포인터와 f와 r를 0으로 설정
Q[r] = data; // 원소와 우선순위 값을 삽입
Pr[r] = p;
}
else if(r == N-1){ //큐에 r를 이용하여 삽입할 수 없지만 빈 공간이 있는 경우
for(i=f; i<=r; i++){ //원소 삽입을 위해 원소 이동
Q[i-f] = Q[i];
Pr[i-f] = Pr[i];
r = r-f;
f = 0;
for(i=r; i>f; i--){
if(p>Pr[i]){ //큐에 있는 원소와 삽입하는 원소의 우선순위 값 비교
Q[i+1] = Q[i]; //우선순위에 따라 원소 이동
Pr[i+1] = Pr[i];//우선순위에 따라 우선순위 값 이동
}
else
break;
Q[i+1] = data;
Pr[i+1] = p;
r++;
}
}
}
else{ //큐의 r이 N-1가 아니면서 임의의 원소가 있는 경우(이동이 필요없음)
for(i=r; i>=f; i--){//큐에 있는 원소와 삽입하는 원소의 우선순위 값 비교
if(p>Pr[i]){
Q[i+1] = Q[i];
Pr[i+1] = Pr[i];
}
else
break;
}
Q[i+1] = data;
Pr[i+1] = p;
r++;
}
}
}
void print(){//큐에 있는 모든 원소를 출력
int i;
for(i=f; i<=r; i++){
printf("\n원소 = %d\t우선순위 값 = %d", Q[i], Pr[i]);
}
}
int dequeue(){//큐에서 front를 통해 원소 삭제
if(f == -1){
printf("큐가 비어있음");
}
else{
printf("삭제된 원소 = %d\t 해당 원소의 우선순위 값 = %d", Q[f], Pr[f]);
if(f==r)
f = r = -1;
else
f++;
}
}
int main(){
int opt, n, i, data, p;
printf("\n------------메뉴------------");
do{
printf("\n\n1. 큐에 원소 삽입\n2. 큐에 있는 원소 출력 \n3. 큐에서 원소 삭제\n4. 종료\n");
printf("\n선택된 번호:");
scanf("%d",&opt);
switch(opt){
case 1:
printf("\n원소의 개수를 입력= ");
scanf("%d",&n);
printf("\n원소 값과 원소의 우선순위 값을 입력:\n");
i=0;
while(i<n){
scanf("%d %d", &data, &p);
enqueue(data, p); //enqueue()함수 호출 i++;
}
break;
case 2:
print(); //print()함수 출력
break;
case 3:
dequeue(); //dequeue()함수 호출
break;
case 4:
break;
default:
printf("\n잘못 선택된 번호");
}
}while(opt!=0)
return 0;
}
실행결과
1. 큐에 원소 삽입
2. 큐에 있는 원소 출력
3. 큐에서 원소 삭제
4. 종료
선택된 번호 : 1
원소의 개수를 입력= 2
원소 값과 원소의 우선순위 값을 입력:
10 2
20 1
1. 큐에 원소 삽입
2. 큐에 있는 원소 출력
3. 큐에서 원소 삭제
4. 종료
선택된 번호 : 2
원소 = 10 우선순위 값 = 2
원소 = 20 우선순위 값 = 1
데크(deque)
데크(double-ended queue)에서 의미하듯 큐 2개를 반대로 붙여서 만든 자료구조임
큐와 스택의 중간 정도의 특징을 가지며 두 가지로 분류
- L-pointer(front) => 데크의 왼쪽 끝을 가리키며, 삽입과 삭제가 이루어짐
- R-pointer(rear) => 데크의 오른쪽 끝을 가리키녀, 삽입과 삭제가 이루어짐
종류 - scroll(입력제한 데크), shelf(출력제한 데크)
오버 플로우를 방지하기 위해 중앙에서 삽입(이동현상 초래) => 환형으로 처리가 필요함
데크(deque)의 구현
두 개의 포인터를 이용한 데크의 생성/삽입/삭제 프로그램
#include <stdio.h>
#define MAX 10
void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);
int main() {
int arr[MAX]; //10개의 arr 배열로 데크를 선언
int front, rear, i, n;
front = rear = -1; //2개의 포인터 front와 rear를-1로 초기화
for (i = 0; i < MAX; i++)
arr[i] = 0; //데크(arr[])의 원소 값을0으로 초기화
addRear(arr, 5, &front, &rear); //원소들을 rear과 front를 이용하여 삽입
addFront(arr, 12, &front, &rear);
addRear(arr, 11, &front, &rear);
addFront(arr, 5, &front, &rear);
addRear(arr, 6, &front, &rear);
addFront(arr, 8, &front, &rear);
printf("데크에 있는 원소들: ");
display(arr); //arr[]의 원소들을 출력
i = delFront(arr, &front, &rear); //front를 통해 원소 삭제
printf("\n삭제된 원소: %d", i);
printf("\n삭제된 이후에 데크에 있는 원소들: ");
display(arr);
addRear(arr, 16, &front, &rear); //rear를 통해 원소 삽입
addRear(arr, 7, &front, &rear);
printf("\n삽입후 데크에 있는 원소들: ");
display(arr); i = delRear(arr, &front, &rear); //rear를 통해 원소 삭제
printf("\n삭제된 원소: %d", i);
printf("\n삭제된 이후에 데크에 있는 원소들: ");
display(arr);
n = count(arr);
printf("\n데크에 있는총 원소들의 개수: %d", n);
}
void addFront(int *arr, int item, int *pfront, int *prear){
int i, k, c;
if (*pfront == 0 && *prear == MAX - 1 ){ //오버플로우 조건 검사
printf("\n데크 오버플로우.\n");
return;
}
if (*pfront == -1 ){
*pfront = *prear = 0;
arr[*pfront] = item; //front 위치에 원소를 삽입
return;
}
if (*prear != MAX - 1 ){ //rear 위치에 원소를 삽입할 공간이 있으면
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++){
arr[k] = arr[k -1]; // rear 방향으로 원소들의 이동
k--;
}
arr[k] = item; // 변경된 위치에 원소 삽입 *pfront = k;
(*prear)++;
} else{ //front 방향으로 원소를 삽입할 수 있으면
(*pfront)--; //front-1 위치에 삽입
arr[*pfront] = item;
}
}
void addRear(int *arr, int item, int *pfront, int *prear){
int i, k;
if (*pfront == 0 && *prear == MAX - 1 ) {//오버플로우 조건 검사
printf("\n데크 오버플로우.\n");
return;
}
if (*pfront == -1 ){
*prear = *pfront = 0;
arr[*prear] = item; //rear 위치에 원소를 삽입
return;
}
if (*prear == MAX - 1 ){//rear 위치에 원소를 삽입할 공간이 없으면
k = *pfront- 1;
for (i = *pfront- 1; i<*prear; i++){
k = i;
if (k == MAX - 1 )
arr[k] = 0;
else
arr[k] = arr[i + 1]; // front 방향으로 원소들의 이동
}
(*prear)--; //rear와 front 위치를 변경
(*pfront)--;
}
(*prear)++;
arr[*prear] = item; //rear+1위치에 원소를 삽입
}
int delFront(int *arr, int *pfront, int *prear){
int item;
if (*pfront == -1 ) {
printf("\n데크 언더플로우.\n");
return 0;
}
item = arr[*pfront];
arr[*pfront] = 0; //front 위치에 0을 삽입
if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;
return item;
}
int delRear(int *arr, int *pfront, int *prear){
int item;
if (*pfront == -1 ) {
printf("\n데크 언더플로우.\n");
return 0;
}
item = arr[*prear];
arr[*prear] = 0; //rear 위치에 0을 삽입
(*prear)--;
if (*prear == -1 )
*pfront = -1;
return item;
}
void display(int *arr){ //데크에 있는 원소들을 출력
int i;
printf("\n front: ");
for (i = 0; i < MAX; i++)
printf(" %d", arr[i]);
printf(" :rear");
}
int count(int *arr){ //데크에 있는 원소의 개수를 파악
int c = 0, i;
for (i = 0; i < MAX; i++) {
if (arr[i] != 0)
c++;
}
return c;
}
실행결과
데크에 있는 원소들:
front: 8 5 12 5 11 6 0 0 0 0 :rear
삭제된 원소: 8
삭제된 이후에 데크에 있는 원소들:
front: 0 5 12 5 11 6 0 0 0 0 :rear
삽입 후 데크에 있는 원소들:
front: 0 5 12 5 11 6 16 7 0 0 :rear
삭제된 원소: 7
삭제된 이후에 데크에 있는 원소들:
front: 0 5 12 5 11 6 16 0 0 0 :rear
데크에 있는 총 원소들의 개수: 6