CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.

Slides:



Advertisements
Similar presentations
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express Slide 1 (of 27)
Advertisements

CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 20).
제14장 동적 메모리.
C 프로그래밍 I.
5장 큐.
Chapter 04. 연결 리스트(Linked List) 2
7장. 큐 스택, 큐 학습목표 리스트 작업은 시간과 무관하게 정의 스택과 큐의 작업은 시간을 기준으로 정의
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
Linked List 학기 SANGJI University.
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
제3장 스택과 큐.
자료 구조: Chapter 3 (2)구조체, 포인터
개정판 누구나 즐기는 C언어 콘서트 제9장 포인터 출처: pixabay.
스택(stack) SANGJI University Kwangman Ko
제 6장. 생성자와 소멸자 학기 프로그래밍언어및실습 (C++).
제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식.
CHAP 4:리스트 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 6:큐.
강의 #6 큐(Queue).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
다음 주 과제 7장 읽어오기 숙제 해서 다음 주(11월 12일) 제출하기. 큐(Queue) E304호,
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
제 5 장. 스택(Stack).
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
Dynamic Memory and Linked List
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
CHAP 6:큐.
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 4:리스트.
CHAP 6:큐.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행
제 4 장 스택과 큐 4.1 스택(stack) 4.2 스택의 활용 4.3 큐 4.4 데큐.
Introduction To Data Structures Using C
자바 5.0 프로그래밍.
자기참조 구조체(1) 먼저 자신과 같은 형의 구조체를 포인트하는 포인터 멤버 필드를 갖는 구조체를 정의한다.
인터넷응용프로그래밍 JavaScript(Intro).
13. 포인터와 배열! 함께 이해하기 IT응용시스템공학과 김 형 진 교수.
8 큐.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
쉽게 풀어쓴 C언어 Express 제14장 포인터 활용 C Express Slide 1 (of 22)
* 프로그램을 간단히 하기 위해 malloc 성공체크는 안 함
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 하 상 호.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
CHAP 21. 전화, SMS, 주소록.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
데이터 동적 할당 Collection class.
알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 하 상 호.
자료구조론 8장 큐(queue).
보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
7주차: Functions and Arrays
C 프로그래밍 I.
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
구조체(struct)와 공용체(union)
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
우선순위 큐 & Heap Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
13. 포인터와 배열! 함께 이해하기.
C++ Espresso 제15장 STL 알고리즘.
6 객체.
제 4 장. 리스트(List).
Presentation transcript:

CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005

큐(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

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

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

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

공백상태, 포화상태 공백상태: front == rear 포화상태: front % M==(rear+1) % M 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다. 3 3 3 4 4 4 C D C D 2 2 2 5 5 5 B E B E F F A A 1 6 1 6 1 6 G G H 7 7 7 rear front rear front 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); // 삽입 함수 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]; 나머지(modulo) 연산을 사용하여 인덱스를 원형으로 회전시킨다.

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

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

덱(deque) 덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 전단(front) 후단(rear) add_front delete_front get_front add_rear delete_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 rear front rear C A B D A ddd_front(dq, A) ddd_rear(dq, D) ddd_rear(dq, B) delete_front(dq) front rear front rear A B C A B delete_rear(dq) ddd_front(dq, C)

덱의 구현 양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중연결 리스트 사용 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; 연결리스트의 연산과 유사 헤드포인터 대신 head와 tail 포인터 사용

덱에서의 삭제연산 // 전단에서의 삭제 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 // 공백상태가 아니면 dq->head->llink=NULL; } return item;

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

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

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

큐의 응용: 시물레이션 시뮬레이션은 하나의 반복 루프 현재시각을 나타내는 clock이라는 변수를 하나 증가 is_customer_arrived 함수를 호출한다. is_customer_arrived 함수는 랜덤 숫자를 생성하여 시뮬레이션 파라미터 변수인 arrival_prov와 비교하여 작으면 새로운 고객이 들어왔다고 판단 고객의 아이디, 도착시간, 서비스 시간 등의 정보를 만들어 구조체에 복사하고 이 구조체를 파라미터로 하여 큐의 삽입 함수 enqueue()를 호출한다. 여기서 고객이 필요로 하는 서비스 시간은 역시 랜덤숫자를 이용하여 생성된다. 지금 서비스하고 있는 고객이 끝났는지를 검사: 만약 service_time이 0이 아니면 어떤 고객이 지금 서비스를 받고 있는 중임을 의미한다. clock이 하나 증가했으므로 service_time을 하나 감소시킨다. 만약 service_time이 0이면 현재 서비스받는 고객이 없다는 것을 의미한다. 따라서 큐에서 고객 구조체를 하나 꺼내어 서비스를 시작한다..

큐의 응용: 시물레이션 // 시뮬레이션 프로그램 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();