Queue - 1

특성

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료 구조
• 선형큐와 원형큐(환원큐) 의 종류로 나뉜다.
• FIFO 구조

---

연산

enQueue(item) : 큐의 가장 꼬리에 원소를 삽입하는 연산
deQueue() : 큐의 앞쪽에서 원소를 삭제하고 반환하는 연산
createQueue() : 큐의 생성자, 공백 상태의 큐를 생성
isEmpty()
isFull() : 큐가 포화 상태인지 확인하는 연산
Qpeek() : 큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산

(2)의 그림을 보면, rear 는 마지막 데이터의 인덱스를 가르킨다.
또한 front 는 가장 앞의 데이터 인덱스 -1이 된다. Queue의 사이즈는 rear-front가 된다.

(7)에서 보면, 모두 삭제가 일어나게 되면, front와 rear는 같은 위치가 된다.
(삭제 : front-- / 삽입 : rear++)

---

선형 큐

큐의 크기는 배열의 크기와 동일하다
초기에는 front 와 rear 는 -1로 되어있고, 이와 같이 front와 rear가 같다면 공백 상태로 본다.
rear == n-1 (n:배열의 크기, n-1 배열의 마지막 인덱스) 의 경우 포화 상태로 본다.

구현

1. 초기 공백 큐 생성
   • 크기가 n인 1차원 배열 생성
   • front 와 rear 를 -1로 초기화
   • 큐의 사이즈는 10개를 담을 수 있는 것이 아니라, 10번 삽입이 가능한 것을 의미

static String[] queue = new String[10]; 

static int front = -1;
static int rear = -1;

2. 삽입 : enQueue(item)
   • 마지막 원소 뒤에 새로운 원소를 삽입
   • rear를 하나 증가시켜 새로운 원소를 삽입할 자리 마련
   • 사이즈를 넘어가지 않도록 한 번 확인을 해줘야 한다.

// 삽입 성공 여부를 반환하는 boolean 타입도 가능 
static void enQueue(String item) {
	if(isFull()) {
		System.out.println("큐가 가득 찼습니다.");
		return;
	}
	queue[++rear] = item;
}

3. 공백 및 포화 상태 검사 : isEmpty(), isFull()

static boolean isEmpty() {
	if (front == rear) return true;
	else return false; 
		
	// return front == rear 
	// 이라는 간단한 식으로 해도 된다. 
}
	
static boolean isFull() {
	return rear == queue.length - 1;
}

4. 삭제 : deQueue()
   • 가장 앞에 있는 원소를 삭제하기 위해
   • front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소 이동
   • 새로운 첫 번째 원소를 리턴 함으로써 삭제와 동일한 기능을 한다.

static String deQueue() {
	if(isEmpty()) {
		System.out.println("큐가 비어있습니다.");
		return null;
	}
		
	String item = queue[++front];
	return item;
}

5. 조회 : Qpeek()
   • 가장 앞에 있는 값을 조회
   • deQueue와 동일한 수식을 쓰지만, 삭제와 달리 front 값을 올리지 않는다.

static String Qpeek() {
	if(isEmpty()) {
		System.out.println("큐가 비어있습니다.");
		return null;
	}
	String item = queue[front + 1];
	return item;
}

6. 사이즈 확인 : size()

static int size() {
	return rear - front;
}

---

선형 큐 이용 시 문제점

• 잘못된 포화 상태 인식
  • 선형 큐를 이용하여 원소의 삽입과 삭제를 계속하면, 배열의 앞부분은 비어있어, 활용할 수 있지만 rear = n-1인 포화 상태로 더는 삽입을 수행하지 않는다.
  • 이런 상태를 해결하기 위해, 저장된 원소들을 배열의 앞부분으로 모두 이동 시켜야 한다.
  • 다만, 많은 시간이 소요되어 큐의 효율 성이 급격히 떨어진다.
  • 배열 대신 연결 리스트(LinkedList)를 사용하여도 가능하다.
  • 혹은 원형 큐를 사용할 수 있다.
    • 원형 큐 : 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 있는 것
    • n - 1의 값이 되는 경우, 다시 0번 인덱스로 돌아가는 방식. 모듈러 연산 (i = (i+1)%N) 으로 인덱스 진행을 하면 된다.
    • 다만 front와 rear가 같은 값이 나오게 되는, 포화 상태와 공백 상태의 구분이 어렵다.

---

큐의 활용

public class Queue_큐API {

	public static void main(String[] args) {
//		Queue<Integer> queue = new Queue<>();
// 		큐는 인터페이스이기 때문에, 구현체로 만들 수 없다. 
		Queue<Integer> queue = new LinkedList<>();
		
		// 삽입
		queue.add(1); // 추가될 수 없는 상태면 예외 발생을 시킨다. 
		queue.offer(1); // 추가될 수 없으면 return false
		
		System.out.println(queue);
		
		// 삭제
		queue.remove(); // 큐가 비어있으면, 예외 발생 
		queue.poll(); // 삭제될 수 없으면 return null 
		
		
		// 조회
		queue.element(); // 예외 발생 
		queue.peek(); // return null
		
		
	}

}

버퍼 (buffer)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Person{
	int no;
	int cnt;
	
	public Person (int no,int cnt) {
		this.no = no;
		this.cnt = cnt;
	}
	
	@Override
	public String toString() {
		return "마이쮸 현황 : " + no + "번째의 사람이, " + cnt + "개 갖고 가져갔습니다.";
	}
}

public class Queue_마이쮸 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Queue<Person> queue = new LinkedList<>();
		System.out.print("몇 개의 마이쮸를 나눠 가질 건가요? >> ");
		// 전체 마이쮸 갯수 
		int N = sc.nextInt(); 

		int pNum = 1;
		
		
		queue.add(new Person(pNum++, 1));
		System.out.println();
		while (N > 0) {
			// 큐에서 한 명이 빠져나와 마이쮸를 갖고 간다. 
			Person p = queue.poll();
			
			N -= p.cnt;
			System.out.println(p.toString());
			System.out.println("남은 마이쮸는 " + N + "개");
			if (N <= 0) {
				System.out.println(p.no + "번이 마지막을 갖고 갔습니다.");
				break;
			}
			
			p.cnt++;
			
			// 갖고 갈 수 있는 갯수를 늘리고 삽입 
			queue.add(p);
			
			// 새 멤버 추가 
			queue.add(new Person(pNum++, 1));
			
		}
	}
}

마이쮸 나눠 갖기.