5장 큐.

5장 큐

순서 5.1 큐 추상 데이타 타입 5.2 큐의 순차 표현 5.3 C 배열을 이용한 큐의 구현 5.4 큐의 연결 표현
5.6 큐의 응용 5.7 우선 순위 큐 5.8 덱

큐 추상 데이타 타입(1) 큐(queue) 한쪽 끝(rear)에서는 삽입(enqueue)만, 또 다른 끝(front)에서는 삭제(dequeue)만 하도록 제한되어 있는 유한 순서 리스트(finite ordered list) 선입선출, First-In-First-Out(FIFO) 리스트 큐에서 제일 먼저 삽입된 원소가 제일 먼저 삭제될 원소가 됨 선착순 서버, first-come-first-serve (FCFS) 시스템 서비스를 받기 위한 대기 행렬로 볼 수 있음 큐의 작동 구조 삭제 삽입 front rear

큐 추상 데이타 타입(2) 큐에서의 삽입과 삭제 큐의 응용 사례 f : front, r : rear
운영 체제 : 작업 큐를 통한 제출 순서에 따른 작업 스케줄 서비스를 기다리는 작업들의 대기 상태를 나타내는 데 적절 f r f r f r f r f r f r A A B A B C A B C D B C D C D 삽입(A) 삽입(B) 삽입(C) 삽입(D) 삭제 삭제

큐 추상 데이타 타입(3) 큐 추상 데이타 타입(ADT Queue) ADT Queue
데이타 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 : Q ∈ Queue; item ∈ Element; createQ() ::= create an empty queue; enqueue(Q, item) ::= insert item at the rear of Q; isEmpty(Q) ::= if (Q is empty) then return true else return false; dequeue(Q) ::= if (isEmpty(Q)) then return null else remove and return the front element of Q; remove(Q) ::= if (isEmpty(Q)) then return null else remove the front element of Q; peek(Q) ::= if (isEmpty(Q)) then return null else return the front element of Q; End Queue

큐의 순차 표현(1) 1차원 배열 큐를 표현하는 가장 간단한 방법 Q[n]을 이용한 순차 표현 순차 표현을 위한 변수
두 인덱스 변수 front, rear 초기화 : front = rear = -1 (공백큐) 공백큐 : front = rear 만원 : rear = n-1

큐의 순차 표현(2) 큐의 연산자(1) createQ() // 공백 큐(Q[])를 생성 Q[n];
front ← -1; // 초기화 rear ← -1; end createQ() isEmpty(Q) // 큐(Q)가 공백인지를 검사 return (front = rear); end isEmpty() // 이 is Empty 연산자는 아주 간단해서 직접 구현하여 사용할 수도 있다. enqueue(Q, item) // 큐(Q)에 원소를 삽입 // Q에 원소 삽입 if (rear=n-1) then queueFull(); // Q가 만원인 상태를 처리 else rear ← rear + 1; Q[rear] ← item; end enqueue()

큐의 순차 표현(3) 큐의 연산자(2) dequeue(Q) // Q에서 원소를 삭제하여 반환
if (isEmpty(Q)) then return null; // Q가 공백인 상태를 처리 front ← front + 1; return Q[front]; end dequeue() remove(Q) // Q에서 원소를 삭제 if (isEmpty(Q)) then return null; // 큐(Q)가 공백인 상태를 처리 end remove() peek(Q) // Q에서 원소를 검색 if (isEmpty(Q)) then return null; // 큐(Q)가 공백인 상태를 처리 else return Q[front+1]; end peek()

큐의 순차 표현(4) 순차 표현의 문제점 원형 큐(circular queue) Rear=n-1인 경우
큐의 앞에서 삭제로 인해 비 공간이 생길 수 있음 빈공간을 없애기 위해 앞쪽으로 이동, front‧rear 재설정  시간, 연산의 지연 문제 실제로 큐가 만원인 경우 배열의 크기를 확장해야 함 원형 큐(circular queue) 순차 표현의 문제점 해결 위해 배열 Q[n]을 원형으로 운영 원형 큐의 구현 초기화 : front = rear = 0 (공백큐) 공백큐 : front = rear 원소 삽입 : rear를 하나 증가시키고, 그 위치에 원소 저장 만원 : rear를 하나 증가시켰을 때, rear = front (실제 front 공간 하나가 비지만, 편의를 위해 그 공간을 희생)

큐의 순차 표현(5) 원형 큐의 여러 상태 1차원 배열을 원형으로 유지하는 방법 mod(modulus) 연산자 이용
삽입을 위해 먼저 rear를 증가시킬 때 : rear  (rear+1) mod n rear 값은 n-1 다음에 n이 되지 않고, 다시 0으로 되돌아감 삭제를 위해 front를 증가시킬 때 : front  (front+1) mod n rear와 마찬가지로, front 값은 n-1 다음에 0이 되어 원형으로 순환 [n-2] [0] ... [1] [n-1] [n-2] [0] ... a 1 [1] [2] [n-1] [n-2] [n-1] [0] ... a 1 [1] [2] n-3 n-2 front = [0] rear = [0] (a) 공백 원형 큐 front = [0] rear = [2] front = [0] rear = [n-1] (c) 만원 원형 큐 (b) 2개의 원소 저장

큐의 순차 표현(6) 원형 큐에서의 enqueue와 dequeue 연산 enqueue(Q, item)
rear ← (rear+1) mod n; // 원형 큐(Q) 인덱스 if (front=rear) then queueFull(); // 큐(Q)가 만원인 상태를 처리 Q[rear] ← item; end enqueue() dequeue(Q) // 원형 큐(Q)에서 원소를 삭제하여 반환 if (front=rear) then return null; //큐(Q)가 공백인 상태를 처리 else { front ← (front+1) mod n; // 원형 인덱스 return Q[front]; } end dequeue()

C 배열을 이용한 큐의 구현(1) Queue를 구현하기 위한 기본 함수 프로토타입
int isEmpty(int *front, int rear); // 큐가 공백인가를 검사 void enqueue(int *rear, element item); // element 타입의 원소를 삽입 element dequeue(int *front, int rear); // element 타입의 원소를 삭제하여 반환 void delete(int *front, int rear); // 원소를 삭제 element peek(int front, int rear); // element 타입의 원소를 검색

C 배열을 이용한 큐의 구현(2) 1차원 배열(queue[])를 이용한 큐의 구현(1) /* C 배열을 이용한 큐의 구현*/
#define Q_SIZE 100 /* 최대 큐 크기 */ typedef int element; element queue[Q_SIZE]; void enqueue(int *rear, element item) { if(*rear == Q_SIZE-1) { /* 큐가 만원인 경우를 처리 */ printf("Queue is full\n"); return; } queue[++*rear] = item; } int isEmpty (int *front, int rear) { if (*front == rear) return 1; /* 큐가 공백인 경우 */ else return 0;

C 배열을 이용한 큐의 구현(3) 1차원 배열(queue[])를 이용한 큐의 구현(2)
element dequeue(int *front, int rear) { if (*front == rear) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else return queue[++*front]; } void delete(int *front, int rear) { if (*front == rear) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); } else ++*front;

C 배열을 이용한 큐의 구현(4) 1차원 배열(queue[])를 이용한 큐의 구현(3)
element peek(int front, int rear) { if (front == rear) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else { return queue[front+1]; }

C 배열을 이용한 큐의 구현(5) 1차원 배열(queue[])를 이용한 큐의 구현(4) int main( void ) {
int front = -1; /* 삭제 연산 인덱스 */ int rear = -1; /* 삽입 연산 인덱스 */ element data; enqueue(&rear, 1); enqueue(&rear, 2); data = peek(front, rear); printf("data=%d\n", data); data = dequeue(&front, rear); data = dequeue(&front, rear); return 0; }

큐의 연결 표현(1) 연결리스트로 표현된 큐 여러 개의 큐를 동시에 필요로 하는 경우에 효율적
연결 큐(linked queue)의 구조 단순 연결 리스트를 두 개의 포인터 변수 front, rear로 관리 초기화 : front = rear = null (공백큐) 큐의 공백 여부 : front 또는 rear가 null인지 검사를 통해 알 수 있음 front rear data link null

큐의 연결 표현(2) 연결 큐에서의 삽입, 삭제, 검색 연산 구현(1)
enqueue(Q, item) // 연결큐(Q)에 item을 삽입 newNode ← getNode(); // 새로운 노드를 생성 newNode.data ← item; newNode.link ← null; if (rear = null) then { // Q가 공백인 경우 rear ← newNode; front ← newNode; } else { rear.link ← newNode; end enqueue() dequeue(Q) // 큐(Q)에서 원소를 삭제하고 값을 반환 if (front = null) then return null; // Q가 공백인 경우 oldNode ← front; item ← front.data; front ← front.link; if (front = null) then rear ← null; // 삭제로 인해 Q가 공백이 되는 이유 retNode(oldNode); return item; end dequeue()

큐의 연결 표현(3) 연결 큐에서의 삽입, 삭제, 검색 연산 구현(2) delete(Q) // 큐(Q)에서 원소를 삭제
if (front = null) then queueEmpty(); // 큐(Q)가 공백인 경우 else { oldNode ← front; front ← front.link; if (front = null) then rear ← null; retNode(oldNode); } end delete() peek(Q) // 큐(Q)의 front 원소를 검색 if (front = null) then queueEmpty(); // 큐(Q)가 공백인 경우 else return (front.data); end peek()

큐의 연결 표현(4) 연결큐의 특징 k개의 큐를 사용 삽입, 삭제로 인한 다른 원소들의 이동이 필요 없음 연산이 신속하게 수행
여러 개의 큐 운영시에도 연산이 간단 링크 필드에 할당하는 추가적인 저장 공간 필요 k개의 큐를 사용 큐0, 큐1, 큐2, …, 큐k-1 각 큐에 대한 front와 rear : 배열 front[i], rear[i]를 사용 초기화 front[i]  null; 0≤i<k rear[i]  null; 0≤i<k

큐의 연결 표현(5) m개의 큐에서의 삽입, 삭제, 검색 연산 구현(1) enqueue(i, item)
newNode ← getNode(); newNode.data ← item; newNode.link ← null; if (front[i] = null) then { // 큐 i가 공백인 경우 front[i] ← newNode; rear[i] ← newNode; } else { // 큐 i가 공백이 아닌 경우 rear[i].link ← newNode; end enqueue()

큐의 연결 표현(6) m개의 큐에서의 삽입, 삭제, 검색 연산 구현(2) dequeue(i)
if (front[i] = null) then queueEmpty(); // 큐 i가 공백인 경우 else { oldNode ← front[i]; item ← front[i].data; front[i] ← front[i].link; if(front[i] = null) then rear[i] ← null; // 큐 i가 공백이 된 경우 retNode(oldNode); // 노드를 가용 공간 리스트에 반환 return item; } end dequeue()

큐의 연결 표현(7) m개의 큐에서의 삽입, 삭제, 검색 연산 구현(3) delete(i) // 큐 i에서 원소를 삭제
if (front[i] = null) then queueEmpty(); else { oldNode ← front[i]; front[i] ← front[i].link; if(front[i] = null) then rear[i] ← null; retNode(oldNode); } end delete() peek(i) // 큐 i에서 원소 값을 검색 if (front[i] = null) then queueEmpty(); else return (front[i].data); end peek()

C 리스트를 이용한 큐의 구현(1) 원소 데이타 · 노드 · 연결 큐 타입
원소 데이타 · 노드 · 연결 큐 타입 typedef struct { /* 큐의 struct 원소 타입 */ int id; char name[10]; char grade; } element ; typedef struct queueNode { /* 연결 큐의 노드 타입 */ element data; struct queueNode* link; } queueNode ; typedef struct { /* 연결 큐 데이타 타입 */ queueNode* front; /* 삭제연산 포인터 */ queueNode* rear; /* 삽입연산 포인터 */ int length; /* 큐(리스트)의 원소 수를 표현 */ } linkedQueue ;

C 리스트를 이용한 큐의 구현(2) 큐를 구현한 연결 리스트 표현 n개의 노드(원소)로 구성된 연결 큐 1 null null
front rear length X 1 data link 2 null … n개의 노드(원소)로 구성된 연결 큐 1 length rear front null link data front rear length null 공백 연결 큐 하나의 노드를 가진 연결 큐

C 리스트를 이용한 큐의 구현(3) 연결 리스트로 큐를 구현한 C 프로그램(1) #include <stdio.h>
#include <stdlib.h> typedef struct { /* 연결 큐의 struct 원소 타입 */ int id; char name[10]; char grade; }element ; typedef struct queueNode { /* 연결 큐의 노드 타입 */ element data; struct queueNode* link; } queueNode ; typedef struct { /* 연결 큐 데이타 타입 */ queueNode* front; /* 삭제연산 포인터 */ queueNode* rear; /* 삽입연산 포인터 */ int length; /* 큐(리스트)의 원소 수를 표현 */ }linkedQueue ;

C 리스트를 이용한 큐의 구현(4) 연결 리스트로 큐를 구현한 C 프로그램(2) linkedQueue* createQ() {
linkedQueue* q q = (linkedQueue*)malloc(sizeof(linkedQueue)); q->front = NULL; q->rear = NULL; q->length = 0; return q; } int isEmpty (linkedQueue* q) { /* 연결 큐가 공백인가를 검사 */ return (q->length == 0);

C 리스트를 이용한 큐의 구현(5) 연결 리스트로 큐를 구현한 C 프로그램(3)
void enqueue(linkedQueue* q, element item) { /* 연결 큐에 원소를 삽입 */ queueNode* newNode; newNode = (queueNode*)malloc(sizeof(queueNode)); newNode->data = item; newNode->link = NULL; if (q->length==0) { /* 연결 큐가 공백인 경우 */ q->front = q->rear = newNode; } else { q->rear->link = newNode; q->rear = newNode; q->length++; }

element dequeue(linkedQueue* q) { /* 연결 큐에서 원소를 삭제하고 반환 */ queueNode* temp; element item; if (q->length==0) { /* 연결 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else { item = q->front->data; temp = q->front; q->front = q->front->link; if (q->front == NULL) q->rear = NULL; q->length--; free(temp); /* 삭제된 노드를 반환 */ return item; } }

void delete(linkedQueue* q) { /* 연결 큐에서 원소를 삭제 */ queueNode* temp; if (q->length==0) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else { temp = q->front; q->front = q->front->link; if (q->front == NULL) q->rear = NULL; q->length--; free(temp); /* 삭제된 노드를 반환 */ } }

element peek(linkedQueue* q) { /* 연결 큐에서 원소를 검색 */ if (q->length == 0) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else return q->front->data; } int main() { element item; linkedQueue* q; q = createQ(); item.id = 123; strcpy(item.name, "Hong"); item.grade ='A'; enqueue(q, item); · · · }

큐의 응용 - 운영체제에서 큐 운영체제에서 큐의 응용
상이한 속도로 실행하는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당 예: CPU와 프린터 사이의 프린트 버퍼(printBufferQueue) 프린트 버퍼에서의 판독과 기록 작업 writeLine() // CPU가 프린트 해야 할 라인을 프린트 버퍼 큐에 삽입 if (there is a line L to print) and (printBufferQueue ≠ full) and (printBufferQueue ≠ busy) then enqueue(printBufferQueue, L); end writeLine() readLine() // 프린터가 프린트 버퍼 큐의 라인들을 프린트 if(printBufferQueue ≠ empty) and (printBufferQueue ≠ busy) then { L ← dequeue(printBufferQueue); print L; } end readLine()

컴퓨터 시뮬레이션(1) 시뮬레이션의 정의 어떤 물리적 시스템의 행태를 분석하고 예측하기 위해 컴퓨터 모델을 통해 시뮬레이트하는 것 물리적 시스템 특정 목적을 달성하기 위해 동작하고 상호 작용하는 독립적인 원소나 개체의 집합

컴퓨터 시뮬레이션(2) 물리적 시스템의 상태 일련의 상태 변수(state variable)를 사용하여 표현
공항의 항공기 교통 시뮬레이션 예 개체: 항공기 상태: 항공기의 상태 (공중, 지상에서 착륙이나 이륙) 보통 시간대별로 측정 연속적 시스템(continuous system) 시뮬레이션 시스템 상태는 시간에 따라 연속적으로 변함 이산 시스템(discrete system) 시뮬레이션 상태 변수들은 어떤 특정 사건 발생 시점에서만 변함

컴퓨터 시뮬레이션(3) 시뮬레이션에서의 시간
물리적 시스템에서의 시간을 의미하는 시뮬레이트 되는 시간 (simulated time)과 시뮬레이션 프로그램에서의 연산 시간 (computation time)을 분명하게 구별 해야함 대부분의 경우 시뮬레이트 되는 시간보다 연산 시간이 훨씬 짧음 예 : 기상 예측 시스템

컴퓨터 시뮬레이션(4) 큐잉 시스템(queueing system) 큐잉 시스템의 특징 큐잉 시스템의 종류
대부분의 물리적 시스템을 모델링 서비스를 기다리는 대기선(waiting line)을 가진 시스템 대기선 : 큐의 선입선출(FIFO) 성질을 만족 큐잉 시스템의 종류 단일 서버 큐잉 시스템 다중 큐 다중 서버 큐잉 시스템 큐잉 네트워크

컴퓨터 시뮬레이션(5) 단일 서버 큐잉 시스템 단일 큐, 단일 서버로 구성 시뮬레이트 가정
고객 도착 시간 간격의 분포 : 고객들의 도착시간은 어떤 확률 분포 함수 A(t)에 따라 상이하다고 가정 서비스 시간 분포 : 개개 고객의 서비스 시간은 어떤 확률 분포 함수 S(t)에 따라 상이하게 제공된다고 가정 위의 정보를 기초로 큐의 평균 길이, 고객의 평균 대기 시간, 서버의 작업 처리 능력 등을 분석 서버 완료 큐 도착

컴퓨터 시뮬레이션(6) 큐잉 시스템 시뮬레이션 구성 요소 시뮬레이션에 필요한 자료 시뮬레이션의 종류
고객 큐 : 대기선을 모델링 서버 : 고객들을 서비스 스케줄러 : 시뮬레이션하는 동안 사건이 일어날 시간을 스케줄 시뮬레이션에 필요한 자료 새로운 고객 도착 : 확률 분포 함수 A(t)에 따라 정해지는 시간 서비스 받고 시스템 나감 : 확률 분포 함수 S(t)에 따라 결정되는 시간 시뮬레이션의 종류 시간 중심 시뮬레이션(time-driven simulation) 시뮬레이션 클록에 일정 단위 시간을 계속적으로 증가시키면서 시뮬레이션을 수행 사건 중심 시뮬레이션(event-driven simulation) 시뮬레이션 클록을 사건이 발생할 때마다 경과된 시간을 증가시키고, 상태 변수를 갱신하면서 시뮬레이션을 수행

컴퓨터 시뮬레이션(7) 단일 서버 큐잉 시스템 시뮬레이션(1)
timeDrivenSimulation(startSimulation, endSimulation) // startSimulation: 시뮬레이션 시작 시간 // endSimulation: 시뮬레이션 종료 시간 // 필요한 여러 상태 변수들을 초기화 clock ← startSimulation; // 시뮬레이션 시계(clock) arrivalTime; // 고객이 서비스를 받기 위해 시스템에 도착한 시간 leaveTime; // 고객이 서비스를 받고 떠나는 시간 serverState; // 서버의 busy(서비스 중) 또는 idle(휴식 중) 상태를 표현 tick; // 시뮬레이션 시계의 단위 시간 queue; // 고객이 서비스를 받기 위해 대기하는 큐

while (clock < endSimulation) do { // 시뮬레이션 종료 시간이 되지 않은 경우 clock ← clock + tick; // 클록의 단위 시간을 증가 if (clock ≥ arrivalTime) then { // 새로운 고객이 도착한 경우 enqueue(queue, customer); // 고객(customer), arrivalTime은 큐로 들어가 서비스를 대기 update(statistics); // 통계 분석 데이타(statistics) 처리 arrivalTime ← clock + arrival(clock); // 다음 고객 도착 시간을 생성 // arrival(): 고객의 도착 시간 간격 } if (clock ≥ leaveTime) then // 고객의 서비스가 완료된 경우 serverState ← idle; // 서버는 쉬는 상태로

if (serverState = idle and not isEmpty(queue)) then { // 다음 고객을 서비스할 수 있는가를 점검 dequeue(queue); // 다음 차례의 고객에 서비스 시작 update(statistics); // 통계 분석 데이타(statistics) 처리 serverState ← busy; // 서버를 서비스 중인 상태로 leaveTime ← clock + service(clock); // 고객이 서비스를 받고 떠나는 시간을 설정 // service(t): 고객의 서비스 시간 생성 } } // end while end timeDrivenSimulation()

컴퓨터 시뮬레이션(10) 복잡한 큐잉 시스템 다중 큐 다중 서버 큐잉 시스템 큐잉 네트워크 Q1 S1 Q2 도착 S2 완료
... ... Qk Sm 도착 완료 Q1 Q2 Q3 S1 S2 S3

우선 순위 큐(1) 우선 순위 큐(priority queue)
원소에 부여된 우선 순위에 따라 우선 순위가 가장 높은 원소부터 삭제하는 자료 구조 스택과 큐도 우선 순위 큐의 일종 스택 : 삽입 시간이 가장 짧은 원소에 가장 높은 우선 순위를 부여한 우선 순위 큐 큐 : 삽입 시간이 가장 오래된 원소에 가장 높은 우선 순위를 부여한 우선 순위 큐 원소의 우선 순위 표현과 연산 보통 우선 순위 key 값을 사용 삭제시 : 우선 순위가 가장 높은 원소가 제일 먼저 삭제 삽입 : 우선 순위와 관계없이 임의의 순서로 언제나 수행

우선 순위 큐(2) 우선 순위 큐(priority queue) 추상 데이타 타입 ADT PriorityQueue 데이타 :
우선순위를 가진 0개 이상의 원소로 된 수집(collection) 연산 : pQ ∈ PriorityQueue; item ∈ Element; createQ() ::= create an empty priority queue; length(pQ) ::= return the number of items in pQ; insert(pQ, item) ::= insert the item into pQ; delete(pQ) ::= if (isEmpty(pQ)) then return error else {delete the item with the highest priority from pQ}; End PriorityQueue

우선 순위 큐(3) 원소들의 비교 연산 우선 순위 큐의 전체 순서(total order) 관계 성립
1) 반사적(reflexive) 성질 : ki ≤ ki 2) 반대칭(antisymmetric) 성질 : k1 ≤ k2 이고 k2 ≤ k1 이면, k1 = k2 3) 이행적 성질(transitive) : k1 ≤ k2 이고 k2 ≤ k3 이면, k1 ≤ k3 우선 순위 큐의 모든 원소 : 우선 순위에 따라 일렬로 정렬

C에서의 우선순위 큐(1) PriorityQueue 구현을 위한 기본 함수 프로토타입
priorityQ* createQ(void); /* 공백 우선순위 큐의 생성 */ void insert(priorityQ* pQ, element item); /* 우선순위 큐 pQ에 원소 item을 삽입 */ element delete(priorityQ* pQ); /* 큐 pQ에서 우선순위가 제일 높은 원소를 삭제하여 반환 */

C에서의 우선순위 큐(2) 우선순위 큐 정렬 함수 우선 순위 큐 정렬(priority queue sorting)을 구현
void priorityQsort(int *a, int length) { int i; priorityQ* pQ; pQ = createQ(); /* 공백 우선순위 큐를 생성 */ for (i = 0; i < length; i++) { insert(pQ, a[i]); /*배열 a[]의 모든 원소를 우선순위 큐 pQ에 삽입 */ } for (i = length-1; i >=0; i--) { a[i] = delete(pQ); /*우선순위 큐 pQ에 있는 원소를 모두 배열 a[]로 다시 이동 */ }

C에서의 우선순위 큐(3) 우선순위 큐 정렬 C 프로그램(1) 정수 값을 우선 순위 큐 정렬 방법으로 정렬
void main() { int i; int n = 10; /*정렬할 원소 수 */ element data[]; data = (element*)malloc(n*sizeof(element)); for (i = 0; i < n; i++) { data[i].key = (3*i-13)*(3*i-13); /*정수 키 값을 가진 10개의 원소를 생성하여 저장 */ printf("%d, ", data[i].key); /*배열 data[]에 저장된 원소의 키 값을 프린트 */ /* : 169, 100, 49, 16, 1, 4, 25, 64, 121, 196 */ } printf("\r\n"); priorityQsort(data, n); /*배열 data[]를 priorityQsort()로 정렬 */ printf("%d, ", data[i].key); /*정렬된 배열 data[]의 각 원소의 키 값을 프린트 */ /* : 196, 169, 121, 100, 64, 49, 25, 16, 4, 1 */ printf("\r\n"); free(data); }

C에서의 우선순위 큐(4) 우선순위 큐 정렬 C 프로그램(2)
void priorityQsort(element* a, int size) { int i; priorityQ* pQ; pQ = createQ(); /* 공백 우선순위 큐를 생성 */ for (i = 0; i < size; i++) { insert(pQ, a[i]); /*배열 a[]의 모든 원소를 우선순위 큐 pQ에 삽입 */ } for (i = size-1; i >=0; i--) { a[i] = delete(pQ); /*우선순위 큐 pQ에 있는 원소를 모두 배열 a[]로 다시 이동 */ free(pQ); }

C 우선순위 큐의 구현(1) 정렬된 연결 리스트를 이용한 구현(1) 정렬된 연결 리스트
원소의 우선 순위에 따라 내림차순으로 유지 삭제 : 단순히 리스트의 첫 번째 노드를 삭제 삽입 : 원소의 우선 순위에 알맞은 위치에 저장 삭제 연산의 비용은 적고, 삽입 연산의 비용은 큼 struct element, struct pListNode Struct pListNode : 연결 리스트의 노드 구조의 정의 typedef struct { /* 큐의 struct 원소 타입 */ int key; /* 우선순위 값을 표현 */ char name[10]; char grade; }element ; typedef struct pListNode { element data; struct pListNode* link; } pListNode;

C 우선순위 큐의 구현(2) 정렬된 연결 리스트를 이용한 구현(2) 정렬된 연결 리스트로 구현한 C 프로그램(1)
// 정렬된 연결 리스트로 구현한 우선 순위 큐 typedef struct { /* 큐의 struct 원소 타입 */ int key; /* 우선순위 값을 표현 */ char name[10]; char grade; }element ; typedef struct pListNode { element data; struct pListNode* link; } pListNode; typedef struct { /* 우선순위 연결 큐의 헤더 */ int length; /* 큐의 원소 수 */ struct pListNode* head; /* 첫 번째 리스트 노드에 대한 포인터 */ } priorityQ;

priorityQ* createQ() { /* 공백 연결 우선순위 큐를 생성 */ priorityQ* pQ; pQ = (priorityQ*)malloc(sizeof(priorityQ)); pQ->length = 0; pQ->head = NULL; return pQ; } int compareTo(element item1, element item2) { /* insert() 함수의 보조 함수 */ int a = item1.key; int b = item2.key; return ((a==b) ? 0 : ((a>b) ? 1 : -1));

pListNode* sortedInsert(pListNode* p, element item) { pListNode* newNode; /* 우선순위에 따라 원소를 삽입 */ if ((p==NULL) || compareTo(item, p->data) >= 0) { /* p가 null이거나 새로 삽입할 item의 우선순위가 */ /* p가 가리키는 원소의 우선순위보다 크거나 같은 경우 */ newNode = (pListNode*)malloc(sizeof(pListNode)); newNode->data = item; newNode->link = p; return (newNode); /* 새로운 리스트 포인터 */ } else { /* item의 우선순위가 p가 가리키는 원소의 우선순위보다 */ /* 작은 경우, p.link가 가리키는 리스트에 item을 삽입 */ p->link = sortedInsert(p->link, item); return (p); }

element delete(priorityQ* pQ) { element item; pListNode* temp; if (pQ->length == 0) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else { item = pQ->head->data; temp = pQ->head; pQ->head = pQ->head->link; pQ->length--; free(temp); return item; } }

C 우선순위 큐의 구현(6) 무정렬 배열을 이용한 우선순위 큐의 구현(1) 무정렬 배열
배열 내 : 우선 순위 키 값을 가진 원소를 임의의 순서로 유지 삽입 : 단순히 새로운 원소를 배열의 끝에 첨가 삭제 : 우선 순위가 제일 높은 원소를 찾은 뒤 삭제,이 삭제된 빈 자리에 배열의 끝에 있는 원소를 이동 삽입 연산은 간단, 삭제 연산은 복잡

C 우선순위 큐의 구현(7) 무정렬 배열을 이용한 우선순위 큐의 구현(2) 무정렬 배열로 구현한 C 프로그램(1)
#include <stdio.h> #include <stdlib.h> typedef struct { /* 큐의 struct 원소 타입 */ int key; /* 우선순위 값을 표현 */ char name[10]; char grade; }element ; typedef struct { /* 무정렬 배열로 구현한 우선순위 큐 타입 */ int length; /* 실제로 큐에 저장되어 있는 원소 수 */ int qSize; /* 우선순위 큐의 크기 */ int increment; /* 배열 확장 단위 */ element* data; /* 우선순위 큐의 원소를 저장하는 배열 */ } priorityQ;

priorityQ* createQ() { /*공백 우선순위 큐 생성 */ priorityQ* pQ; pQ = (priorityQ*)malloc(sizeof(priorityQ)); pQ->length = 0; pQ->qSize = 20; pQ->increment = 5; pQ->data = (element*)malloc(pQ->qSize * sizeof(element)); return pQ; } int compareTo(element item1, element item2) { int a = item1.key; int b = item2.key; return ((a==b) ? 0 : ((a>b) ? 1 : -1)); }

void queueFull(priorityQ* pQ) { /* 우선순위 큐의 크기를 확장 */ int i; element* temp; pQ->qSize += pQ->increment; /* 확장된 크기의 임시 배열을 생성 */ temp =(element*) malloc(pQ->qSize * sizeof(element)); for (i = 0; i < pQ->length; i++){ /* 기존의 원소를 임시 배열로 이동 */ temp[i] = pQ->data[i]; } free(pQ->data); pQ->data = temp; /* 배열 포인터를 변경 */ } void insert(priorityQ* pQ, element item) { /* 우선순위 큐에 원소를 삽입 */ if (pQ->length == pQ->qSize) queueFull(pQ); /* 큐가 만원인 경우 queueFull을 호출 */ pQ->data[pQ->length++] = item;

element delete(priorityQ* pQ) { /* 우선순위가 제일 높은 원소를 삭제하여 반환 */ int maxIndex, i; element maxValue; if (pQ->length == 0) { /* 큐가 공백인 경우 */ printf("Queue is empty\n"); exit(1); } else { maxIndex = 0; /* 첫 번째 원소의 우선순위가 제일 높다고 가정 */ maxValue = pQ->data[0]; for (i = 1; i < pQ->length; i++) { if (compareTo(pQ->data[i], maxValue) > 0) { maxIndex = i; /* 우선순위가 제일 높은 원소의 위치 */ maxValue = pQ->data[i];/* 우선순위가 제일 높은 원소의 값 */ } } pQ->data[maxIndex] = pQ->data[--pQ->length]; /* 배열의 마지막 원소를 이동시키고 원소 수를 감소 */ return maxValue; } }

스트링 타입 원소를 위한 C 우선순위 큐(1) 정렬된 연결 리스트 이용
정수 타입 키 값 대신 스트링 타입의 우선순위 키 값을 갖는 원소를 처리할 수 있는 우선순위 큐로 수정 정수 타입 vs. 스트링 타입의 compareTo() 함수 키 값을 비교하는 compareTo() 함수 수정 필요 int compareTo(element item1, element item2) { /* 정수 타입의 우선순위 키 값을 비교하는 compareTo() 함수 int a = item1.key; int b = item2.key return ((a==b) ? 0 : ((a>b) ? 1 : -1)); } /* 스트링 타입의 우선순위 키 값을 위한 compareTo() 함수 return strcmp(item1.name, item2.name)

스트링 타입 원소를 위한 C 우선순위 큐(2) 우선순위 큐를 이용한 스트링 정렬(1) void main() { int i;
int n = 7; /* 정렬할 원소 수 */ char* names[] = {"Kim", "Cho", "Lee", "Koh", "Pak", "Han", "Yoo"}; element* data = (element*)malloc(n * sizeof(element)); for (i = 0; i < n; i++) { strcpy(data[i].name, names[i]); printf("%s, ", data[i].name); } printf("\r\n"); priorityQsort(data, n); /* 배열 data[]를 priorityQsort()로 정렬 */ printf("%s, ", data[i].name); printf("\r\n"); free(data); }

스트링 타입 원소를 위한 C 우선순위 큐(3) 우선순위 큐를 이용한 스트링 정렬(2)
void priorityQsort(element *a, int length) { int i; priorityQ* pQ; pQ = createQ(); for (i = 0; i < length; i++) { insert(pQ, a[i]); /* 배열 a[]의 모든 원소를 우선순위 큐 pQ에 삽입 */ } for (i = length-1; i >=0; i--) { a[i] = delete(pQ); /* 우선순위 큐 pQ에 있는 원소를 모두 배열 a[]로 다시 이동 */ free(pQ); }

덱(1) 덱(deque : double-ended queue) 스택과 큐의 성질을 종합한 순서 리스트
“deck” 또는 “DQ”라 읽음 삽입과 삭제가 리스트의 양끝에서 임의로 수행될 수 있는 자료구조 스택이나 큐 ADT이 지원하는 연산을 모두 지원

덱(2) 덱의 추상 데이타 타입(ADT) createDeque() ::= create an empty deque;
insertFirst(Deque,e) ::= insert new element e at the beginning of Deque; insertLast(Deque,e) ::= insert new element e at the end of Deque; isEmpty(Deque) ::= if Deque is empty then return true else return false; deleteFirst(Deque) ::= if isEmpty(Deque) then return null else remove and return the first element of Deque; deleteLast(Deque) ::= if isEmpty(Deque) then return null else remove and return the last element of Deque; removeFirst(Deque) ::= if isEmpty(Deque) then return null else remove the first element of Deque; removeLast(Deque) ::= if isEmpty(Deque) then return null else remove the last element of Deque; peekLast(Deque) ::= return the last element of Deque; peekFirst(Deque) ::= return the first element of Deque;

덱(3) 공백 덱에 대한 일련의 연산 수행 연산 덱(Deque) insertFirst(Deque,3) (3)
(5, 3) deleteFirst(Deque) insertLast(Deque,7) (3, 7) (7) deleteLast(Deque) () insertFirst(Deque,9) (9) (9, 7) (3, 9, 7) insertLast(Deque,5) (3, 9, 7, 5)

덱(4) 스택과 큐 ADT 연산에 대응하는 덱의 연산 스택 ADT 연산에 대응하는 연산 큐 ADT 연산에 대응하는 연산
스택 연산 덱 연산 createStack() createDeque() push(S,e) insertLast(Deque,e) isEmpty(S) isEmpty(Deque) pop(S) deleteLast(Deque) remove(S) removeLast(Deque) peek(S) peekLast(Deque) 큐 연산 덱 연산 createQ() createDeque() enqueue(Q,e) insertLast(Deque,e) isEmpty(Q) isEmpty(Deque) dequeue(Q) deleteFirst(Deque) remove(Q) removeFirst(Deque) peek(Q) peekFirst(Deque)

덱(5) 덱의 구현 단순 연결 리스트 이중 연결 리스트 이점 : 리스트의 마지막 노드를 가리키는 포인터를 이용
단점 : 리스트 마지막 노드의 삭제를 상수 시간에 수행할 수 없음 이중 연결 리스트 이점 : 리스트 양쪽 끝에서 삽입과 삭제가 상수 시간에 수행 first 링크, last 링크 사용 리스트의 첫 번째 노드와 마지막 노드만을 가리킴 다른 데이타를 저장할 목적이 아님

덱(6) 이중 연결 리스트를 이용한 덱 공백 이중 연결 덱 3개의 원소를 포함한 이중 연결 덱
Length = 0, first = last = null 3개의 원소를 포함한 이중 연결 덱 null deque length first last 3 deque length first last null X3 llink data rlink X2 X1

덱(7) 이중 연결 리스트를 이용한 덱 구현(1) #include <stdio.h>
#include <stdlib.h> typedef struct { int key; char name[10]; char grade; }element ; typedef struct doubleListNode { element data; struct doubleListNode* rlink; struct doubleListNode* llink; } deqNode; deqNode* first; deqNode* last; int length; } deque;

덱(8) 이중 연결 리스트를 이용한 덱 구현(2) deque* createDeque() { /* 공백 이중 연결 덱을 생성 */ deque* deq; deq = (deque *)malloc(sizeof(deque)); deq->first = NULL; deq->last = NULL; deq->length = 0; return deq; } int isEmpty(deque* deq) { /* 덱이 공백인가를 검사 */ if (deq->length == 0) return 1; else return 0;

덱(9) 이중 연결 리스트를 이용한 Deque 구현(3) public Object deleteFirst() {
if (isEmpty()) return null; DoubleListNode first = head.rlink; Object value = first.data; DoubleListNode second = first.rlink; second.llink = head; head.rlink = second; count--; return value; } public Object deleteLast() { DoubleListNode last = tail.llink; DoubleListNode secondtolast = last.llink; Object value = last.data; secondtolast.rlink = tail; tail.llink = secondtolast;

덱(10) 이중 연결 리스트를 이용한 덱 구현(4) void insertFirst(deque* deq, element item) { /* 연결 덱에 첫 번째 원소를 삽입 */ deqNode* newNode; newNode = (deqNode *)malloc(sizeof(deqNode)); newNode->data = item; if (deq->length == 0) { deq->first = newNode; deq->last = newNode; newNode->rlink = NULL; newNode->llink = NULL; } else { deq->first->llink = newNode; newNode->rlink = deq->first; newNode->llink = NULL; deq->first = newNode; deq->length++; }

덱(11) 이중 연결 리스트를 이용한 덱 구현(5) void insertLast(deque* deq, element item) { /* 연결 덱에 마지막 원소로 삽입 */ deqNode* newNode; newNode = (deqNode * )malloc(sizeof(deqNode)); newNode->data = item; if (deq->length == 0) { /* 덱이 공백인 경우 */ deq->first = newNode; deq->last = newNode; newNode->rlink = NULL; newNode->llink = NULL; } else { deq->last->rlink = newNode; newNode->rlink = NULL; newNode->llink = deq->last; deq->last = newNode; deq->length++; }

덱(12) 이중 연결 리스트를 이용한 덱 구현(6) element deleteFirst(deque* deq) { /* 연결 덱에서 첫 번째 원소를 삭제하고 반환 */ deqNode* temp; element item; if (deq->length==0) { /* 연결 덱이 공백인 경우 */ printf("Deque is empty\n"); exit(1); } else { item = deq->first->data; temp = deq->first; if (deq->first->rlink = NULL) { /* 원소가 1개인 경우 */ deq->first = NULL; deq->last = NULL; } else { /* 원소가 2개 이상인 경우 */ deq->first = deq->first->rlink; deq->first->llink = NULL; deq->length--; free(temp); /* 삭제된 노드를 반환 */ return item; } }

덱(13) 이중 연결 리스트를 이용한 덱 구현(7) element deleteLast(deque* deq) { /* 연결 덱에서 마지막 원소를 삭제하고 반환 */ deqNode* temp; element item; if (deq->length==0) { /* 연결 덱이 공백인 경우 */ printf("Deque is empty\n"); exit(1); } else { item = deq->last->data; temp = deq->last; if (deq->last->llink = NULL) { /* 원소가 1개인 경우 */ deq->first = NULL; deq->last = NULL; } else { /* 원소가 2개 이상인 경우 */ deq->last = deq->last->llink; deq->last->rlink = NULL; deq->length--; free(temp); /* 삭제된 노드를 반환 */ return item; } }

덱(14) 이중 연결 리스트를 이용한 덱 구현(8) void removeFirst(deque* deq) {
/* 연결 덱에서 첫 번째 원소를 삭제 */ deqNode* temp; if (deq->length==0) { /* 연결 덱이 공백인 경우 */ printf("Deque is empty\n"); exit(1); } else { temp = deq->first; if (deq->first->rlink = NULL) { /* 원소가 1개인 경우 */ deq->first = NULL; deq->last = NULL; } else { /* 원소가 2개 이상인 경우 */ deq->first = deq->first->rlink; deq->first->llink = NULL; deq->length--; free(temp); /* 삭제된 노드를 반환 */ }

덱(15) 이중 연결 리스트를 이용한 덱 구현(9) void removeLast(deque* deq) {
/* 연결 덱에서 마지막 원소를 삭제 */ deqNode* temp; if (deq->length==0) { /* 연결 덱이 공백인 경우 */ printf("Deque is empty\n"); exit(1); } else { temp = deq->last; if (deq->last->llink = NULL) { /* 원소가 1개인 경우 */ deq->first = NULL; deq->last = NULL; } else { /* 원소가 2개 이상인 경우 */ deq->last = deq->last->llink; deq->last->rlink = NULL; deq->length--; free(temp); /* 삭제된 노드를 반환 */ } }

덱(16) 이중 연결 리스트를 이용한 덱 구현(10) element peekFirst(deque* deq) {
/* 연결 덱에서 첫 번째 원소를 검색해서 반환 */ if (deq->length==0) { /* 연결 덱이 공백인 경우 */ printf("Deque is empty\n"); exit(1); } else return deq->first->data; } element peekLast(deque* deq) { /* 연결 덱에서 마지막 원소를 검색해서 반환 */ else return deq->last->data; int main() { deque* deq; deq = createDeque(); …

덱(17) 덱을 이용한 스택의 구현(1) 스택의 연산 : 덱의 함수를 호출하는 함수 호출 명령문
deque* createStack() { /* 공백 덱으로 스택을 생성 */ deque* stack; stack = createDeque(); return stack; } int isStackEmpty(deque* stack) { /* 스택이 공백인가를 검사 */ return (isEmpty(stack)); } void push(deque* stack, element item) { /* 스택에 원소 삽입 */ insertLast(stack, item);

덱(18) 덱을 이용한 스택의 구현(2) element peek(deque* stack) { /* 스택의 톱 원소를 검색 */
if (stack->length==0) { /* 스택(연결 덱)이 공백인 경우 */ printf("Stack is empty\n"); exit(1); } else { return peekLast(stack); } element pop(deque* stack) { /* 스택의 톱 원소를 삭제하고 반환 */ return deleteLast(stack);

덱(19) 덱을 이용한 스택의 구현(3) void remove(deque* stack) { /* 스택의 톱 원소를 삭제 */
/* 스택의 톱 원소를 삭제 */ if (stack->length==0) { /* 스택(연결 덱)이 공백인 경우 */ printf("Stack is empty\n"); exit(1); } else { removeLast(stack); }

5장 큐.

Similar presentations

Presentation on theme: "5장 큐."— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

5장 큐.

Similar presentations

Presentation on theme: "5장 큐."— Presentation transcript:

Similar presentations

About project

지원