Internet Computing Laboratory @ KUT Youn-Hee Han 7장. 큐 Internet Computing Laboratory @ KUT Youn-Hee Han

1. 큐 개념 Queue (큐) Waiting Line (대기열) 가장 먼저 넣은 것이 가장 먼저 빠져 나오는 특성 FIFO (First-In First-Out), FCFS (First-Come First-Served) 스택에 비해서 큐가 더 공정하다… (?) Data Structure

1. 큐 개념 Definition of Queue 중요 용어 A queue is an ordered group of homogeneous items (elements), in which new elements are added at one end (the rear), and elements are removed from the other end (the front). 중요 용어 줄의 맨 앞 - 큐 프런트 (Queue Front) 줄의 맨 뒤 - 큐 리어(Queue Rear) Queue Rear에 데이터를 삽입하는 작업 - Add Queue Front에서 데이터를 삭제하는 작업 - Remove   삽입 삭제 검색 ADT 리스트 Insert Delete Retrieve ADT 스택 Push Pop GetTop (PeekTop) ADT 큐 Add (Enqueue) Remove (Dequeue) GetFront (PeekFront) Data Structure

2. 추상 자료형 큐 주요작업 Axiom Create: 새로운 큐를 만들기 Destroy: 사용되던 큐를 파기하기 Add: 현재의 Rear 바로 뒤에 새로운 데이터를 삽입하기 Remove: Front에 있는 데이터를 없에기 Remove1 – 데이터를 단순 삭제 리턴 없음 Remove2 – 데이터로 리턴하고 삭제도 함 GetFront: 현재 큐 Front에 있는 데이터를 검색하기(읽기) IsEmpty: 현재 큐가 비어있는지 확인하기 IsFull: 현재 큐가 꽉 차 있는지 확인하기 GetSize: 현재 큐에 들어가 있는 데이터 개수를 알려주기 Axiom 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 Data Structure

3. C++ 연결 리스트에 의한 큐 구현 Queue의 삽입/삭제 연산 구현 [Basic Version] 양쪽 끝에서 일어남 삽입은 Rear에서, 삭제는 Front에서 연결 리스트의 첫 노드를 Front로, 마지막을 Rear로 간주 queueClass() Private Data: Front Rear 12 15 88 ~queueClass() Add(int Item) Remove() . Data Structure

3. C++ 연결 리스트에 의한 큐 구현 포인터 하나로 구현한 큐 Front 포인터 한 개로 구현 vs. Rear 포인터 한 개로 구현? Front 포인터 하나로만 구현하면 삽입을 위해 끝까지 순회해야 함. 원형 연결 리스트 (Circular Singly-linked List) with Rear 포인터 마지막요소는 Rear 로 접근 첫요소는 Rear->Next 로 접근 Data Structure

3. C++ 연결 리스트에 의한 큐 구현 C++ 연결리스트에 의한 큐 QueueP.h 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( );                  큐 프런트를 삭제, 리턴 값 없음         bool IsEmpty( );             비어 있는지 확인         bool IsFull( );                꽉 차 있는지 확인 (필요 없음) private:         Nptr Rear;                      마지막 노드를 가리키는 포인터    } Data Structure

3. C++ 연결 리스트에 의한 큐 구현 C++ 연결리스트에 의한 큐 – 삽입 QueueP.c void queueClass::Add(int Item) { if (!IsEmpty()) {               현재 하나 이상의 노드가 있다면 1 Nptr p = new node; 포인터 p가 공간의 새 노드의 시작주소를 가리키게 1     p->Data = Item;      새 노드의 데이터 필드를 채우고 2      p->Next = Rear->Next;   이 노드가 결국 마지막 노드가 될 것이니                                 이 노드가 현재의 프런트 노드를 가리키게 3      Rear->Next = p;          현재의 마지막 노드가 새 노드를 가리키게 4      Rear = p;                  새 노드를 마지막 노드로   } else {                            현재 비어있는 큐 이라면 Nptr p = new node; 포인터 p가 공간의 새 노드의 시작주소를 가리키게       p->Data = Item;     새 노드의 데이터 필드를 채우고       p->Next = p;             자기 자신을 가리키게 (Self-Pointing Node)       Rear = p;                  새 노드를 마지막 노드로 } Data Structure

3. C++ 연결 리스트에 의한 큐 구현 C++ 연결리스트에 의한 큐 – 삭제 QueueP.c void queueClass::Remove() { 1 Nptr Front = Rear->Next;    프런트 포인터를 별도로 생성 if (GetSize( ) >= 2) {              노드 두 개 이상일 때 2 Rear->Next = Front->Next;  마지막 노드가 두 번째 노드를 가리키게 3 delete Front;               첫 노드가 사용하던 공간을 반납 } else if (GetSize( ) = = 1) {         노드 하나일 때 Rear = NULL;          삭제하면 빈 큐가 되므로 빈 큐를 표시 delete Front;               첫 노드이자 마지막 노드의 공간 반납   } else if (GetSize( ) = = 0) {         빈 큐에 삭제명령은 오류로 처리 cout << "Deletion on Empty Queue";  } Front Data Structure

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

4. C++ 배열에 의한 큐 구현 C++ 배열에 의한 큐와 스택 간의 비교 스택에서 포인터 유지 – Top 큐에서 포인터 유지 – Front, Rear 위 그림에서 처음에 Top은 0으로 초기화 되었나 -1로 초기화 되었나 ? 큐에서 삽입은 배열의 오른쪽 끝 (Rear)에서, 삭제는 배열의 왼쪽 끝 (Front)에서 일어남 Front는 일반적으로 초기값이 0 위 그림에서 Rear의 초기값은 0인가 -1인가? Data Structure

4. C++ 배열에 의한 큐 구현 C++ 배열에 의한 큐의 연산 삽입 삭제 큐의 상태 판단 Front는 변화 없음 Rear++ 를 행한 후 해당 인덱스에 삽입 삭제 Rear는 변화 없음 단순하게 Front++ 큐의 상태 판단 If (Front > Rear) 비어있는 큐에 대한 판단 if (Front == Rear) 데이터가 하나가 있는지에 대한 판단 Data Structure

두 방법 모두 데이터 이동에 따른 시간 부담이 크다. 4. C++ 배열에 의한 큐 구현 C++ 배열에 의한 큐의 연산 Drift (표류) 현상 - Rightward Shift 연속된 삽입, 삭제에 의하여 큐의 내용이 오른쪽으로 이동하는 현상 문제점 왼쪽에 버려진 공간이 늘어남 왼쪽에 빈 공간이 있음에도 오른쪽에서 막힘 대책: 왼쪽 쉬프트 (Shift Left) 방법 1 - 삭제될 때마다 방법 2 - 오른쪽 끝에 막힐 때 몰아서 한번에 사이즈가 8인 배열 (MAX=8) 두 방법 모두 데이터 이동에 따른 시간 부담이 크다. Data Structure

데이터는 Front에서 Rear로 시계방향으로 저장되어 있음 4. C++ 배열에 의한 큐 구현 원형 배열 (Circular Array) 왼쪽 쉬프트 없이도 표류 현상을 해결하고자 고안됨 원형 연결 리스트와 같은 Concept 배열 인덱스 7에서 1을 증가시킨 인덱스가 8이 아니라 0으로 함 배열의 물리적인 모습은 그대로 Linear 하지만, 개념적으로 원형으로 만들어 주는 방법 원형 배열에서 삽입/삭제을 위한 인덱스를 구하는 연산  Modulo 연산 Rear 데이터는 Front에서 Rear로 시계방향으로 저장되어 있음 Front Rear = (Rear + 1) % MAX Front = (Front + 1) % MAX Data Structure

4. C++ 배열에 의한 큐 구현 원형 배열 (Circular Array)에서 주의해야 할 사항 빈 큐와 꽉찬 큐 판정불가 인덱스로 봐서는 둘 다 동일 조건 Front == Rear + 1 1 2 3 4 5 6 7 4 55 10 33 40 60 15 22 35 Front Rear 방금전 삭제 시킨 인덱스 다음을 가리킴 삭제 5번 삽입 3번 삽입전 증가시킨 후 삽입 1 2 3 4 5 6 7 1 2 3 4 5 6 7 4 55 10 33 40 60 15 22 35 4 55 10 33 40 60 15 22 35 Front Rear Front Rear 5 4 1 6 4 2 1 2 3 4 5 6 7 7 4 3 55 32 2 66 60 15 22 35 1 2 3 4 5 6 7 1 55 10 33 40 60 15 22 35 Data Structure

4. C++ 배열에 의한 큐 구현 원형 배열 (Circular Array)에서 주의해야 할 사항 빈 큐와 꽉찬 큐 판정방법 별도의 Count 변수 유지 삽입시 Count ++ 삭제시 Count - - Count = 1 Count = 0 Count = 7 Count = 8 = MAX 삭제시 Front는 방금전 삭제 시킨 인덱스 다음을 가리킴 데이터는 Front에서 Rear로 시계방향으로 저장되어 있음 삽입시에는 먼저 Rear 증가시킨 후 삽입 Data Structure

4. C++ 배열에 의한 큐 구현 원형 배열 (Circular Array) 큐의 초기화, 삽입, 삭제 queueClass::queueClass( ) {  생성자 함수 Front = 0;                    Rear = -1;    Count = 0;                            데이터 개수 0 } void queueClass::Add(int Item) {  if (Count <= Max) {                     아직 데이터 수가 최대가 아니라면 Rear = (Rear + 1) % MAX;     Rear 인덱스 증가(원형으로)           Queue[Rear] = Item;            큐 배열에 데이터 복사 Count++;                       데이터 수 증가 }                     void queueClass::Remove( ) { if (Count > 0) {                          데이터가 하나라도 있다면 Front = (Front + 1) % MAX;   프런트 인덱스 증가(원형으로) Count--;                          데이터 수 감소   }                        Data Structure

5. 추상자료형 리스트에 의한 큐 구현 추상자료형 리스트에 의한 큐 구현 #include <ListP.h> class queueClass { public:         코드 7-1(또는 코드 7-4)과 동일 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) ; Data Structure

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

6. 큐 응용 예 너비우선탐색 (BFS: Breadth First Search) 탐색 순서에 있어서 깊이보다는 폭을 우선적으로 취한다. A가 Origin 탐색 방법 (소목적 탐색) 1) A에서 거리가 1인 모든 노드를 방문 2) 다음 거기에서 부터 거리가 1인 모든 노드, 즉 A에서 거리가 2인 모든 노드들… 3) 위와 같은 방법 반복 F까지의 경로가 있는가? A-B-G-C-E-H-D-F Data Structure

6. 큐 응용 예 너비우선 탐색을 위한 큐 시작 노드를 삽입 삭제와 동시에 인접 노드를 삽입 한번 간 노드는 다시 안 감 큐에서 제거된 노드를 순차적으로 나열하면 그것이 너비우선 탐색 순서가 됨 Data Structure

6. 큐 응용 예 너비우선 탐색의 Pseudo-code 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;  가 본 것으로 표시         }      } } Data Structure

6. 큐 응용 예 DFS vs. BFS Data Structure

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

6. 큐 응용 예 데크 (Deque: Double Ended Queue) 특수한 형태의 큐로서 삽입 삭제가 Front와 Rear에서 가해질 수 있도록 허용한 자료구조 스택과 큐의 성질을 종합한 순서 리스트 연산 AddLast( ) AddFirst( ) RemoveLast( ) RemoveFirst( ) 큐: RemoveFirst( ), AddLast( ) 만을 사용 스택: RemoveLast( ), AddLast( )만을 사용 Data Structure

6. 큐 응용 예 원형배열 덱 양쪽에서 삽입 삭제: 두 개의 포인터를 유지하는 것이 유리 고정된 한 쪽 끝에서 Add나 Remove가 일어나면 쉬프트 필요 프런트 삭제 시에 Front ++;에 의해 프런트가 전진 프런트 삽입 시에 Front - -;에 의해 프런트가 후진 Front 가 0에서 -1로 변할 때는 결국 7로 변해야 함. Data Structure

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