슬라이드 1

Similar documents
슬라이드 1

슬라이드 1

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

04장.큐

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

03_queue

Microsoft PowerPoint - ch08_큐 [호환 모드]

슬라이드 1

06장.리스트

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

Chapter 4. LISTS

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

11장 포인터

Algorithms

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

2. QUEUE OPERATIONS Initialize the queue Insert to the rear of the queue (also called as Enqueue) Remove (Delete) from the front of the queue (also ca

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

Microsoft PowerPoint - 제4장-스택과큐.pptx

1장. 리스트

Chapter 4. LISTS

슬라이드 1

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

chap 5: Trees

슬라이드 1

Microsoft PowerPoint - 07-chap05-Stack.ppt

슬라이드 1

untitled

Chap 6: Graphs

슬라이드 1

Chapter 4. LISTS

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

Algorithms

4장

슬라이드 1

중간고사 (자료 구조)

슬라이드 1

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

슬라이드 1

<BCBCB9CCB3AA20C0DAB7E1202D20BDBAC5C3C5A52E687770>

슬라이드 1

슬라이드 1

C 언어 강의노트

슬라이드 1

슬라이드 1

Lab 3. 실습문제 (Single linked list)_해답.hwp

03장.스택.key

Microsoft PowerPoint - 자료구조2008Chap06

슬라이드 1

Microsoft PowerPoint - 06-List.ppt

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

슬라이드 1

chap01_time_complexity.key

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ

5.스택(강의자료).key

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

Microsoft PowerPoint - chap06-2pointer.ppt

슬라이드 1

PowerPoint 프레젠테이션

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센

슬라이드 1

Microsoft PowerPoint - chap4_list

4장

Microsoft PowerPoint - chap11-포인터의활용.pptx

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

Microsoft PowerPoint - ch07 - 포인터 pm0415

02장.배열과 클래스

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

chap x: G입력

Microsoft PowerPoint - 제11장 포인터(강의)

03장.스택

ABC 10장

슬라이드 1

11장 포인터

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

PowerPoint 프레젠테이션

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

untitled

슬라이드 1

01장.자료구조와 알고리즘

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Microsoft PowerPoint - 제11장 포인터

chap x: G입력

슬라이드 1

슬라이드 1

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

08장.트리

PowerPoint 프레젠테이션

KNK_C_05_Pointers_Arrays_structures_summary_v02

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

01_List

Transcription:

CHAP 6: 큐

큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear)

큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임 연산 : create() ::= 큐를생성한다. init(q) ::= 큐를초기화한다. is_empty(q) ::= 큐가비어있는지를검사한다. is_full(q) ::= 큐가가득찼는가를검사한다. enqueue(q, e) ::= 큐의뒤에요소를추가한다. dequeue(q) ::= 큐의앞에있는요소를반환한다음삭제한다. peek(q) ::= 큐에서삭제하지않고앞에있는요소를반환한다.

큐의응용 직접적인응용 시뮬레이션의대기열 ( 공항에서의비행기들, 은행에서의대기열 ) 통신에서의데이터패킷들의모델링에이용 프린터와컴퓨터사이의버퍼링 간접적인응용 스택과마찬가지로프로그래머의도구 많은알고리즘에서사용됨 생산자버퍼소비자 data QUEUE

배열을이용한큐 선형큐 : 배열을선형으로사용하여큐를구현 삽입을계속하기위해서는요소들을이동시켜야함 문제점이많아사용되지않음 [-1] [0] [1] [2] [3] [4] [5] front rear [-1] [0] [1] [2] [3] [4] [5] 원형큐 : 배열을원형으로사용하여큐를구현 front rear [3] [2] [1] [0] [MAX_SIZE-2] [MAX_SIZE-1]

큐의구조 큐의전단과후단을관리하기위한 2 개의변수필요 front: 첫번째요소하나앞의인덱스 rear: 마지막요소의인덱스 rear 2 1 B A 3 4 5 6 0 7 front

3 4 3 4 2 5 2 5 1 6 1 A 6 0 7 rear 0 7 front rear front (a) 초기상태 (b) A 삽입 rear 3 4 rear 3 4 2 B 5 2 B 5 1 A 6 1 6 0 7 front 0 7 front (c) B 삽입 (d) A 삭제

공백상태, 포화상태 공백상태 : front == rear 포화상태 : front % M==(rear+1) % M 공백상태와포화상태를구별하기위하여하나의공간은항상비워둔다. 3 4 3 4 3 4 2 5 2 B C D E 5 2 B C D E 5 1 6 1 A G F 6 1 A H G F 6 0 7 0 7 0 7 front rear front rear front rear (a) 공백상태 (b) 포화상태 (c) 오류상태

큐의연산 나머지 (modulo) 연산을사용하여인덱스를원형으로회전시킨다. // 공백상태검출함수 int is_empty(queuetype *q) { return (q->front == q->rear); // 포화상태검출함수 int is_full(queuetype *q) { return ((q->rear+1)%max_queue_size == q->front);

큐의연산 나머지 (modulo) 연산을사용하여인덱스를원형으로회전시킨다. // 삽입함수 void enqueue(queuetype *q, element item) { if( is_full(q) ) error(" 큐가포화상태입니다 "); q->rear = (q->rear+1) % MAX_QUEUE_SIZE; q->queue[q->rear] = item; // 삭제함수 element dequeue(queuetype *q) { if( is_empty(q) ) error(" 큐가공백상태입니다 "); q->front = (q->front+1) % MAX_QUEUE_SIZE; return q->queue[q->front];

연결된큐 연결된큐 (linked queue): 연결리스트로구현된큐 front 포인터는삭제와관련되며 rear 포인터는삽입 front 는연결리스트의맨앞에있는요소를가리키며, rear 포인터는맨뒤에있는요소를가리킨다 큐에요소가없는경우에는 front 와 rear 는 NULL front rear A B NULL C D NULL

연결된큐에서의삽입과삭제 front rear temp A B C D NULL 삽입 front rear A B C D NULL front rear 삭제 A B C D NULL temp front rear A B C D NULL

연결된큐에서의삽입

연결된큐에서의삭제

덱 (deque) 덱 (deque) 은 double-ended queue 의줄임말로서큐의전단 (front) 과후단 (rear) 에서모두삽입과삭제가가능한큐 add_front add_rear delete_front delete_rear get_front 전단 (front) 후단 (rear) get_rear

덱 ADT 객체 : n 개의 element 형으로구성된요소들의순서있는모임 연산 : create() ::= 덱을생성한다. init(dq) ::= 덱을초기화한다. is_empty(dq) ::= 덱이공백상태인지를검사한다. is_full(dq) ::= 덱이포화상태인지를검사한다. add_front(dq, e) ::= 덱의앞에요소를추가한다. add_rear(dq, e) ::= 덱의뒤에요소를추가한다. delete_front(dq) ::= 덱의앞에있는요소를반환한다음삭제한다 delete_rear(dq) ::= 덱의뒤에있는요소를반환한다음삭제한다. get_front(q) ::= 덱의앞에서삭제하지않고앞에있는요소를반환한다. get_rear(q) ::= 덱의뒤에서삭제하지않고뒤에있는요소를반환한다.

덱의연산 front A rear front C A B D rear add_front(dq, A) add_rear(dq, D) front rear front rear A B A B D add_rear(dq, B) delete_front(dq) front C A B rear front A B rear add_front(dq, C) delete_rear(dq)

덱의구현 양쪽에서삽입, 삭제가가능하여야하므로일반적으로 이중연결리스트사용 typedef int element; // 요소의타입 typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; // 노드의타입 typedef struct DequeType { DlistNode *head; DlistNode *tail; DequeType; // 덱의타입

덱에서의삽입연산 연결리스트의연산과유사 헤드포인터대신 head 와 tail 포인터사용

덱에서의삽입연산

덱에서의삽입연산 void add_rear(dequetype *dq, element item) { DlistNode *new_node = create_node(dq->tail, item, NULL); if( is_empty(dq)) dq->head = new_node; else dq->tail->rlink = new_node; dq->tail = new_node;

덱에서의삽입연산 // void add_front(dequetype *dq, element item) { DlistNode *new_node = create_node(null, item, dq->head); if( is_empty(dq)) dq->tail = new_node; else dq->head->llink = new_node; dq->head = new_node;

덱에서의삭제연산

덱에서의삭제연산 // 전단에서의삭제 element delete_front(dequetype *dq) { element item; DlistNode *removed_node; if (is_empty(dq)) error(" 공백덱에서삭제 "); else { removed_node = dq->head; // 삭제할노드 item = removed_node->data; // 데이터추출 dq->head = dq->head->rlink; // 헤드포인터변경 free(removed_node); // 메모리공간반납 if (dq->head == NULL) // 공백상태이면 dq->tail = NULL; else return item; // 공백상태가아니면 dq->head->llink=null;

덱에서의삭제연산

큐의응용 : 버퍼 큐는서로다른속도로실행되는두프로세스간의상호작용을조화시키는버퍼역할을담당 CPU 와프린터사이의프린팅버퍼, 또는 CPU 와키보드사이의키보드버퍼 대개데이터를생산하는생산자프로세스가있고데이터를소비하는소비자프로세스가있으며이사이에큐로구성되는버퍼가존재

QueueType buffer; /* 생산자프로세스 */ producer() { while(1){ 데이터생산 ; while( lock(buffer)!= SUCCESS ) ; if(!is_full(buffer) ){ enqueue(buffer, 데이터 ); unlock(buffer); /* 생산자프로세스 */ consumer() { while(1){ while( lock(buffer)!= SUCCESS ) ; if(!is_empty(buffer) ){ 데이터 = dequeue(buffer); 데이터소비 ; unlock(buffer);

큐의응용 : 시뮬레이션 큐잉이론에따라시스템의특성을시뮬레이션하여분석하는데이용 큐잉모델은고객에대한서비스를수행하는서버와서비스를받는고객들로이루어진다 은행에서고객이들어와서서비스를받고나가는과정을시뮬레이션 고객들이기다리는평균시간을계산

큐의응용 : 시물레이션 시뮬레이션은하나의반복루프 현재시각을나타내는 clock 이라는변수를하나증가 is_customer_arrived 함수를호출한다. is_customer_arrived 함수는랜덤숫자를생성하여시뮬레이션파라미터변수인 arrival_prov 와비교하여작으면새로운고객이들어왔다고판단 고객의아이디, 도착시간, 서비스시간등의정보를만들어구조체에복사하고이구조체를파라미터로하여큐의삽입함수 enqueue() 를호출한다.

큐의응용 : 시물레이션 고객이필요로하는서비스시간은역시랜덤숫자를이용하여생성된다. 지금서비스하고있는고객이끝났는지를검사 : 만약 service_time 이 0 이 아니면어떤고객이지금서비스를받고있는중임을의미한다. clock 이하나증가했으므로 service_time 을하나감소시킨다. 만약 service_time 이 0 이면현재서비스받는고객이없다는것을의미한다. 따라서큐에서고객구조체를하나꺼내어서비스를시작한다..

시뮬레이션프로그램 typedef struct { int id; int arrival_time; int service_time; element; typedef struct { element queue[max_queue_size]; int front, rear; QueueType; QueueType queue;

시뮬레이션프로그램 // 0 에서 1 사이의실수난수생성함수 double random() { return rand()/(double)rand_max; // 시뮬레이션에필요한여러가지상태변수 int duration=10; // 시물레이션시간 double arrival_prob=0.7; // 하나의시간단위에도착하는평균고객의수 int max_serv_time=5; // 하나의고객에대한최대서비스시간 int clock; // 시뮬레이션의결과 int customers; // 전체고객수 int served_customers; // 서비스받은고객수 int waited_time; // 고객들이기다린시간

시뮬레이션프로그램 // 랜덤숫자를생성하여고객이도착했는지도착하지않았는지를판단 int is_customer_arrived() { if( random() < arrival_prob ) return TRUE; else return FALSE; // 새로도착한고객을큐에삽입 void insert_customer(int arrival_time) { element customer; customer.id = customers++; customer.arrival_time = arrival_time; customer.service_time=(int)(max_serv_time*random()) + 1; enqueue(&queue, customer); printf(" 고객 %d 이 %d 분에들어옵니다. 서비스시간은 %d 분입니다.", customer.id, customer.arrival_time, customer.service_time);

시뮬레이션프로그램 // 큐에서기다리는고객을꺼내어고객의서비스시간을반환한다. int remove_customer() { element customer; int service_time=0; if (is_empty(&queue)) return 0; customer = dequeue(&queue); service_time = customer.service_time-1; served_customers++; waited_time += clock - customer.arrival_time; printf(" 고객 %d 이 %d 분에서비스를시작합니다. 대기시간은 %d 분이었습니다.", customer.id, clock, clock - customer.arrival_time); return service_time;

시뮬레이션프로그램 // 통계치를출력한다. void print_stat() { printf(" 서비스받은고객수 = %d", served_customers); printf(" 전체대기시간 = %d 분 ", waited_time); printf("1 인당평군대기시간 = %f 분 ", (double)waited_time/served_customers); printf(" 아직대기중인고객수 = %d", customers-served_customers);

큐의응용 : 시물레이션 // 시뮬레이션프로그램 void main() { int service_time=0; clock=0; while(clock < duration){ clock++; printf(" 현재시각 =%d\n",clock); if (is_customer_arrived()) { insert_customer(clock); if (service_time > 0) service_time--; else { service_time = remove_customer(); print_stat();