PowerPoint 프레젠테이션

Transcription

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

2 큐 큐 = 대기열 2

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

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

5 추상자료형큐 액시엄 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

6 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

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

8 원형연결리스트큐의삽입 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; 새노드의데이터필드를채우고 자기자신을가리키게 새노드를마지막노드로 8

9 원형연결리스트큐의삭제 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"; 첫노드이자마지막노드의공간반납 빈큐에삭제명령은오류로처리 9

10 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

11 스택, 큐 배열에의한스택 / 큐배열비교 스택은탑변수큐는프런트, 리어변수 11

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

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

14 삽입 원형배열 삽입인덱스 : (Rear + 1) % MAX 14

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

16 원형배열큐함수 코드 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

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

18 회문 큐응용예 앞에서읽으나뒤에서읽으나동일한단어, 문자열토마토, 기러기 코드 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

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

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

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

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

23 너비우선탐색을위한큐 큐응용예 시작노드를삽입삭제와동시에인접노드를삽입소모적탐식한번간노드는다시안감 23

24 코드 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

25 큐응용예 덱 (DEQUE: Double Ended Queue) 키보드입력버퍼, 화면스크롤양쪽에서삽입, 삭제의필요성이존재 25

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

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

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