[2017.05.15~2017.05.19] 자료구조 3/5

큐

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트
• 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조(FIFO:선입선출)

이미지 출처 : https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

큐의 연산

• 삽입:enQueue
• 삭제:deQueue

스택과 큐의 연산 비교

	삽입 연산		삭제 연산
	연산자	삽입 위치	연산자	삭제 위치
스택	push	top	pop	top
큐	enQueue	rear	deQueue	front

선형 큐

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

원형 큐

이미지 출처 : 교재

큐의 응용

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

맵(Map)

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

정렬

2개 이상의 자료를 순서대로 재배열 하는 것

키 : 자료를 정렬하는 데 사용하는 기준 값

정렬방법의 분류

• 실행 방법에 따른 분류
• 비교식 정렬 - 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법
• 분산식 정렬 - 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

선택 정렬

-전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

소스 추가할 것 : https://github.com/leeyebin/Java_DataStructure/blob/master/JavaDS/src/day3/SelectionSort.java

버블 정렬

-인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

소스 추가할 것 : https://github.com/leeyebin/Java_DataStructure/blob/master/JavaDS/src/day3/BubbleSort.java

퀵정렬

-정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법

소스 추가할 것 : https://github.com/leeyebin/Java_DataStructure/blob/master/JavaDS/src/day3/QuickSort.java

삽입정렬

정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법

소스 추가할 것 : https://github.com/leeyebin/Java_DataStructure/blob/master/JavaDS/src/day3/InsertionSort.java