PowerPoint 프레젠테이션

Similar documents
PowerPoint 프레젠테이션

슬라이드 1

Chapter 4. LISTS

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt

슬라이드 1

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

슬라이드 1

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

03_queue

04장.큐

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

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

chap 5: Trees

Microsoft PowerPoint - ch08_큐 [호환 모드]

PowerPoint 프레젠테이션

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

untitled

06장.리스트

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

슬라이드 1

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

11장 포인터

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

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

1장. 리스트

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

Chap 6: Graphs

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

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

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

Chapter 4. LISTS

Chapter 4. LISTS

Algorithms

C 언어 강의노트

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

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 - 자료구조2008Chap06

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

Algorithms

슬라이드 1

PowerPoint 프레젠테이션

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

03장.스택.key

Microsoft PowerPoint - 07-chap05-Stack.ppt

chap01_time_complexity.key

슬라이드 1

Microsoft PowerPoint - 06-List.ppt

슬라이드 1

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

슬라이드 1

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

슬라이드 1

4장

chap x: G입력

(Microsoft Word - \301\337\260\243\260\355\273\347.docx)

<BCBCB9CCB3AA20C0DAB7E1202D20BDBAC5C3C5A52E687770>

Microsoft PowerPoint - 제10장-그래프.pptx

슬라이드 1

Microsoft PowerPoint - logo_3.ppt [호환 모드]

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

chap 5: Trees

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

슬라이드 1

슬라이드 1

슬라이드 1

01_List

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

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

슬라이드 1

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

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

2002년 2학기 자료구조

Microsoft PowerPoint - ch07 - 포인터 pm0415

ABC 10장

Microsoft PowerPoint - chap13-입출력라이브러리.pptx

02장.배열과 클래스

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

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

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

슬라이드 1

Microsoft PowerPoint - ch07_스택 [호환 모드]

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

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

08장.트리

K&R2 Reference Manual 번역본

슬라이드 1

Microsoft PowerPoint - chap4_list

05_tree

PowerPoint Presentation

제 3 장 스택과 큐

10주차.key

설계란 무엇인가?

1. auto_ptr 다음프로그램의문제점은무엇인가? void func(void) int *p = new int; cout << " 양수입력 : "; cin >> *p; if (*p <= 0) cout << " 양수를입력해야합니다 " << endl; return; 동적할

Transcription:

스택, 큐 7 장. 큐 리스트작업은시간과무관하게정의스택과큐의작업은시간을기준으로정의큐는가장먼저삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형큐의기본개념을스택과대조하여이해한다. 추상자료형큐를구현하기위한세가지방법을이해한다. 원형배열이필요한이유와동작원리를이해한다. 큐의응용예를구체적으로명확하게이해한다. 1

Section 01 큐개념 - 큐 큐 = 대기열 [ 그림 7-1] 대기열 2

큐 대기열을모델링 용어 선입선출, FIFO, FCFS 줄의맨앞을큐프런트 (Queue Front) 맨뒤를큐리어 (Queue Rear) 큐리어에데이터를삽입하는작업 = 큐애드 (Add) 큐프런트의데이터를삭제하는작업 = 큐리무브 (Remove) 삽입 삭제 검색 ADT 리스트 Insert Delete Retrieve ADT 스택 Push Pop GetTop(PeekTop) ADT 큐 Add(Enqueue) Remove(Dequeue) GetFront(PeekFront) [ 표 7-1] 추상자료형별용어차이 3

Section 02 추상자료형큐 - 추상자료형큐작업 Create: 새로운큐를만들기 Destroy: 사용되던큐를파기하기 Add: 현재의리어바로뒤에새로운데이터를삽입하기 Remove: 프런트에있는데이터를가져오기 GetFront: 현재큐프런트에있는데이터를검색하기 ( 읽기 ) IsEmpty: 현재큐가비어있는지확인하기 IsFull: 현재큐가꽉차있는지확인하기 GetSize: 현재큐에들어가있는데이터개수를알려주기 4

추상자료형큐액시엄 GetFront(Add(Create(Q), V)) = V GetFront(Add(Add(Q, W), V)) = GetFront(Add(Q, W)) IsEmpty(Create(Q)) = TRUE Remove((Create(Q)) = ERROR GetFront(Create(Q)) = ERROR 5

Section 03 C++ 연결리스트에의한큐구현 - C++ 연결리스트에의한큐 코드 7-1: QueueP.h (C++ Interface by Linked List) typedef struct { int Data; 큐데이터를정수형으로가정 node* Next; 다음노드를가리키는포인터변수 node; 노드는구조체타입 typedef node* Nptr; Nptr 타입이가리키는것은노드타입 const int MAX = 100; class queueclass { public: queueclass( ); 생성자함수 queueclass(const queueclass& Q); 복사생성자함수 ~queueclass( ); 소멸자함수 void Add(int Item); Item 값을큐에삽입 void Remove( ); 큐프런트를삭제, 리턴값없음 boolean IsEmpty( ); 비어있는지확인 boolean IsFull( ); 꽉차있는지확인 private: Nptr Rear; 마지막노드를가리키는포인터 6

큐의삽입삭제 양쪽끝에서일어남 ( 삽입은리어에, 삭제는프런트에서 ) 연결리스트의첫노드를프런트로, 마지막을리어로간주스택은삽입삭제모두한쪽끝에서일어남 리어포인터하나로구현한큐 C++ 연결리스트에의한큐 원형연결리스트첫요소는 Rear->Next 에의해접근가능프런트포인터하나로만구현하면삽입을위해끝까지순회해야함 [ 그림 7-2] 원형연결리스트에의한큐 7

원형연결리스트큐의삽입 void queueclass::add(int Item) { if (! IsEmpty( )) 현재하나이상의노드가있다면 { Nptr p = new node; 포인터 p가공간의새노드의시작주소를가리키게 p->data = Item; 새노드의데이터필드를채우고 p->next = Rear->Next; 이노드가결국마지막노드가될것이니이노드가현재의프런트노드를가리키게 Rear->Next = p; 현재의마지막노드가새노드를가리키게 Rear = p; 새노드를마지막노드로 else 현재비어있는큐이라면 { p = new node; 포인터 p가공간의새노드의시작주소를가리키게 p->data = Item; 새노드의데이터필드를채우고 p->next = p; 자기자신을가리키게 Rear = p; 새노드를마지막노드로 [ 그림 7-3] 원형연결리스트큐의삽입 [ 그림 7-4] 큐 8

원형연결리스트큐의삭제 void queueclass::remove( ) { Nptr Front = Rear->Next; 편의상프런트포인터를별도로생성 if (GetSize( ) >= 2) 노드두개이상일때 { Rear->Next = Front->Next; 마지막노드가두번째노드를가리키게 delete Front; 첫노드가사용하던공간을반납 else if (GetSize( ) = = 1) 노드하나일때 { Rear = NULL; 삭제하면빈큐가되므로빈큐를표시 delete Front; 첫노드이자마지막노드의공간반납 else if (GetSize( ) = = 0) 빈큐에삭제명령은오류로처리 { cout << "Deletion on Empty Queue"; [ 그림 7-5] 원형연결리스트큐의삭제 9

Section 04 C++ 배열에의한큐구현 - C++ 배열에의한큐코드 7-4: QueueA.h (C++ Interface by Array) const int MAX = 100; class queueclass { public: queueclass( ); 생성자함수 queueclass(const queueclass& Q); 복사생성자함수 ~queueclass( ); 소멸자함수 void Add(int Item); Item 값을큐에삽입 void Remove( ); 큐프런트를삭제, 리턴값없음 boolean IsEmpty( ); 비어있는지확인 boolean IsFull( ); 꽉차있는지확인 private: int Front, Rear; 프런트, 리어인덱스를추적 int Count; 원형연결배열에사용 int Queue[MAX]; 큐데이터는정수형, 최대 100개 10

배열에의한스택 / 큐배열비교스택, 큐 스택은탑변수큐는프런트, 리어변수 [ 그림 7-6] 스택과큐의비교 11

배열에의한큐삽입, 삭제 Front 0, Rear -1로초기화삽입이면 Rear++ 한후에삽입삭제이면 Front++ 큐의상태판단 Front > Rear 이면빈큐 Front == Rear 이면큐아이템하나 12

배열에의한큐의표류표류 연속된삽입, 삭제에의한오른쪽이동왼쪽빈공간이있음에도오른쪽에서막힘대책 : 왼쪽쉬프트 삭제될때마다 오른쪽끝에막힐때몰아서한번에 [ 그림 7-7] 표류현상 13

삽입 삽입인덱스 : (Rear + 1) % MAX 원형배열 [ 그림 7-8] 원형배열 14

빈큐와꽉찬큐판정불가 인덱스로봐서는둘다동일조건 Front = Rear + 1 별도의 Count 변수유지 삽입시 Count ++ 삭제시 Count - - 원형배열 [ 그림 7-9] 빈큐와꽉찬큐 15

코드 7-5: 원형배열큐의초기화, 삽입, 삭제 queueclass::queueclass( ) 생성자함수 { Front = 0; Rear = -1; Count = 0; 데이터개수 0 void queueclass::add(int Item) { if (Count <= Max) 아직데이터수가최대가아니라면 { Rear = (Rear + 1) % MAX; 리어인덱스증가 ( 원형으로 ) Queue[Rear] = Item; 큐배열에데이터복사 Count++; 데이터수증가 void queueclass::remove( ) { if (Count > 0) 데이터가하나라도있다면 { Front = (Front + 1) % MAX; 프런트인덱스증가 ( 원형으로 ) Count--; 원형배열큐함수 데이터수감소 16

Section 05 추상자료형리스트에의한큐구현 - 추상자료형리스트에의한큐 코드 7-6: QueueL.h (C++ Interface by ADT LIST) #include <ListP.h> class queueclass { public: private: listclass L; ; void queueclass::add(int Item) { L.Insert(L.Length( ) + 1, Item); void queueclass::remove( ) {L.Delete(1); 코드 6-7( 또는코드 6-5) 과동일 삽입함수 삭제함수 int queueclass::getfront(int& FrontItem) 검색함수 { L.Retrieve(1, FrontItem) ; 17

Section 06 큐응용예 - 큐응용예 회문앞에서읽으나뒤에서읽으나동일한단어, 문자열토마토, 기러기 코드 7-7: 회문판정 Q.Create( ); S.Create( ); 큐와스택을생성 for (i = 0; i < stringlength( ); i++) 문자열끝까지 { Read Character into C; 하나씩읽어서변수 C에저장 Q.Add(C); S.Push(C); 큐에삽입, 스택에삽입 Matched = TRUE: 매칭된것으로초기화 while (!IsEmpty( ) && Matched) 비어있지않고, 미스매치되지않는동안 { if (Q.GetFront( ) = = S.GetTop( )) 큐프런트와스택탑이일치하면 { Q.Remove( ); S.Pop( ); 각각삭제 else Matched = FALSE; 일치하지않으면빠져나감 return MatchedSoFar; 비어서빠져나오면트루를리턴 18

큐응용예시뮬레이션 모의실험, 큐잉이론이벤트발생시기 : 시간구동시뮬레이션, 사건구동시뮬레이션 대기시간 (A, 20, 5) (B, 22, 4) (C, 23, 2) (D, 30, 3) 의순서로일이발생 Event CustomerQueue Arrival Start End 20 A A: 20 20 25 22 B 23 B C 25 C B: 22 25 29 29 C: 23 29 31 30 D 31 D: 30 31 34 34 [ 표 7-2] (A, 20, 5) (B, 22, 4) (C, 23, 2) (D, 30, 3) 의처리 19

큐응용예 메저와트리거그래픽입력모드 리퀘스트모드 프로그램이요구하는입력장비로부터입력 프로그램실행중에메져값을요구샘플모드 프로그램이요구하는입력장비로부터입력 현재의메져값을가져다실행이벤트모드 사용자가선택한임력장비가우선권을가짐 이벤트큐와콜백함수 20

큐응용예시공유시스템의일괄처리작업 사용자 ID 별로우선순위를분류 queuetype MultiQueue[MaxPriority]; 이면우선순위별로 MultiQueue[0], MultiQueue[1], MultiQueue[2] 를형성배치잡이제출되면, 운영체제중디스패처 (Dispatcher) 는사용자 ID 를기준으로해당큐에삽입먼저실행중이던잡이끝나면, 운영체제중스케줄러 (Job Scheduler) 는사용자 ID 를기준으로해당큐에서삭제 21

Section 07 너비우선탐색 - 너비우선탐색 너비우선탐색 (BFS: Breadth First Search) 깊이보다는폭을취함 A-B-G-C-E-H-D-F A 에서거리 1 인노드, 다시각각으로부터거리 1 인노드,. [ 그림 7-10] 너비우선탐색 22

너비우선탐색을위한큐 시작노드를삽입삭제와동시에인접노드를삽입소모적탐식한번간노드는다시안감 너비우선탐색 [ 그림 7-11] 너비우선탐색과큐 23

너비우선탐색 코드 7-8: 너비우선탐색 BreadthFirstSearch(Origin) { Q.Create( ); 새로운큐를만들기 Q.Add(Origin); 출발지를큐에삽입 Mark Origin as Visited; 출발지를가본것으로표시 while (!Q.IsEmpty( )) 빈큐가아닐동안 { Q.GetFront(Front); 큐프런트에있는노드를 Front로복사 Q.Remove( ); 큐프런트를제거 for (Each Unvisited Nodes C Adjacent to Front) { Q.Add(C); 큐에삽입 Mark C as Visited; 가본것으로표시 24

Section 08 덱 - 덱덱 (DEQUE: Double Ended Queue) 키보드입력버퍼, 화면스크롤양쪽에서삽입, 삭제의필요성이존재 [ 그림 7-12] 키보드입력 [ 그림 7-13] 화면스크롤 25

덱덱 (DEQUE: Double Ended Queue) AddLast( ), AddFirst( ), RemoveLast( ), RemoveFirst( ) 큐 : RemoveFirst( ), AddLast( ) 만을사용스택 : RemoveLast( ), AddLast( ) 만을사용덱이일반클래스 (General Class) 라면큐나스택은특수클래스 (Special Class, Adaptor Class) 26

덱원형배열덱 양쪽에서삽입삭제 : 두개의포인터를유지하는것이유리고정된한쪽끝에서 Add나 Remove가일어나면쉬프트필요프런트삭제시에 Front ++; 에의해프런트가전진프런트삽입시에 Front - -; 에의해프런트가후진 [ 그림 7-14] 원형배열덱 27

Josephus 의문제 덱 유대인 41 명이로마군에쫓겨동굴에갇혔다. 잡혀죽기를원치않던이사람들은 [ 그림 7-15] 와같이둥글게둘러앉아아무도남은사람이없을때까지다음세번째사람 (Every 3rd Person) 을죽이기로했다. Josephus 는이러한죽음을원치않았다. 생존자두사람중하나가되기위해서는몇번째에서야하는가 [ 그림 7-15] 요세푸스의문제 28

Thank you 29