8 큐.

Slides:



Advertisements
Similar presentations
멘토링 2 주차 장 프로그래밍을 위한 자바의 자료형  값이 변하지 않는 상수  메모리 기억공간인 변수.
Advertisements

명품 JAVA Programming 제 3 장 반복문, 배열, 예외처리.
스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).
10. 예외 처리.
컴퓨터 응용 및 실습 Part1. OOP&Java Programming data type Review
3 장 stack and queue.
[INA240] Data Structures and Practice
Internet Computing KUT Youn-Hee Han
5장 큐.
Chapter 10 – 추상 자료형 Outline 10.1 소개 10.2 Ada의 추상 자료형 10.3 C++의 추상 자료형
실전 프로젝트 2 : 숫자야구 숫자 야구를 구현해보자.
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
자료구조 실습 (03분반)
5장. 리스트 리스트 학습목표 목록이나 도표처럼 여러 데이터를 관리할 수 있는 자료형을 추상화
6장 트리.
2주 실습강의 Java의 기본문법(1) 인공지능연구실.
Chapter 02 자바 기본구조 자바 프로그래밍의 기초적인 문법을 소개
Internet Computing KUT Youn-Hee Han
제7장 제어구조 I – 식과 문장.
명품 JAVA Essential.
Internet Computing KUT Youn-Hee Han
10장 객체-지향 프로그래밍 II ©창병모.
8장 자바 입출력.
4장 스택.
JAVA 프로그래밍 6장 객체지향프로그래밍의 핵심.
7 스택.
Power Java 제10장 배열.
배열, 포인터, 참조 배열은 같은 형을 가지는 변수들의 묶음이다..
Choi, Namseok Java 기초 (Java의 제어문과 배열) Choi, Namseok
제 4 장 L i s t.
스택(stack) SANGJI University Kwangman Ko
강의 #6 큐(Queue).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
다음 주 과제 7장 읽어오기 숙제 해서 다음 주(11월 12일) 제출하기. 큐(Queue) E304호,
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
명품 Java Programming.
최용술 장 Thread 최용술
C언어 응용 제 10 주 트리.
Chapter 05. 클래스 완성. chapter 05. 클래스 완성 01. 복사 생성자 복사 생성(Copy Construction) 생성될 때 자신과 같은 타입의 객체를 변수로 받아, 이 객체와 같은 값을 갖는 새로운 객체를 생성하는 것 명시적인 생성 과정뿐만.
김 정 석 Web Programming 김 정 석
주소록 프로그램.
스택(Stack) 김진수
제 4주 2014년 1학기 강원대학교 컴퓨터학부 담당교수: 정충교
12 검색.
IT CookBook, 자바로 배우는 쉬운 자료구조
CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
DataScience Lab. 박사과정 김희찬 (월)
03. 안드로이드를 위한 Java 문법 제목. 03. 안드로이드를 위한 Java 문법 제목.
WAP Java Seminar
Ch.1 Iterator Pattern <<interface>> Aggregate +iterator
Chapter 04 리스트.
제 2장 어휘구조와 자료형 토 큰 리 터 럴 주 석 자 료 형 배 열 형.
컴퓨터공학실습(I) 3주 인공지능연구실.
Chap02 객체 지향 개념 2.1 객체지향(object-oriented)과 절차지향(procedural-oriented)
프로그래머를 위한 첫걸음 JDBC Lecture 001 BY MINIO
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
Chapter 02. 소프트웨어와 자료구조.
Java 3장. 자바의 기본 구조 I : 변수, 자료형, 연산자 public class SumTest {
CHAP 8:우선순위큐.
제 11장. 템플릿과 STL 학기 프로그래밍언어및실습 (C++).
JVM의 구조와 메모리 모델 JVM의 내부 구조 클래스 파일 클래스 로더 메소드(method) 영역 힙(heap) 영역
자료구조론 8장 큐(queue).
자바 5.0 프로그래밍.
C# 10장. 참조형.
CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
DataScience Lab. 박사과정 김희찬 (화)
Presentation transcript:

8 큐

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

큐 큐(Queue) 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)된다. ☞ 선입선출 구조 (FIFO, First-In-First-Out) 스택과 큐의 구조 비교

큐 큐의 구조

큐 큐의 연산 삽입 : enQueue 삭제 : deQueue 스택과 큐의 연산 비교

큐 추상 자료형 큐 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 itemof 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]

큐 A B 큐의 연산 과정 공백 큐 생성 : 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

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

큐의 구현 선형 큐 1차원 배열을 이용한 큐 상태 표현 큐의 크기 = 배열의 크기 변수 front : 저장된 첫 번째 원소의 인덱스 저장 변수 rear : 저장된 마지막 원소의 인덱스 저장 상태 표현 초기 상태 : front = rear = -1 공백 상태 : front = rear 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

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

큐의 구현 공백 큐 검사 알고리즘과 포화상태 검사 알고리즘 공백 상태 : 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]

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

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

큐의 구현 큐의 검색 알고리즘 가장 앞에 있는 원소를 검색하여 반환하는 연산 ① 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐에 있는 첫 번째 원소를 반환 peek(Q) if(isEmpty(Q)) then Queue_Empty(); else return Q[front+1]; end peek() [알고리즘 8-5]

큐의 구현 순차 자료구조 방식으로 구현한 큐 프로그램 001 interface Queue{ 002 boolean isEmpty(); 003 void enQueue(char item); 004 char deQueue(); 005 void delete(); 006 char peek(); 007 } 008 009 class ArrayQueue implements Queue{ 010 private int front; 011 private int rear; 012 private int queueSize; 013 private char itemArray[]; 014 015 public ArrayQueue(int queueSize){ 016 front = -1; 017 rear = -1; [예제 5-4] >> 계속

큐의 구현 018 this.queueSize = queueSize; 019 itemArray = new char[this.queueSize]; 020 } 021 022 public boolean isEmpty(){ 023 return (front == rear); 024 } 025 026 public boolean isFull(){ 027 return (rear == this.queueSize-1); 028 } 029 030 public void enQueue(char item){ 031 if(isFull()){ 032 System.out.println("Inserting fail! Array Queue is full!!"); 033 } 034 else{ 035 itemArray[++rear] = item; [예제 5-4] >> 계속

큐의 구현 036 System.out.println("Inserted Item : " + item); 037 } 038 } 037 } 038 } 039 040 public char deQueue(){ 041 if(isEmpty()) { 042 System.out.println("Deleting fail! Array Queue is empty!!"); 043 return 0; 044 } 045 else{ 046 return itemArray[++front]; 047 } 048 049 } 050 051 public void delete(){ 052 if(isEmpty()){ 053 System.out.println("Deleting fail! Array Queue is empty!!"); [예제 5-4] >> 계속

큐의 구현 054 055 } 056 else { 057 ++front; 058 } 059 } 060 055 } 056 else { 057 ++front; 058 } 059 } 060 061 public char peek(){ 062 if(isEmpty()){ 063 System.out.println("Peeking fail! Array Queue is empty!!"); 064 return 0; 065 } 066 else 067 return itemArray[front+1]; 068 } 069 070 public void printQueue(){ 071 if(isEmpty()) [예제 5-4] >> 계속

큐의 구현 072 System.out.printf("Array Queue is empty!! %n %n"); 073 else{ 075 for(int i=front+1; i<=rear; i++) 076 System.out.printf("%c ", itemArray[i]); 077 System.out.println();System.out.println(); 078 } 079 } 080 081 } 082 083 class Ex8_1{ 084 public static void main(String args[]){ 085 int queueSize = 3; 086 char deletedItem; 087 ArrayQueue Q = new ArrayQueue(queueSize); 088 089 Q.enQueue('A'); [예제 5-4] >> 계속

큐의 구현 090 Q.printQueue(); 091 092 Q.enQueue('B'); 093 Q.printQueue(); 094 095 deletedItem = Q.deQueue(); 096 if(deletedItem != 0) 097 System.out.println("deleted Item : " + deletedItem); 098 Q.printQueue(); 099 100 Q.enQueue('C'); 101 Q.printQueue(); 102 103 deletedItem = Q.deQueue(); 104 if(deletedItem != 0) 105 System.out.println("deleted Item : " + deletedItem); 106 Q.printQueue(); 107 [예제 5-4] >> 계속

큐의 구현 108 deletedItem = Q.deQueue(); 109 if(deletedItem != 0) 110 System.out.println("deleted Item : " + deletedItem); 111 Q.printQueue(); 112 113 deletedItem = Q.deQueue(); 114 if(deletedItem != 0) 115 System.out.println("deleted Item : " + deletedItem); 116 Q.printQueue(); 117 } 118 } [예제 5-4] >> 계속

큐의 구현 실행 결과

큐의 구현 원형 큐 선형 큐의 잘못된 포화상태 인식 선형 큐의 잘못된 포화상태 인식의 해결 방법-1 큐에서 삽입과 삭제를 반복하면서 아래와 같은 상태일 경우, 앞부분에 빈 자리가 있지만 rear=n-1 상태이므로 포화상태로 인식하고 더 이상의 삽 입을 수행하지 않는다. 선형 큐의 잘못된 포화상태 인식의 해결 방법-1 저장된 원소들을 배열의 앞부분으로 이동시키기 순차자료에서의 이동 작업은 연산이 복잡하여 효율성이 떨어짐

큐의 구현 선형 큐의 잘못된 포화상태 인식의 해결 방법-2 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다 고 가정하고 사용 원형 큐의 논리적 구조

큐의 구현 원형 큐의 구조 초기 공백 상태 : front = rear = 0 front와 rear의 위치가 배열의 마지막 인덱스 n-1에서 논리적인 다음자리 인 인덱스 0번으로 이동하기 위해서 나머지연산자 mod를 사용 3 ÷ 4 = 0 …3 (몫=0, 나머지=3) 3 mod 4 = 3 공백 상태와 포화 상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사 용하지 않고 항상 빈자리로 둔다.

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

큐의 구현 원형 큐의 공백상태 검사 알고리즘과 포화상태 검사 알고리즘 공백 상태 : 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]

큐의 구현 원형 큐의 삽입 알고리즘 ① 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]

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

큐의 구현 원형 큐에서의 연산 과정 ① createQueue(); ② enQueue(cQ, A); A rear rear [0] [1] [2] [3] rear front rear [1] [2] A [0] [3] front

큐의 구현 ③ enQueue(cQ, B); ④ deQueue(cQ); ⑤ enQueue(cQ, C);                            ⑥ enQueue(cQ, D); rear front rear [1] [2] [1] [2] A B A B [0] [3] [0] [3] front front front [1] [2] B [1] [2] B C D C [0] [3] rear [0] [3] rear

큐의 구현 순차 자료구조 방식으로 구현한 원형 큐 프로그램 001 interface Queue{ 002 boolean isEmpty(); 003 void enQueue(char item); 004 char deQueue(); 005 void delete(); 006 char peek(); 007 } 008 009 class ArrayCQueue implements Queue{ 010 private int front; 011 private int rear; 012 private int queueSize; 013 private char itemArray[]; 014 015 public ArrayCQueue(int queueSize){ 016 front = 0; 017 rear = 0; [예제 5-4] >> 계속

큐의 구현 018 this.queueSize = queueSize; 019 itemArray = new char[this.queueSize]; 020 } 021 022 public boolean isEmpty(){ 023 return (front == rear); 024 } 025 026 public boolean isFull(){ 027 return (((rear+1) % this.queueSize) == front); 028 } 029 030 public void enQueue(char item){ 031 if(isFull()){ 032 System.out.println("Inserting fail! Array Circular Queue is full!!"); 033 } 034 else{ 035 rear = (rear+1) % this.queueSize; [예제 5-4] >> 계속

큐의 구현 036 itemArray[rear] = item; 037 System.out.println("Inserted Item : " + item); 038 } 039 } 040 041 public char deQueue(){ 042 if(isEmpty()) { 043 System.out.println("Deleting fail! Array Circular Queue is empty!!"); 044 return 0; 045 } 046 else{ 047 front = (front+1) % this.queueSize; 048 return itemArray[front]; 049 } 050 051 } 052 053 public void delete(){ [예제 5-4] >> 계속

큐의 구현 054 if(isEmpty()){ 055 System.out.println("Deleting fail! Array Circular Queue is empty!!"); 056 057 } 058 else { 059 front = (front+1) % this.queueSize; 060 } 061 } 062 063 public char peek(){ 064 if(isEmpty()){ 065 System.out.println("Peeking fail! Array Circular Queue is empty!!"); 066 return 0; 067 } 068 else 069 return itemArray[(front+1) % this.queueSize]; 070 } 071 [예제 5-4] >> 계속

큐의 구현 072 public void printQueue(){ 073 if(isEmpty()) 074 System.out.println("Array Circular Queue is empty!!"); 075 else{ 076 System.out.printf("Array Circular Queue>> "); 077 for(int i=(front+1) % this.queueSize; i!=(rear+1)% this.queueSize; i=++i % this.queueSize) 078 System.out.printf("%c ", itemArray[i]); 079 System.out.println(); System.out.println(); 080 } 081 } 082 083 } 084 085 086 class Ex8_2{ 087 public static void main(String args[]){ 088 int queueSize = 4; [예제 5-4] >> 계속

큐의 구현 089 char deletedItem; 090 ArrayCQueue cQ = new ArrayCQueue(queueSize); 091 092 cQ.enQueue('A'); 093 cQ.printQueue(); 094 095 cQ.enQueue('B'); 096 cQ.printQueue(); 097 098 deletedItem = cQ.deQueue(); 099 if(deletedItem != 0) 100 System.out.println("deleted Item : " + deletedItem); 101 cQ.printQueue(); 102 103 cQ.enQueue('C'); 104 cQ.printQueue(); 105 106 cQ.enQueue('D'); [예제 5-4] >> 계속

큐의 구현 실행 결과 107 cQ.printQueue(); 108 109 cQ.enQueue('E'); 111 } 112 } [예제 5-4]

큐의 구현 연결 큐 단순 연결 리스트를 이용한 큐 상태 표현 연결 큐의 구조 큐의 원소 : 단순 연결 리스트의 노드 큐의 원소의 순서 : 노드의 링크 포인터로 연결 변수 front : 첫 번째 노드를 가리키는 포인터 변수 변수 rear : 마지막 노드를 가리키는 포인터 변수 상태 표현 초기 상태와 공백 상태 : front = rear = null 연결 큐의 구조

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

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

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

큐의 구현 ① 삽입할 새 노드를 생성하여 데이터 필드에 item을 저장한다. 삽입할 새 노드는 연결 큐의 마지막 노드가 되어야 하므로 링크 필드에 null을 저장 한다. ② 새 노드를 삽입하기 전에 연결 큐가 공백인지 아닌지를 검사한다. 연결 큐가 공백인 경우에는 삽입할 새 노드가 큐의 첫 번째 노드이자 마지막 노드이므로 포인터 front와 rear가 모두 새 노드를 가리키도록 설정한다.

큐의 구현 ③ 큐가 공백이 아닌 경우, 즉 노드가 있는 경우에는 현재 큐의 마지막 노 드의 뒤에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정한다.

큐의 구현 연결 큐의 삭제 알고리즘 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() delete(LQ) old ← front; front ← front.link; if(isEmpty(LQ)) then rear ← null; returnNode(old); end delete() [알고리즘 8-13]

큐의 구현 ① 삭제연산에서 삭제할 노드는 큐의 첫 번째 노드로서 포인터 front가 가 리키고 있는 노드이다. front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다. ② 삭제연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫번째 노드) 가 되어야하므로, 포인터 front를 재설정한다.

큐의 구현 ③ 현재 큐에 노드가 하나뿐이어서 삭제연산 후에 공백 큐가 되는 경우 : ☞ 큐의 마지막 노드가 없어지므로 포인터 rear를 null로 설정한다. ④ 포인터 old가 가리키고 있는 노드를 삭제하고, 메모리 공간을 시스템에 반환(returnNode())한다

큐의 구현 연결 큐의 검색 알고리즘 연결 큐의 첫 번째 노드, 즉 front 노드의 데이터 필드 값을 반환 peek(LQ) if(isEmpty(LQ)) then Queue_Empty() else return (front.data); end peek() [알고리즘 8-14]

큐의 구현 연결 큐에서의 연산 과정 ① 공백 큐 생성 : createLinkedQueue(); ② 원소 A 삽입 : enQueue(LQ, A); ③ 원소 B 삽입 : enQueue(LQ, B);

큐의 구현 ④ 원소 삭제 : deQueue(LQ); ⑤ 원소 C 삽입 : enQueue(LQ, C);

큐의 구현 ⑥ 원소 삭제 : deQueue(LQ); ⑦ 원소 삭제 : deQueue(LQ);

큐의 구현 연결 자료구조 방식을 이용하여 구현한 연결 큐 프로그램 001 interface Queue{ 002 boolean isEmpty(); 003 void enQueue(char item); 004 char deQueue(); 005 void delete(); 006 char peek(); 007 } 008 009 class QNode{ 010 char data; 011 QNode link; 012 } 013 014 class LinkedQueue implements Queue{ 015 QNode front; 016 QNode rear; 017 [예제 8-3] >> 계속

큐의 구현 018 public LinkedQueue(){ 019 front = null; 020 rear = null; 021 } 022 023 public boolean isEmpty(){ 024 return (front == null); 025 } 026 027 public void enQueue(char item){ 028 QNode newNode = new QNode(); 029 newNode.data = item; 030 newNode.link = null; 031 if(isEmpty()){ 032 front = newNode; 033 rear = newNode; 034 } 035 else { [예제 8-3] >> 계속

큐의 구현 036 rear.link = newNode; 037 rear = newNode; 038 } 038 } 039 System.out.println("Inserted Item : " + item); 040 } 041 042 public char deQueue(){ 043 if(isEmpty()) { 044 System.out.println("Deleting fail! Linked Queue is empty!!"); 045 return 0; 046 } 047 else{ 048 char item = front.data; 049 front = front.link; 050 if(front == null) 051 rear = null; 052 return item; 053 } [예제 8-3] >> 계속

큐의 구현 054 } 055 056 public void delete(){ 057 if(isEmpty()){ 054 } 055 056 public void delete(){ 057 if(isEmpty()){ 058 System.out.println("Deleting fail! Linked Queue is empty!!"); 059 } 060 061 else { 062 front = front.link; 063 if(front == null) 064 rear = null; 065 } 066 } 067 068 public char peek(){ 069 if(isEmpty()){ 070 System.out.println("Peeking fail! Linked Queue is empty!!"); 071 return 0; [예제 8-3] >> 계속

큐의 구현 072 } 073 else 074 return front.data; 075 } 076 072 } 073 else 074 return front.data; 075 } 076 077 public void printQueue(){ 078 if(isEmpty()) 079 System.out.printf("Linked Queue is empty!! %n %n"); 080 else{ 081 QNode temp = front; 082 System.out.printf("Linked Queue>> "); 083 while(temp != null){ 084 System.out.printf("%c ", temp.data); 085 temp = temp.link; 086 } 087 System.out.println();System.out.println(); 088 } 089 } [예제 8-3] >> 계속

큐의 구현 090 } 091 092 class Ex8_3{ 093 public static void main(String args[]){ 094 char deletedItem; 095 LinkedQueue LQ = new LinkedQueue(); 096 097 LQ.enQueue('A'); 098 LQ.printQueue(); 099 100 LQ.enQueue('B'); 101 LQ.printQueue(); 102 103 deletedItem = LQ.deQueue(); 104 if(deletedItem != 0) 105 System.out.println("deleted Item : " + deletedItem); 106 LQ.printQueue(); 107 [예제 8-3] >> 계속

큐의 구현 108 LQ.enQueue('C'); 109 LQ.printQueue(); 110 111 deletedItem = LQ.deQueue(); 112 if(deletedItem != 0) 113 System.out.println("deleted Item : " + deletedItem); 114 LQ.printQueue(); 115 116 deletedItem = LQ.deQueue(); 117 if(deletedItem != 0) 118 System.out.println("deleted Item : " + deletedItem); 119 LQ.printQueue(); 120 121 deletedItem = LQ.deQueue(); 122 if(deletedItem != 0) 123 System.out.println("deleted Item : " + deletedItem); 124 LQ.printQueue(); 125 } 126 } [예제 8-3]

큐의 구현 실행 결과

큐의 구현  덱(Deque, double-ended queue) 큐 2개를 반대로 붙여서 만든 자료구조 Deque 삭제 삽입 Queue-1 Queue-2  front rear 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 }; [ADT 8-2]

큐의 구현 // 덱의 rear에 있는 item(원소)을 덱에서 삭제하고 반환하는 연산 removeFront(DQ) ∷= if (isEmpty(DQ)) then return null 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]

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

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

덱 덱의 구현 ⑨ insertFront(DQ, 'F'); 양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서 변화가 많으므로 순차 자료구조는 비효율적 양방향으로 연산이 가능한 이중 연결 리스트를 사용한다. DQ F E A front rear D

덱의 구현 이중 연결 리스트를 이용한 덱 프로그램 001 class DQNode{ 002 char data; 003 DQNode rlink; 004 DQNode llink; 005 } 006 007 class DQueue{ 008 DQNode front; 009 DQNode rear; 010 011 public DQueue(){ 012 front = null; 013 rear = null; 014 } 015 016 public boolean isEmpty(){ 017 return (front == null); [예제 8-4] >> 계속

덱의 구현 018 } 019 020 public void insertFront(char item){ 018 } 019 020 public void insertFront(char item){ 021 DQNode newNode = new DQNode(); 022 newNode.data = item; 023 if(isEmpty()){ 024 front = newNode; 025 rear = newNode; 026 newNode.rlink = null; 027 newNode.llink = null; 028 } 029 else { 030 front.llink = newNode; 031 newNode.rlink = front; 032 newNode.llink = null; 033 front = newNode; 034 } 035 System.out.println("Front Inserted Item : " + item); [예제 8-4] >> 계속

덱의 구현 036 } 037 038 public void insertRear(char item){ 036 } 037 038 public void insertRear(char item){ 039 DQNode newNode = new DQNode(); 040 newNode.data = item; 041 if(isEmpty()){ 042 front = newNode; 043 rear = newNode; 044 newNode.rlink = null; 045 newNode.llink = null; 046 } 047 else { 048 rear.rlink = newNode; 049 newNode.rlink = null; 050 newNode.llink = rear; 051 rear = newNode; 052 } 053 System.out.println("Rear Inserted Item : " + item); [예제 8-4] >> 계속

덱의 구현 054 } 055 056 public char deleteFront(){ 057 if(isEmpty()) { 054 } 055 056 public char deleteFront(){ 057 if(isEmpty()) { 058 System.out.println("Front Deleting fail! Dqueue is empty!!"); 059 return 0; 060 } 061 else{ 062 char item = front.data; 063 if(front.rlink == null){ 064 front = null; 065 rear = null; 066 } 067 else { 068 front = front.rlink; 069 front.llink = null; 070 } 071 return item; [예제 8-4] >> 계속

덱의 구현 072 } 073 } 074 075 public char deleteRear(){ 072 } 073 } 074 075 public char deleteRear(){ 076 if(isEmpty()) { 077 System.out.println("Rear Deleting fail! Dqueue is empty!!"); 078 return 0; 079 } 080 else{ 081 char item = rear.data; 082 if(rear.llink == null){ 083 rear = null; 084 front = null; 085 } 086 else { 087 rear = rear.llink; 088 rear.rlink = null; 089 } [예제 8-4] >> 계속

덱의 구현 090 return item; 091 } 092 } 093 094 public void removeFront(){ 091 } 092 } 093 094 public void removeFront(){ 095 if(isEmpty()) { 096 System.out.println("Front Removing fail! Dqueue is empty!!"); 097 } 098 else{ 099 if(front.rlink == null){ 100 front = null; 101 rear = null; 102 } 103 else { 104 front = front.rlink; 105 front.llink = null; 106 } 107 } [예제 8-4] >> 계속

덱의 구현 108 } 109 110 public void removeRear(){ 111 if(isEmpty()) { 108 } 109 110 public void removeRear(){ 111 if(isEmpty()) { 112 System.out.println("Rear Removing fail! Dqueue is empty!!"); 113 } 114 else{ 115 if(rear.llink == null){ 116 rear = null; 117 front = null; 118 } 119 else { 120 rear = rear.llink; 121 rear.rlink = null; 122 } 123 } 124 } 125 [예제 8-4] >> 계속

덱의 구현 126 public char peekFront(){ 127 if(isEmpty()){ 128 System.out.println("Front Peeking fail! DQueue is empty!!"); 129 return 0; 130 } 131 else 132 return front.data; 133 } 134 135 public char peekRear(){ 136 if(isEmpty()){ 137 System.out.println("Rear Peeking fail! DQueue is empty!!"); 138 return 0; 139 } 140 else 141 return rear.data; 142 } 143 [예제 8-4] >> 계속

덱의 구현 144 public void printDQueue(){ 145 if(isEmpty()) 146 System.out.printf("DQueue is empty!! %n %n"); 147 else{ 148 DQNode temp = front; 149 System.out.printf("DQueue>> "); 150 while(temp != null){ 151 System.out.printf("%c ", temp.data); 152 temp = temp.rlink; 153 } 154 System.out.println(); System.out.println(); 155 } 156 } 157 } 158 159 class Ex8_4{ 160 public static void main(String args[]){ 161 char deletedItem; [예제 8-4] >> 계속

덱의 구현 162 DQueue DQ = new DQueue(); 163 164 DQ.insertFront('A'); 165 DQ.printDQueue(); 166 167 DQ.insertFront('B'); 168 DQ.printDQueue(); 169 170 DQ.insertRear('C'); 171 DQ.printDQueue(); 172 173 deletedItem = DQ.deleteFront(); 174 if(deletedItem != 0) 175 System.out.println("Front deleted Item : " + deletedItem); 176 DQ.printDQueue(); 177 178 deletedItem = DQ.deleteRear(); 179 if(deletedItem != 0) [예제 8-4] >> 계속

덱의 구현 180 System.out.println("Rear deleted Item : " + deletedItem); 181 DQ.printDQueue(); 182 183 DQ.insertRear('D'); 184 DQ.printDQueue(); 185 186 DQ.insertFront('E'); 187 DQ.printDQueue(); 188 189 DQ.insertFront('F'); 190 DQ.printDQueue(); 191 } 192 } [예제 8-4] >> 계속

덱의 구현 실행 결과

큐의 응용 운영체제의 작업 큐 프린터 버퍼 큐 스케줄링 큐 CPU에서 프린터로 보낸 데이터 순서대로(선입선출) 프린터에서 출력하 기 위해서 선입선출 구조의 큐 사용 스케줄링 큐 CPU 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해 큐를 사용

큐의 응용 시뮬레이션 큐잉 시스템 시뮬레이션을 위한 수학적 모델링에서 대기행렬과 대기시간 등을 모델링하기 위해서 큐잉 이론(Queue theory) 사용