---

⚡ Queue와 삽입 정렬

---

📌 원형 큐

🔷 선형 큐의 잘못된 포화 인식 단점을 해결하기 위한 큐 구조

• 물리적으로는 선형이나 논리적으로는 원형의 구조를 가지고 있다.

🔷 구조

• 초기 공백 상태

  • front == rear == 0

• index의 순환

  • front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 한다
  • 나머지 연산자 mod 사용

• front 변수

  • 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다.

	삽입 위치	삭제 위치
선형큐	rear = rear+1	front = front+1
원형큐	rear = (rear+1)%n	front = (front+1)%n

import java.util.Arrays;

public class dailyClass {
	// 배열을 선언함으로써 createQueue 연산을 한 것이라고 생각
	public static String[] queue = new String[5];
	public static int size = queue.length;
	// 원형의 도넛 모양
	// front: 마지막으로 삭제된 원소의 위치, 공백과 포화를 구분하기 위해 비워둔다
	// rear: 마지막 원소의 위치
	public static int front = 0, rear = 0;
	
	public static void main(String[] args) {
		enQueue("박영규");
		enQueue("박영규");
		enQueue("박영규");
		enQueue("박영규");
		System.out.println(Arrays.toString(queue));
		System.out.println(front + " " + rear);
		System.out.println(deQueue());
		System.out.println(Arrays.toString(queue));
		System.out.println(front + " " + rear);
		enQueue("새 박영규");
		System.out.println(Arrays.toString(queue));
		System.out.println(deQueue());
		enQueue("새 박영규");
		System.out.println(front + " " + rear);
		System.out.println(Arrays.toString(queue));
	}
	
	// 공백 검사
	public static boolean isEmpty() {
		return front == rear;
	}
	
	// 포화 검사
	public static boolean isFull() {
		return (rear+1)%size == front;
	}
	
	// 삽입: void
	public static void enQueue(String item) {
		// 배열로 구현시에만 해당하는 로직
		if(isFull()) {
			System.out.println("꽉 찼어용");
			return;
		}
		rear = (++rear)%size;
		queue[rear] = item;
	}
	
	// 삭제
	public static String deQueue() {
		if(isEmpty()) {
			System.out.println("비었음");
			return null;
		}
		
		front = (++front)%size;
		return queue[front];
	}
}

---

📌 우선순위 큐(Priority Queue)

🔷 특성

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO 순서가 아니라 우선순위가 높은 대로 먼저 나가게 된다.

🔷 우선순위 큐의 적용 분야

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영체제의 테스크 스케줄링

🔷 구현

• 배열 혹은 리스트를 이용
• enQueue: 우선순위에 맞게 재배치를 해줘야 함

  ❗ 배열로 구현 시에 곤란할 수 있다. 원소의 재배치가 발생하면 시간과 메모리 낭비가 크기 때문에...

• deQueue: 일반 큐와 동일

💡 우선순위 큐는 자바에서 당연히 제공해준다!
단, comparator or comparable 활용이 필수적

---

📌 삽입 정렬(Insertion Sort)

🔷 자료 배열의 모든 원소들을 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성한다.

🔷 정렬 과정

• 정렬할 자료를 두 개의 부분집합 S와 U로 가정
  • 부분집합 S: 정렬된 앞부분의 원소들
  • 부분집합 U: 아직 정렬되지 않은 나머지 원소들
• 정렬되지 않는 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입
• 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다, 부분집합 U가 공집합이 되면 삽입 정렬이 완성

💡 시간복잡도는 O(n^2), 최선일 때 O(n) => 이미 정렬되어있을 때

import java.util.Arrays;

public class dailyClass {
	static int data[] = {69, 10, 30, 2, 16, 8, 31, 22};
	
	public static void main(String[] args) {
		// 배열을 이용한 삽입정렬
		for(int i = 1; i < data.length; i++) {
			int key = data[i]; // 정렬할 값
			int j;
			// 넣을 위치를 찾으면서 뒤로 민다
			for(j = i-1; j>=0 && data[j] > key; j--) {
				data[j+1] = data[j];
			}
			data[j+1] = key;
		} // 정렬 사이클
		
		System.out.println(Arrays.toString(data));
	}
	
}

---

목표로 한 정렬 학습의 절반 이상이 진행되었다.
박수.