자료구조론 8장 큐(queue).

Presentation on theme: "자료구조론 8장 큐(queue)."— Presentation transcript:

1 자료구조론 8장 큐(queue)

2 이 장에서 다룰 내용 큐 큐의 구현 큐의 응용

3 큐 큐(Queue) 삽입과 삭제의 위치가 다음과 같이 제한된 유한 순서 리스트
삭제는 한쪽 끝(front)에서만 이루어지고, 삽입은 다른쪽 끝(rear) 에서만 이루어진다. 선입선출 구조 (FIFO, First-In-First-Out) 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)된 원 소가 맨 앞에 있다가 가장 먼저 삭제(First-Out)된다.

4 큐 큐의 구조 큐의 연산 큐에서의 삽입 연산 : enQueue 큐에서의 삭제 연산 : deQueue

5 큐 스택과 큐의 비교 구조 연산

6 큐의 추상자료형 ADT Queue 데이터 : 0개 이상의 원소를 가진 유한 순서 리스트
연산 : Q∈Queue; item∈Element; createQueue() ∷= create an empty Q; // 공백 큐를 생성하는 연산 isEmpty(Q) ∷= if (Q is empty) then return true else return false; // 큐가 공백인지 아닌지를 확인하는 연산 enQueue(Q, item) ∷= insert item at the rear of Q; // 큐의 rear에 item(원소)을 삽입하는 연산 deQueue(Q) ∷= if (isEmpty(Q)) then return error else { delete and return the front item of Q }; // 큐의 front에 있는 item(원소)을 큐에서 삭제하고 반환하는 연산 delete(Q) ∷= if (isEmpty(Q)) then return error else { delete the front item of Q }; // 큐의 front에 있는 item(원소)을 삭제하는 연산 peek(Q) ∷= if (isEmpty(Q)) then return error else { return the front item of the Q }; // 큐의 front에 있는 item(원소)을 반환하는 연산 End Queue [ADT 8-1]

7 큐의 구현 선형 큐 1차원 배열을 이용한 큐 큐의 크기 = 배열의 크기
변수 front : 저장된 첫 번째 원소 바로 앞 인덱스 저장 변수 rear : 저장된 마지막 원소의 인덱스 저장 상태 표현 초기 상태 : front = rear = -1 공백 상태 : front = rear 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스) [0] [1] [n-2] [n-1] Q D E F G front rear

8 큐의 구현 큐의 연산 과정 공백 큐 생성 : createQueue(); 원소 A 삽입 : enQueue(Q, A);
원소 B 삽입 : enQueue(Q, B); [0] [1] [2] front = rear = -1 Q [0] [1] [2] Q A rear front = -1 [0] [1] [2] Q A B rear front = -1

9 큐의 구현 원소 삭제 : deQueue(Q); 원소 C 삽입 : enQueue(Q, C); Q A front rear Q
[0] [1] [2] Q B A front rear [0] [1] [2] Q B C front rear Q [0] [1] [2] B C front rear [0] [1] [2] Q C front rear

10 큐의 구현 큐 생성 알고리즘 크기가 n인 1차원 배열 생성 front와 rear를 -1로 초기화 createQueue()
Q[n]; front ← -1; rear ← -1; end createQueue() [알고리즘 8-1]

11 큐의 구현 공백상태/포화상태 검사 알고리즘 공백 상태 : front = rear 포화 상태 : rear = n-1
(n : 배열의 크기, n-1 : 배열의 마지막 인덱스) isEmpty(Q) if(front=rear) then return true; else return false; end isEmpty() isFull(Q) if(rear=n-1) then return true; end isFull() [알고리즘 8-2]

12 큐의 구현 큐의 삽입 알고리즘 마지막 원소의 뒤에 삽입해야 하므로
① 마지막 원소의 인덱스를 저장한 rear의 값을 하나 증가시켜 삽입할 자리 준비 ② rear 위치에 item을 저장 enQueue(Q, item) if(isFull(Q)) then Queue_Full(); else { rear ← rear+1; // ❶ Q[rear] ← item; // ❷ } end enQueue() [알고리즘 8-3] [0] [1] [2] [0] [1] [2] Q Q A B A B C rear rear rear front front

13 큐의 구현 큐의 삭제 알고리즘 가장 앞에 있는 원소를 삭제해야 하므로
① front의 위치를 한자리 뒤로 이동하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리 준비 ② 그 자리의 원소를 삭제하여 반환 deQueue(Q) if(isEmpty(Q)) then Queue_Empty(); else { front ← front+1; // ❶ return Q[front]; // ❷ } end deQueue() [알고리즘 8-4] [0] [1] [2] [0] [1] [2] Q Q A B C A B C front rear front rear front

14 큐의 구현 순차 자료구조 방식으로 구현한 큐 프로그램
public class ArrayQueue implements Queue{ private int front; private int rear; private int queueSize; private char[] itemArray; public ArrayQueue(int queueSize){ front = -1; rear = -1; this.queueSize = queueSize; itemArray = new char[queueSize]; } public boolean isEmpty(){ return (front == rear); public boolean isFull(){ return (rear == queueSize-1); public interface Queue{ boolean isEmpty(); void enQueue(char item); char deQueue(); void delete(); char peek(); }

15 큐의 구현 public void enQueue(char item){ if(isFull()){
System.out.println("Inserting fail! Array Queue is full!!"); } else{ itemArray[++rear] = item; public char deQueue(){ if(isEmpty()) { System.out.println("Deleting fail! Array Queue is empty!!"); return 0; return itemArray[++front];

16 큐의 구현 public void delete(){ if(isEmpty())
System.out.println("Deleting fail! Array Queue is empty!!"); else ++front; } public char peek(){ if(isEmpty()){ System.out.println("Peeking fail! Array Queue is empty!!"); return 0; return itemArray[front+1]; public String toString(){ String result = "Array Queue>> "; for(int i=front+1; i<=rear; i++) result += itemArray[i] + " "; return result;

17 큐의 구현 public class Ex8_1 { public static void main(String[] args){
ArrayQueue q = new ArrayQueue(3); q.enQueue('A'); System.out.println(q); q.enQueue('B'); System.out.println(q); char deletedItem = q.deQueue(); if(deletedItem != 0) System.out.println("deleted item : " + deletedItem); System.out.println(q); deletedItem = q.deQueue(); q.enQueue('C'); System.out.println(q); q.enQueue('D'); System.out.println(q); }

18 큐의 구현 – 원형 큐 선형 큐의 포화 상태 문제 선형 큐의 잘못된 포화상태 인식의 해결 방법 (1)
큐에서 삽입과 삭제를 반복하면서 앞부분에 빈자리가 있지만 포화상 태(rear=n-1)로 인식하여 더 이상의 삽입을 수행할 수 없는 경우가 생긴다. 선형 큐의 잘못된 포화상태 인식의 해결 방법 (1) 저장된 원소들을 배열의 앞부분으로 이동시킴  순차자료에서의 이동 작업으로 효율 떨어짐 [0] [1] [n-2] [n-1] Q D E F front rear [0] [1] [n-2] [n-1] Q D E F front rear

19 큐의 구현 – 원형 큐 선형 큐의 잘못된 포화상태 인식의 해결 방법 (2) 원형 큐(circular queue)
1차원 배열을 사용하되 논리적으로 배열의 처음과 끝이 연결되 어 있다고 가정하고 사용 즉, Q[n-1] 다음 원소가 Q[0] 원형 큐의 논리적 구조

20 큐의 구현 – 원형 큐 원형 큐의 구조 초기 공백 상태 : front = rear = 0
큐 연산시 front와 rear의 위치 이동 : 배열의 마지막 인덱스 n-1 다 음 인덱스 0번으로 이동하기 위해서 나머지연산자 mod를 사용 선형 큐 원형 큐 front = front front = (front + 1) mod n rear = rear rear = (rear + 1) mod n 예를 들어 n=5인 경우 0 0 1 1 2 2 3 3 4 4 5 0 6 1 0+1 1+1 2+1 3+1 4+1 5+1 (0+1) mod 5 (1+1) mod 5 (2+1) mod 5 (3+1) mod 5 (4+1) mod 5

21 큐의 구현 – 원형 큐 공백 상태와 포화 상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다. 삽입 A empty A rear rear front 삽입 BCDEF front rear front rear E F D E F C B A 삭제 4회 front

22 큐의 구현 – 원형 큐 F Q G P G O H N I M J L K empty full front rear front
삭제 삭제 empty 삽입 G front rear front rear Q G P G O H full 삽입 HIJKLMHOPQ N I M J L K

23 큐의 구현 – 원형 큐 원형 큐 생성 알고리즘 크기가 n인 1차원 배열 생성 front와 rear를 0 으로 초기화
createQueue() cQ[n]; front ← 0; rear ← 0; end createQueue() [알고리즘 8-6]

24 큐의 구현 – 원형 큐 원형 큐의 공백상태/포화상태 검사 알고리즘 공백 상태 front = rear
포화 상태 : 삽입할 rear의 다음 위치 = front의 현재 위치 (rear+1) mod n = front isEmpty(cQ) if(front=rear) then return true; else return false; end isEmpty() isFull(cQ) if(((rear+1) mod n)=front) then return true; end isFull() [알고리즘 8-7]

25 큐의 구현 – 원형 큐 원형 큐의 삽입 알고리즘 ① rear의 값을 조정하여 삽입할 자리를 준비
rear ← (rear+1) mod n; ② 준비한 자리 cQ[rear]에 원소 item을 삽입 enQueue(cQ, item) if(isFull(cQ)) then Queue_Full(); else { rear ← (rear+1) mod n; // ❶ cQ[rear] ← item; // ❷ } end enQueue() [알고리즘 8-8]

26 큐의 구현 – 원형 큐 원형 큐의 삭제 알고리즘 ① front의 값을 조정하여 삭제할 자리를 준비
front ← (front+1) mod n; ② 준비한 자리에 있는 원소 cQ[front]를 삭제하여 반환 deQueue(cQ) if(isEmpty(cQ)) then Queue_Empty(); else { front ← (front+1) mod n; // ❶ return cQ[front]; // ❷ } end deQueue() [알고리즘 8-9]

27 큐의 구현 – 원형 큐 순차 자료구조 방식으로 구현한 원형 큐 프로그램
public class ArrayCQueue implements Queue { private int front; private int rear; private int queueSize; private char itemArray[]; public ArrayCQueue(int queueSize){ front = 0; rear = 0; this.queueSize = queueSize; itemArray = new char[queueSize]; } public boolean isEmpty(){ return (front == rear); public boolean isFull(){ return (((rear+1) % queueSize) == front); public interface Queue{ boolean isEmpty(); void enQueue(char item); char deQueue(); void delete(); char peek(); }

28 큐의 구현 – 원형 큐 public void enQueue(char item){ if(isFull()){
System.out.println("Inserting fail! Array Circular Queue is full!!"); } else{ rear = (rear+1) % queueSize; itemArray[rear] = item; public char deQueue(){ if(isEmpty()) { System.out.println("Deleting fail! Array Circular Queue is empty!!"); return 0; front = (front+1) % queueSize; return itemArray[front];

29 큐의 구현 – 원형 큐 public void delete(){ if(isEmpty())
System.out.println("Deleting fail! Array Circular Queue is empty!!"); else front = (front+1) % queueSize; } public char peek(){ if(isEmpty()){ System.out.println("Peeking fail! Array Circular Queue is empty!!"); return 0; return itemArray[(front+1) % queueSize]; public String toString(){ String result = "Array Circular Queue>> "; for(int i=(front+1) % queueSize; i!=(rear+1)% queueSize; i=++i % queueSize) result += itemArray[i] + “ “; return result;

30 큐의 구현 – 원형 큐 public class Ex8_2 {
public static void main(String args[]){ ArrayCQueue cQ = new ArrayCQueue(3); cQ.enQueue('A'); System.out.println(cQ); cQ.enQueue('B'); System.out.println(cQ); char deletedItem = cQ.deQueue(); if(deletedItem != 0) System.out.println("deleted item : " + deletedItem); System.out.println(cQ); deletedItem = cQ.deQueue(); cQ.enQueue('C'); System.out.println(cQ); cQ.enQueue('D'); System.out.println(cQ); }

31 큐의 구현 – 연결리스트 구현 연결리스트로 구현한 큐 단순 연결 리스트를 이용하여 큐를 구현할 수 있다.
front : 첫 번째 노드를 가리키는 객체 레퍼런스 변수 rear : 마지막 노드를 가리키는 객체 레퍼런스 변수 큐 노드의 순서는 링크로 표현됨 상태 표현 초기 상태 : front = rear = null 공백 상태 : front = rear = null 큐의 구조

32 큐의 구현 – 연결리스트 구현 큐 생성 알고리즘 초기화 : front = rear = null
createLinkedQueue() front ← null; rear ← null; end createLinkedQueue() [알고리즘 8-10]

33 큐의 구현 – 연결리스트 구현 큐의 공백상태 검사 알고리즘 공백 상태 : front = rear = null
isEmpty(LQ) if(front=null) then return true; else return false; end isEmpty() [알고리즘 8-11]

34 큐의 구현 – 연결리스트 구현 큐 삽입 알고리즘 enQueue(LQ, item) [알고리즘 8-12]
new ← getNode(); new.data ← item; new.link ← null; if (isEmpty(LQ)) then { // 연결 큐가 공백인 경우 rear ← new; front ← new; } else { // 연결 큐에 노드가 있는 경우 rear.link ← new; end enQueue() [알고리즘 8-12]

35 큐의 구현 – 연결리스트 구현 큐 삭제 알고리즘 deQueue(LQ)
if(isEmpty(LQ)) then Queue_Empty(); else { old ← front; item ← front.data; front ← front.link; if (isEmpty(LQ)) then rear ← null; returnNode(old); return item; } end deQueue() [알고리즘 8-13]

36 큐의 구현 – 연결리스트 구현 연산 과정 ① createLinkedQueue(); ② enQueue(LQ, A);
③ enQueue(LQ, B); ④ deQueue(LQ);

37 큐의 구현 – 연결리스트 구현 연결 자료구조 방식을 이용하여 구현한 큐 프로그램
public class LinkedQueue { QNode front, rear; public LinkedQueue(){ front = null; rear = null; } public boolean isEmpty(){ return (front == null); public void enQueue(char item){ QNode newNode = new QNode(); newNode.data = item; newNode.link = null; if(isEmpty()){ front = newNode; rear = newNode; else { rear.link = newNode; class QNode{ char data; QNode link; }

38 큐의 구현 – 연결리스트 구현 public char deQueue(){ if(isEmpty()) {
System.out.println("Deleting fail! Linked Queue is empty!!"); return 0; } else{ char item = front.data; front = front.link; if(front == null) rear = null; return item; public String toString(){ String result = "Linked Queue>> "; QNode temp = front; while(temp != null){ result += temp.data + “ “; temp = temp.link; return result;

39 Deque 덱(Deque, double-ended queue) 양쪽 끝에서 삽입과 삭제 연산이 모두 가능한 선형 자료구조
scroll : 입력이 한쪽 끝에서만 이루어지는 input restricted deque shelf : 출력이 한쪽 끝에서만 이루어지는 output restricted deque 삽입 삽입 삭제 삭제 front rear 저장된 원소 중에서 가장 앞부분 원소 저장된 원소 중에서 가장 뒷부분 원소

40 Deque 덱에 대한 추상 자료형 ADT deque 데이터 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 :
DQ∈deque; item∈Element; createDeque() ∷= create an empty DQ; // 공백 덱을 생성하는 연산 isEmpty(DQ) ∷= if (DQ is empty) then return true else return false; // 덱이 공백인지 아닌지를 확인하는 연산 insertFront(DQ, item) ∷= insert item at the front of DQ; // 덱의 front 앞에 item(원소)을 삽입하는 연산 insertRear(DQ, item) ∷= insert item at the rear of DQ; // 덱의 rear 뒤에 item(원소)을 삽입하는 연산 deleteFront(DQ) ∷= if (isEmpty(DQ)) then return null else { delete and return the front item of DQ }; // 덱의 front에 있는 item(원소)을 덱에서 삭제하고 반환하는 연산 deleteRear(DQ) ∷= if (isEmpty(DQ)) then return null else { delete and return the rear item of DQ }; // 덱의 rear에 있는 item(원소)을 덱에서 삭제하고 반환하는 연산 [ADT 8-2]

41 Deque removeFront(DQ) ∷= if (isEmpty(DQ)) then return null [ADT 8-2]
else { remove the front item of DQ }; // 덱의 front에 있는 item(원소)을 삭제하는 연산 removeRear(DQ) ∷= if (isEmpty(DQ)) then return null else { remove the rear item of DQ }; // 덱의 rear에 있는 item(원소)을 삭제하는 연산 peekFront(DQ) ∷= if (isEmpty(DQ)) then return null else { return the front item of the DQ }; // 덱의 front에 있는 item(원소)을 반환하는 연산 peekRear(DQ) ∷= if (isEmpty(DQ)) then return null else { return the rear item of the DQ }; // 덱의 rear에 있는 item(원소)을 반환하는 연산 End deque [ADT 8-2]

42 Deque 덱의 연산 과정 ① createDeque(); ② insertFront(DQ, 'A');
③ insertFront(DQ, 'B'); ④ insertRear(DQ, 'C'); front rear DQ A B C

43 Deque ⑤ deleteFront(DQ); ⑥ deleteRear(DQ); ⑦ insertRear(DQ, 'D');
⑧ insertFront(DQ, 'E'); ⑨ insertFront(DQ, 'F'); DQ A C B front rear DQ A C front rear DQ A D front rear DQ E A D front rear DQ F E A D front rear

44 덱의 구현 이중 연결리스트로 구현 덱은 양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저 장된 원소의 순서 변화가 많으므로 순차 자료구조로 구현하면 비 효율적이다. 양방향으로 연산이 가능하도록 이중 연결리스트로 구현한다.

45 큐의 응용 운영체제의 작업 큐 시뮬레이션에서의 큐잉 시스템 프린터 버퍼 큐
CPU에서 프린터로 보낸 데이터 순서대로(선입선출) 프린터에서 출력하기 위해서 선입선출 구조의 큐 사용 스케줄링 큐 CPU 사용을 요청한 프로세스들을 스케줄링하기 위해 큐를 사용 시뮬레이션에서의 큐잉 시스템 시뮬레이션을 위한 수학적 모델링에서 대기행렬과 대기시간 등을 모 델링하기 위해서 큐잉 이론(Queue theory) 사용