썸넬 Img ref :
https://velog.io/@leejuhwan/%EC%8A%A4%ED%83%9DSTACK%EA%B3%BC-%ED%81%90QUEUE
🌱 배열
크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말합니다.
🌿 장/단점
-
장점
- 메모리에 연속적으로 할당되어 있어 어느 위치에서나 O(1)에 조회가 가능(검색 성능 우수)
- 인덱스를 이용하여 무작위 접근 가능(순차 접근을 하지 않아도 됨)
- 순차 접근을 하더라도 연결 리스트보다 빠름
-
단점
- 자료의 삽입이나 삭제 작업에서 데이터 이동이 많아 비효율적임
- 크기가 고정되어 있어 메모리 낭비나 부족 현상이 발생할 가능성이 높음
🌿 동적 배열
동적 배열은 크기가 고정된 배열에서 예상보다 많은 자료가 들어올 경우, 동적으로 크기를 조정할 수 있는 배열의 단점을 보완한 자료형입니다.
📌 동적 배열 자료형
자바의 ArrayList는 동적 배열 자료형입니다. 배열 크기를 임의로 변화시킬 수 있고, 타입을 직접 설정할 수 있습니다. 하지만 배열 크기가 정해진 용량을 다 채우면, 더블링이 발생하여 현재의 2배 크기로 늘리는데 기존 데이터를 모두 복사하여 옮기기 때문에 O(n)의 비용이 발생합니다. 입력 시간이나 검색 시간은 O(1)으로 동일합니다.
🌱 연결 리스트
데이터의 순서가 메모리에 물리적인 순서로 저장되지 않는 자료구조입니다. 모든 노드는 연결 구조이며, 데이터와 다음 노드의 주소로 구성되어 있습니다.
🌿 장/단점
- 장점
- 포인터 작업만 하면 되므로, 새로운 노드를 삽입하거나 삭제하기가 간편
- 빈 공간을 허용하지 않기 때문에 데이터 관리에 편리
- 데이터 개수만큼 메모리를 할당하므로, 메모리 관리가 편리
- 시작 또는 마지막 노드의 삽입/삭제/추출은 O(1)에 가능
- 단점
- 특정 인덱스를 찾기 위해서는 전체 데이터를 순서대로 읽어야하므로, O(n)의 시간이 소요됨(검색 능력 떨어짐)
- 객체로 데이터를 다루기 때문에 적은 양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 큼
🌿 구현
코드package excercise.test;
class ListNode {
private String data; //데이터 저장
public ListNode link; //참조 링크
public ListNode() {
this.data = null;
this.link = null;
}
public ListNode(String data) {
this.data = data;
this.link = null;
}
public ListNode(String data, ListNode link) {
this.data = data;
this.link = link;
}
public String getData() {
return data;
}
}
public class LinkedList {
private ListNode head;
public LinkedList() {
head = null; //head 초기화
}
//Node 삽입(중간에 삽입)
public void insertNode(ListNode preNode, String data) {
ListNode newNode = new ListNode(data); //새로운 노드 생성
//연결 작업
newNode.link = preNode.link;
preNode.link = newNode;
}
//Node 삽입(마지막에 삽입)
public void insertNode(String data) {
ListNode newNode = new ListNode(data); //새로운 노드 생성
if (head == null) { //head가 null인 경우 새로운 노드를 참조하도록 함
this.head = newNode;
} else {
ListNode tempNode = head;
//마지막 노드 탐색
while (tempNode.link != null) {
tempNode = tempNode.link; //다음 노드를 참조
}
tempNode.link = newNode;
}
}
//Node 삭제(중간 노드 삭제)
public void deleteNode(String data) {
ListNode preNode = head;
ListNode tempNode = head.link;
//첫 번째 노드 삭제
if (data.equals(preNode.getData())) {
head = preNode.link; //다음 노드 참조
preNode.link = null; //연결 해제
} else {
while (tempNode != null) {
//타깃 일치
if (data.equals(tempNode.getData())) {
//마지막 노드 삭제
if (tempNode.link == null) {
preNode.link = null;
}
//중간 노드 삭제
else {
//연결 작업
preNode.link = tempNode.link;
tempNode.link = null;
}
break;
}
//타깃 불일치 -> 다음 노드로 이동
else {
preNode = tempNode;
tempNode = tempNode.link;
}
}
}
}
//Node 삭제(마지막 노드 삭제)
public void deleteNode() {
ListNode preNode;
ListNode tempNode;
//모든 노드가 삭제된 상황
if (head == null) {
return;
}
//노드가 1개 남았을 경우
if (head.link == null) {
head = null;
} else {
preNode = head;
tempNode = head.link;
//마지막 노드 탐색
while (tempNode.link != null) {
preNode = tempNode;
tempNode = tempNode.link;
}
preNode.link = null; //마지막 노드 삭제
}
}
//Node 탐색
public ListNode searchNode(String data) {
ListNode tempNode = this.head;
//타깃 탐색
while (tempNode != null) {
//탐색 완료
if (data.equals(tempNode.getData())) {
return tempNode;
} else {
tempNode = tempNode.link; //다음 노드 할당
}
}
return tempNode;
}
//reverse linked list
public void reverseList() {
ListNode nextNode = head; //head 할당
ListNode currentNode = null;
ListNode preNode = null;
//전체 순회
while (nextNode != null) {
//다음 노드로 이동
preNode = currentNode;
currentNode = nextNode;
nextNode = nextNode.link;
currentNode.link = preNode; //현재 노드의 링크 방향을 역방향으로
}
//currentNode가 마지막 노드를 가리킬 때, head로 지정
head = currentNode;
}
//Linked List 출력
public void printList() {
ListNode tempNode = this.head;
//전체 순회
while (tempNode != null) {
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.link; //다음 노드 할당
}
System.out.println();
}
}
package excercise.test;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
@SpringBootApplication
public class TestApplication {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
String str = "wed";
linkedList.insertNode("sun");
linkedList.insertNode("mon");
linkedList.insertNode("tue");
linkedList.insertNode("wed");
linkedList.insertNode("thu");
linkedList.insertNode("fri");
linkedList.insertNode("sat");
linkedList.printList();
System.out.println("linkedList 검색 = " + linkedList.searchNode(str).getData());
linkedList.deleteNode(linkedList.searchNode(str).getData());
linkedList.printList();
str = "sun";
linkedList.deleteNode(linkedList.searchNode(str).getData());
linkedList.printList();
linkedList.reverseList();
linkedList.printList();
// SpringApplication.run(TestApplication.class, args);
}
}
🌱 스택(Stack)
한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 LIFO(Last In First Out) 구조로 동작합니다. 이러한 구조는 보통 '뒤로 가기', '실행 취소(undo)', 'stack memory'에서 쓰입니다.
장점은 후출선입인 만큼 직전의 데이터를 빠르게 갖고 올 수 있다는 것입니다. 또한 균형성 검사를 할 수 있기 때문에 수식, 괄호 등의 검사에서도 쓰입니다.
스택은 ArrayList로도 구현할 수 있으며, '동적 할당'을 전제로 합니다.
🌿 스택 주요 메소드
주요 메소드는 push와 pop입니다. 여기서 중요한 것은 search() 메소드는 스택 내부 배열의 인덱스를 반환하는 것이 아니라 스택의 상단으로부터 몇 번째에 위치하는지를 반환하는 것입니다. 즉, 거리 개념이라고 보면 됩니다.
🌿 구현
📌 Stack Interface
코드package excercise.test.interface_form;
public interface StackInterface<E> {
/**
* 스택의 맨 위에 요소를 추가
*
* @param item 스택에 추가할 요소
* @return 스택의 추가된 요소
* */
E push(E item);
/**
* 스택의 맨 위에 있는 요소를 제거하고 제거된 요소를 반환
*
* @return 제거 된 요소
* */
E pop();
/**
* 스택의 맨 위에 있는 요소를 제거하지 않고 반환
*
* @return 스택의 맨 위에 있는 요소
*/
E peek();
/**
* 스택의 상단으로부터 특정 요소가 몇 번째 위치에 있는지를 반환
* 중복되는 원소가 있을 경우, 가장 위에 있는 요소의 위치가 반환됨
*
* @param value 스택에서 위치를 찾을 요소
* @return 스택의 상단으로부터 처음으로 요소와 일치하는 위치를 반환
* 만약 일치하는 요소가 없을 경우 -1을 반환
*/
/*
* ________
* | a |
* idx 3 |______| search("w")
* | e | --> 상단(idx 3)으로 부터 3번 째에 위치
* idx 2 |______| == return 되는 값 : 3
* | w |
* idx 1 |______|
* | k |
* idx 0 |______|
*
*/
int search(Object value);
/**
* 스택의 요소 개수를 반환
*
* @return 스택에 있는 요소 개수를 반환
* */
int size();
/*
* 스택에 있는 모든 요소를 삭제
* */
void clear();
/**
* 스택에 요소가 비어있는지를 반환
*
* @return 스택에 요소가 없을 경우 {<code>true</code>}, 그 외의 경우 {<code>false</code>} 반환
* */
boolean empty();
}
📌 Stack
코드package excercise.test;
import excercise.test.interface_form.StackInterface;
import java.util.Arrays;
import java.util.EmptyStackException;
public class Stack<E> implements StackInterface<E> {
private static final int DEFAULT_CAPACITY = 10; //최소(기본) 용적 크기
private static final Object[] EMPTY_ARRAY = {}; //빈 배열
private Object[] array; //요소를 담을 배열
private int size; //요소 개수
//생성자1 (초기 공간 할당x)
public Stack() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
//생성자2 (초기 공간 할당o)
public Stack(int capacity) {
this.array = new Object[capacity];
this.size = 0;
}
private void resize() {
//빈 배열일 경우 (capacity is 0)
if (Arrays.equals(array, EMPTY_ARRAY)) {
array = new Object[DEFAULT_CAPACITY];
return;
}
int arrayCapacity = array.length; //현재 용적 크기
//용적이 가득 찰 경우
if (size == arrayCapacity) {
int newSize = arrayCapacity * 2; //더블링(메모리 할당)
//배열 복사
array = Arrays.copyOf(array, newSize);
return;
}
//용적의 절반 미만으로 요소가 차지하고 있을 경우
if (size < (arrayCapacity / 2)) {
int newCapacity = (arrayCapacity / 2); //메모리 절약
//배열 복사
array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, newCapacity)); //최소 용적 크기 이상 유지
return;
}
}
@Override
public E push(E item) {
//용적이 꽉 차 있다면 용적을 재할당
if (size == array.length) {
resize();
}
array[size] = item; //마지막 위치에 요소 추가
size++; //사이즈 1 증가
return item;
}
@Override
public E pop() {
//삭제할 요소가 없다면 Stack이 비어 있다는 의미이므로 예외 발생시킴
if (size == 0) {
throw new EmptyStackException();
}
@SuppressWarnings("unchecked")
E obj = (E) array[size - 1]; //삭제할 요소를 반환하기 위한 임시 변수
array[size - 1] = null; //요소 삭제
size--; //사이즈 1 감소
resize(); //용적 재할당
return obj;
}
@SuppressWarnings("unchecked")
@Override
public E peek() {
//삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시킴
if (size == 0) {
throw new EmptyStackException();
}
return (E) array[size - 1];
}
@Override
public int search(Object value) {
//value가 null일 때는 equals(null)이 되어 NullPointerException 이 발생할 수 있음
//== 로 null 값을 비교
if (value == null) {
for (int idx = size - 1; idx >= 0; idx--) {
//배열 내 null 값 찾음
if (array[idx] == null) {
return size - idx; //Top으로부터 거리
}
}
} else {
for (int idx = size - 1; idx >= 0; idx--) {
//같은 객체를 찾았을 경우 size - idx 값을 반환
if (array[idx].equals(value)) {
return size - idx;
}
}
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
//저장되어있던 모든 요소를 null 처리
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
resize();
}
@Override
public boolean empty() {
return size == 0;
}
}
📌 Stack - 테스트 및 설명
코드Stack<Integer> stack = new Stack<>();
Integer target = 3;
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println("search in stack = " + stack.search(target));
while (stack.size() != 0) {
System.out.println("stack top value : " + stack.peek());
stack.pop();
}
System.out.println("stack.empty() = " + stack.empty());
- DEFAULT_CAPACITY : 배열이 생성될 때의 최초 할당 크기(용적)이자 최소 할당 용적 변수
- EMPTY_ARRAY : 아무 것도 없는 빈 배열 (용적이 0인 배열)
- array : 요소들을 담을 배열
- size : 배열에 담긴 요소(원소)의 개수 변수 (용적 크기가 아님)
생성자
생성자1 : 초기 공간 할당을 하지 않고, 동적으로 용적이 정해짐
생성자2 : 초기 입력된 수 만큼 공간이 할당됨. 미리 데이터의 개수를 예측하고 싶을 때 사용
최적화된 용적의 필요성
만약 데이터는 적은데 용적이 크면 메모리가 낭비되고, 반대로 용적은 적은데 데이터가 많으면 메모리 부족 문제가 발생합니다. 그렇기 때문에 size(요소의 개수)가 용적(capacity)에 얼마 만큼 차 있는지를 확인하고, 적절한 크기에 맞게 배열의 용적을 변경해야 합니다. 또한 용적은 외부에서 마음대로 접근하면 데이터의 손실을 야기할 수 있으므로 private로 제한합니다.
resize 메소드
주소가 아닌 값 비교이므로 Arrays.equals() 사용
배열 복사는 Arrays.copyOf() 메소드를 사용하면 편리하게 복사할 수 있습니다.
Arrays.copyOf() : 만약 복사할 배열보다 용적의 크기가 클 경우 먼저 배열을 복사한 뒤, 나머지 빈 공간은 null로 채워지기 때문에 편리합니다.
@SuppressWarnings("unchecked")
Object -> E 타입 변환에 대한 무점검 경고를 억제합니다. push하여 받아들이는 데이터 타입은 유일하게 E 타입만 존재합니다. 그렇기 때문에 형 안정성이 보장되고, 이런 상황에서 경고를 억제하는 것이 권장됩니다. 단, ClassCastException 예외가 없음이 확실할 때 최소한의 범위에서 써야 합니다. 그렇지 않으면 중요한 경고 메시지를 놓칠 수 있습니다.
- search 메소드 그림 참고
Top으로부터 떨어져있는 거리(단, 1부터 시작)
수식 : size - index
데이터를 찾지 못했을 경우 -1 반환
🌱 큐(Queue)
Queue는 '대기열' 개념으로 이해하면 됩니다. 즉, '선입선출(FIFO)'의 구조를 가진 자료구조입니다. 따라서, 시간 순으로 어떤 작업 또는 데이터를 처리할 필요가 있는 것들은 큐의 성질을 갖고 있다고 보면 됩니다. 또한 대표적으로 알고리즘에서는 BFS(너비 우선 탐색)에 사용됩니다.
큐를 구현하는 클래스는 크게 PriorityQueue(우선순위 큐), ArrayDeque(배열 양방향 큐), LinkedList(연결리스트) 이렇게 3가지가 있습니다.
🌿 큐 주요 메소드
offer()는 리스트의 add(), poll()은 remove(), peek()는 element()와 비슷한 역할입니다.
다만 차이점은 add(), remove(), element()는 내부적으로 예외를 처리하고 있습니다. 예를 들어 index 밖을 넘어가거나, 삭제할 요소가 없는 경우에 대해 예외를 던집니다.
하지만 offer(), poll(), peek()의 경우 예외를 던지는 것이 아닌 특별한 값을 던지는데, 일반적으로 null 또는 false를 던집니다.
🌿 구현
📌 Queue Interface
코드package interface_form;
public interface QueueInterface<E> {
/**
* 큐의 가장 마지막에 요소를 추가
*
* @param e 큐에 추가할 요소
* @return 큐에 요소가 정상적으로 추가되었을 경우 true 반환
*/
boolean offer(E e);
/**
* 큐의 첫 번째 요소를 삭제하고 삭제된 요소를 반환
*
* @return 큐의 삭제된 요소 반환
* */
E poll();
/**
* 큐의 첫 번째 요소를 반환
*
* @return 큐의 첫 번째 요소 반환
* */
E peek();
}
📌 Queue(using array)
-문제점
배열에서 offer(), poll()을 수행하다보면 index가 뒷쪽으로 쏠리는 현상이 발생합니다. 이것을 해결하기 위해 원형 큐(Circular Queue)가 사용됩니다.
front와 rear 포인터를 두고, 순환하면서 데이터를 넣고 빼는 작업을 하는 것입니다. 따라서, 데이터를 넣을 때는 rear+1 위치에 넣고, 마지막 index 다음 위치를 0으로 셋팅해야 합니다.
만약에 더 이상 빈 자리가 없을 경우에만 배열의 크기를 늘려주면 됩니다.
반대로 원소를 삭제할 경우, front를 움직여서 front+1번째 원소를 삭제합니다.
(삭제는 front를 따르고, 삽입은 rear를 따름)
또한, front 를 비어둬야 하는데 이것은 모든 원소가 삭제되었을 때, front와 rear가 같은 위치에 있게 되어 큐의 empty 확인에 용이합니다.
마찬가지로 해당 자료구조는 '동적 할당'을 전제로 합니다.
코드package queue.array;
import interface_form.QueueInterface;
public class ArrayQueue<E> implements QueueInterface<E> {
private static final int DEFAULT_CAPACITY = 64; //최소(기본) 용적 크기
private Object[] array; //요소를 담을 배열
private int size; //요소 개수
private int front; //시작 인덱스(빈 공간)
private int rear; //마지막 인덱스
//생성자1(초기 용적 할당을 안할 경우)
public ArrayQueue() {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.front = 0;
this.rear = 0;
}
//생성자2(초기 용적 할당을 할 경우)
public ArrayQueue(int capacity) {
this.array = new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = 0;
}
private void resize(int newCapacity) {
int arrayCapacity = array.length; //현재 용적 크기
Object[] newArray = new Object[newCapacity]; //용적을 변경한 배열
/*
* i = new array index
* j = original array
* index 요소 개수(size)만큼 새 배열에 값 복사
* */
for (int i = 1, j = front + 1; i <= size; i++, j++) {
newArray[i] = array[j % arrayCapacity];
}
this.array = null;
this.array = newArray; //새 배열을 기존 arry의 배열로 덮어씌움
front=0;
rear = size;
}
@Override
public boolean offer(E item) {
//용적이 가득 찼을 경우
if ((rear + 1) % array.length == front) {
resize(array.length * 2); //용적 더블링
}
rear = (rear + 1) % array.length; //rear을 rear의 다음 위치로 갱신
array[rear] = item;
size++; //사이즈 1 증가
return true;
}
@Override
public E poll() {
//삭제할 요소가 없을 경우
if (size == 0) {
return null;
}
front = (front + 1) % array.length; //front를 한 칸 옮김
@SuppressWarnings("unchecked")
E item = (E) array[front]; //반환할 데이터를 임시 저장
array[front] = null; //front 위치 데이터 삭제
size--; //사이즈 1 감소
//용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if (array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
//아무리 작아도 최소 용적 미만으로 줄이지는 않도록 함
resize(Math.max(DEFAULT_CAPACITY, array.length) / 2);
}
return item;
}
@Override
public E peek() {
//삭제할 요소가 없을 경우
if (size == 0) {
return null;
}
@SuppressWarnings("unchecked")
E item = (E) array[(front + 1) % array.length];
return item;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
int start = (front + 1) % array.length;
/*
* i : 요소 개수 만큼만 반복(전체 이동)
* idx : 원소 위치로, 매회 (idx + 1) % array.length 위치로 갱신(데이터 내 이동)
*
* 전체 순회하면서 데이터 방 중에서 value 찾기 -> 효율적
* */
for (int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
if (array[idx].equals(value)) {
return true;
}
}
return false;
}
public void clear() {
for (int i = 0; i < array.length; i++) {
array[i] = null;
}
front = rear = size = 0;
}
public void toQueue() {
for (int i = 0, idx = (front + 1) % array.length; i < size; i++, idx = (idx + 1) % array.length) {
System.out.println("array[idx] = " + array[idx]);
}
}
}
생성자
생성자1 : 초기 공간 할당을 하지 않고, 동적으로 용적이 정해짐
생성자2 : 초기 입력된 수 만큼 공간이 할당됨. 미리 데이터의 개수를 예측하고 싶을 때 사용
resize()
원형 큐를 사용하므로, 용적을 증가해야 하는 경우와 줄여야 하는 경우를 굳이 나눌 필요가 없습니다.
큐가 가득 찬 상황 : (rear + 1) % arrayCapacity == front
용적을 증가시킬 때는 for문 로직으로 처리하고, 용적을 감소시킬 때는 호출 위치에서 size < (arrayCapacity/4) 조건을 걸고 newCapacity 매개변수를 전달하여 조정된 새 배열을 만들고 값을 채웁니다.
📌 ArrayQueue Test
코드package queue.array;
public class ArrayQueueApplication {
public static void main(String[] args) {
ArrayQueue<Student> q = new ArrayQueue<Student>();
Student s = new Student("조지아", 93);
q.offer(new Student("티오피", 88));
q.offer(s);
q.offer(new Student("스벅", 72));
q.offer(new Student("파스쿠치", 66));
q.toQueue();
System.out.println();
System.out.println("q.peek() = " + q.peek());
System.out.println("q.poll() = " + q.poll());
System.out.println();
q.toQueue();
System.out.println();
System.out.println("q.size() = " + q.size());
System.out.println("조지아 탐색 = " + q.contains(s));
System.out.println("q.isEmpty() = " + q.isEmpty());
}
}
class Student {
String name;
int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", score=" + score +
'}';
}
}
🌿 Linked Queue(LinkedList-Queue) 구현
큐를 연결 리스트로 구현할 경우, 각 데이터들을 노드 객체에 담고 노드 간 서로 연결해주기 때문에 배열처럼 요소 개수에 따라 늘려주거나 줄여줄 필요도 없고 삽입, 삭제 때는 연결된 링크만 끊거나 이어주면 되기 때문에 관리면에서도 편합니다.
📌 LinkedListQueue
- Node : 연결 리스트 구성 노드
- Interface : QueueInterface 동일
package queue.linkedList;
public class Node<E> {
E data;
Node<E> next; //다음 노드를 가리키는 변수
public Node(E data) {
this.data = data;
this.next = null;
}
}
package queue.linkedList;
import interface_form.QueueInterface;
public class LinkedListQueue<E> implements QueueInterface<E> {
private Node<E> head; //가장 앞 노드
private Node<E> tail; //가장 뒷 노드
private int size; //큐 요소 개수
public LinkedListQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<>(value);
//비어있을 경우
if (size == 0) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode; //tail 대상 노드 변경
size++;
return true;
}
@Override
public E poll() {
//삭제할 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
//삭제될 요소 임시 보관
E elem = head.data;
Node<E> nextNode = head.next;
//head의 모든 데이터 삭제
head.data = null;
head.next = null;
//head = head.next
head = nextNode;
size--;
return elem;
}
@Override
public E peek() {
//삭제할 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
return head.data;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
for (Node<E> e = head; e != null; e = e.next) {
if (value.equals(e.data)) {
return true;
}
}
return false;
}
public void clear() {
for (Node<E> e = head; e != null;) {
Node<E> next = e.next;
e.data = null;
e.next = null;
e = next;
}
size = 0;
head = tail = null;
}
}
📌 LinkedListQueue Test
코드package queue.linkedList;
public class LinkedListQueueApplication {
public static void main(String[] args) {
LinkedListQueue<Character> q = new LinkedListQueue<Character>();
Character c = new Character("army_one", "A");
q.offer(new Character("army_two", "B"));
q.offer(c);
q.offer(new Character("army_three", "C"));
q.offer(new Character("army_four", "D"));
q.toQueue();
System.out.println();
System.out.println("q.peek() = " + q.peek());
System.out.println("q.poll() = " + q.poll());
System.out.println();
q.toQueue();
System.out.println();
System.out.println("q.size() = " + q.size());
System.out.println("q.contains(c) = " + q.contains(c));
System.out.println(">>>Clear Queue");
q.clear();
System.out.println("q.isEmpty() = " + q.isEmpty());
}
}
class Character {
String name;
String grade;
public Character(String name, String grade) {
this.name = name;
this.grade = grade;
}
@Override
public String toString() {
return "Character{" +
"name='" + name + '\'' +
", grade='" + grade + '\'' +
'}';
}
}
🌱 데크(Deque)
Deque는 양방향 연결 리스트(Doubly LinkedList)와 유사한 메커니즘입니다. 데크는 양 쪽 방향에서 삽입 삭제가 이루어진다는 의미로 double-ended queue의 줄임말입니다. 또한, offer()와 pollLast를 조합하면 스택으로도 사용할 수 있습니다.
🌿 데크 주요 메소드
🌿 구현
📌 Deque(using array)
- Interface : QueueInterface 동일
- offer(E) : offerLast(offer), offerFirst
- poll() : pollFirst(poll), pollLast
- peek() : peekFirst(peek), peekLast
package deque.array;
import interface_form.QueueInterface;
import java.util.Arrays;
public class ArrayDeque<E> implements QueueInterface<E> {
private static final int DEFAULT_CAPACITY = 64; //최소(기본) 용적 크기
private Object[] array; //요소를 담을 배열
private int size; //요소 개수
private int front; //start index (빈 공간)
private int rear; //last index
//생성자1 (초기 용적 할당을 안할 경우)
public ArrayDeque() {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.front = 0;
this.rear = 0;
}
//생성자2 (초기 용적 할당을 할 경우)
public ArrayDeque(int capacity) {
this.array = new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = 0;
}
private void resize(int newCapacity) {
int arrayCapacity = array.length; //현재 용적 크기
Object[] newArray = new Object[newCapacity]; //용적을 변경한 배열
/*
* i = new array index
* j = original array
* index 요소 개수(size) 만큼 새 배열에 값 복사
* */
for (int i = 1, j = front + 1; i <= size; i++, j++) {
newArray[i] = array[j % arrayCapacity];
}
this.array = null;
this.array = newArray; //새 배열 -> 기존 배열
front = 0;
rear = size;
}
@Override
public boolean offer(E item) {
return offerLast(item);
}
public boolean offerLast(E item) {
//용적이 가득 찼을 경우
if ((rear + 1) % array.length == front) {
resize(array.length * 2); //용적 더블링
}
rear = (rear + 1) % array.length; //rear 다음 위치로
array[rear] = item;
size++;
return true;
}
public boolean offerFirst(E item) {
//용적이 가득 찼을 경우
if ((front - 1 + array.length) % array.length == rear) {
resize(array.length * 2); //용적 더블링
}
array[front] = item;
front = ((front - 1) + array.length) % array.length; //front 전방 이동
size++;
return true;
}
@Override
public E poll() {
return pollFirst();
}
public E pollFirst() {
//삭제할 요소가 없을 경우
if (size == 0) {
return null;
}
front = (front + 1) % array.length; //front 다음 칸 이동
@SuppressWarnings("unchecked")
E item = (E) array[front]; //반환 데이터 임시 저장
array[front] = null; //데이터 삭제
size--;
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if (array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
//용적 조정 (하한선 = DEFAULT_CAPACITY)
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;
}
public E pollLast() {
//삭제할 요소가 없을 경우
if (size == 0) {
return null;
}
@SuppressWarnings("unchecked")
E item = (E) array[rear]; //반환 데이터 임시 저장
array[rear] = null; //데이터 삭제
rear = (rear - 1 + array.length) % array.length; //rear 전방 이동
size--;
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if (array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
//용적 조정 (하한선 = DEFAULT_CAPACITY)
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;
}
@Override
public E peek() {
return peekFirst();
}
public E peekFirst() {
//요소가 없을 경우
if (size == 0) {
return null;
}
@SuppressWarnings("unchecked")
E item = (E) array[(front + 1) % array.length];
return item;
}
public E peekLast() {
//요소가 없을 경우
if (size == 0) {
return null;
}
@SuppressWarnings("unchecked")
E item = (E) array[rear];
return item;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
int start = (front + 1) % array.length;
/*
* i : 요소 개수 만큼만 반복
* idx : 데이터 범위 내 반복
* */
for (int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
if (array[idx].equals(value)) {
return true;
}
}
return false;
}
public void clear() {
Arrays.fill(array, null);
front = rear = size = 0;
}
public void toDeque() {
int start = (front + 1) % array.length;
for (int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
System.out.println("array[idx] = " + array[idx]);
}
}
}
📌 ArrayDeque - 테스트 및 설명
코드package deque.array;
public class ArrayDequeApplication {
public static void main(String[] args) {
ArrayDeque<Coffee> deque = new ArrayDeque<>();
Coffee c = new Coffee("연유라떼", 4000);
deque.offer(new Coffee("콜롬비아", 4000));
deque.offer(new Coffee("아메리카노", 2000));
deque.offer(c);
deque.offerFirst(new Coffee("솔트라떼", 4500));
deque.toDeque();
System.out.println();
System.out.println("Do you have a 연유라떼? = " + deque.contains(c));
System.out.println();
System.out.println("deque.peek() = " + deque.peek());
System.out.println("deque.peekLast() = " + deque.peekLast());
System.out.println();
System.out.println("deque.poll() = " + deque.poll());
System.out.println("deque.pollLast() = " + deque.pollLast());
System.out.println();
deque.toDeque();
System.out.println();
System.out.println("deque.size() = " + deque.size());
System.out.println();
System.out.println("deque.poll() = " + deque.poll());
System.out.println("deque.pollLast() = " + deque.pollLast());
System.out.println();
System.out.println("deque.isEmpty() = " + deque.isEmpty());
}
}
class Coffee {
String name;
int price;
public Coffee(String name, int price) {
this.name = name;
this.price = price;
}
@Override
public String toString() {
return "Coffee{" +
"name='" + name + '\'' +
", price=" + price +
'}';
}
}
생성자
생성자1 : 초기 공간 할당을 하지 않고, 동적으로 용적이 정해짐
생성자2 : 초기 입력된 수 만큼 공간이 할당됨. 미리 데이터의 개수를 예측하고 싶을 때 사용
resize()
원형 큐를 사용하므로, 용적을 증가해야 하는 경우와 줄여야 하는 경우를 굳이 나눌 필요가 없습니다.
큐가 가득 찬 상황 : (rear + 1) % arrayCapacity == front
용적을 증가시킬 때는 for문 로직으로 처리하고, 용적을 감소시킬 때는 호출 위치에서 size < (arrayCapacity/4) 조건을 걸고 newCapacity 매개변수를 전달하여 조정된 새 배열을 만들고 값을 채웁니다.
offerFirst(item)
front를 앞으로 이동하기 때문에 음수를 고려해야 합니다. 따라서, 용적 크기 만큼 더해준 뒤 % 연산을 해야 합니다.
pollLast()
rear를 앞으로 이동하기 때문에 음수를 고려해야 합니다. 따라서, 용적 크기 만큼 더해준 뒤 % 연산을 해야 합니다.
📌 LinkedListDeque
데크는 양뱡향 접근이 가능해야 하기 때문에 이중 연결 리스트의 노드를 사용해야 합니다.
📌 Node
package deque.linkedList;
public class Node<E> {
E data; //데이터를 담을 변수
Node<E> next; //다음 노드 참조
Node<E> prev; //이전 노드 참조
public Node(E data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
📌 LinkedListDeque 구현
- Interface : QueueInterface 동일
- offer(E) : offerLast(offer), offerFirst
- poll() : pollFirst(poll), pollLast
- peek() : peekFirst(peek), peekLast
package deque.linkedList;
import interface_form.QueueInterface;
public class LinkedListDeque<E> implements QueueInterface<E> {
private Node<E> head; //가장 앞에 있는 노드를 가리키는 변수
private Node<E> tail; //가장 뒤에 있는 노드를 가리키는 변수
private int size; //요소(노드) 개수
public LinkedListDeque() {
head = null;
tail = null;
size = 0;
}
@Override
public boolean offer(E value) {
return offerLast(value);
}
public boolean offerLast(E value) {
//데이터가 없을 경우
if (size == 0) {
return offerFirst(value);
}
Node<E> newNode = new Node<>(value);
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
size++;
return true;
}
public boolean offerFirst(E value) {
Node<E> newNode = new Node<>(value);
newNode.next = head;
/*
* head가 null이 아닐 경우에만 기존 head 노드의 prev 변수가
* 새 노드를 가리키도록 함
* 기존 head 노드가 null인 경우, 데이터가 아무 것도 없는 상태이므로,
* head.prev를 하면 잘못된 참조가 됨
* */
if (head != null) {
head.prev = newNode;
}
head = newNode; //head가 새 노드를 가리키도록 함
size++;
/*
* 다음에 가리킬 노드가 없는 경우(데이터가 새 노드밖에 없는 경우 == 이전 head가 null인 경우)
* 데이터가 한 개(새 노드)밖에 없으므로 새 노드는 처음 시작 노드이자 마지막 노드
* tail == head
* */
if (head.next == null) {
tail = head;
}
return true;
}
@Override
public E poll() {
return pollFirst();
}
public E pollFirst() {
//삭제할 데이터가 없는 경우
if (size == 0) {
return null;
}
E elem = head.data; //반환 데이터
Node<E> nextNode = head.next;
//삭제 처리
head.data = null;
head.next = null;
//head 다음 노드가 있을 경우(새로운 head가 되므로 prev는 null)
if (nextNode != null) {
nextNode.prev = null;
}
head = null;
head = nextNode; //head 갱신
size--;
/*
* 삭제된 요소가 Deque의 유일한 요소였을 경우
* 그 요소는 head이자 tail
* 삭제되면서 tail도 가리킬 요소가 없기 때문에
* size가 0일 경우, tail도 null 처리
* */
if (size == 0) {
tail = null;
}
return elem;
}
public E pollLast() {
//데이터가 없을 경우
if (size == 0) {
return null;
}
E elem = tail.data; //반환 데이터
Node<E> prevNode = tail.prev;
//삭제 처리
tail.data = null;
tail.prev = null;
//tail 앞에 노드가 있을 경우(새로운 tail이 되므로 next를 null 처리)
if (prevNode != null) {
prevNode.next = null;
}
tail = null;
tail = prevNode; //tail 갱신
size--;
/*
* 삭제된 요소가 Deque의 유일한 요소였을 경우
* 그 요소는 head이자 tail
* 삭제되면서 head도 가리킬 요소가 없기 때문에
* size가 0일 경우, head도 null 처리
* */
if (size == 0) {
head = null;
}
return elem;
}
@Override
public E peek() {
return peekFirst();
}
public E peekFirst() {
//데이터가 없을 경우
if (size == 0) {
return null;
}
return head.data;
}
public E peekLast() {
//데이터가 없을 경우
if (size == 0) {
return null;
}
return tail.data;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
for (Node<E> e = head; e != null; e = e.next) {
if (value.equals(value)) {
return true;
}
}
return false;
}
public void clear() {
for (Node<E> e = head; e != null;) {
Node<E> next = e.next;
e.data = null;
e.next = null;
e.prev = null;
e = next;
}
size = 0;
head = tail = null;
}
public void toDeque() {
for (Node<E> e = head; e != null; e = e.next) {
System.out.println("e.data = " + e.data);
}
}
}
offerFirst
offer(offerLast)
poll(pollFirst)
pollLast
🌱 우선순위 큐
대체적으로 Heap 자료구조를 기반으로 구현됩니다. 그리고 힙은 연결리스트처럼 구현하거나 배열을 활용하여 구현할 수 있는데, 힙 특성상 배열을 이용하는 것이 훨씬 구현하기에도 편리합니다.
각 요소들이 각각의 우선순위를 갖고 있고, 요소들의 대기열에서 '우선순위가 높은 요소'가 '우선순위가 낮은 요소'보다 먼저 제공되는 자료구조입니다.
엄연히 따지자면 힙과 우선순위 큐의 개념은 다릅니다. 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'입니다. 반면, 우선순위 큐는 우선순위가 높은 순서대로 요소를 제공받습니다.
우선순위 큐는 '추상적 모델' 개념에 좀 더 가깝고, 이를 구현하는 방식은 여러 방식이 있습니다. 그리고 우선순위 큐를 구현하는 데 있어 가장 대표적인 방식이 'Heap' 자료구조를 활용하는 것입니다.
🌿 구현
코드package priorityQueue;
import interface_form.QueueInterface;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class PriorityQueue<E> implements QueueInterface<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10; //최소(기본) 용적 크기
private int size; //요소 개수
private Object[] array; //요소를 담을 배열
//생성자1 (초기 공간 할당x)
public PriorityQueue() {
this(null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
//생성자2 (초기 공간 할당o)
public PriorityQueue(int capacity) {
this(capacity, null);
}
public PriorityQueue(int capacity, Comparator<? super E> comparator) {
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
//받은 인덱스의 부모 노드 인덱스를 반환
private int getParent(int index) {
return index / 2;
}
//받은 인덱스의 왼쪽 자식 노드 인덱스를 반환
private int getLeftChild(int index) {
return index * 2;
}
//받은 인덱스의 오른쪽 자식 노드 인덱스를 반환
private int getRightChild(int index) {
return index * 2 + 1;
}
/**
* @param newCapacity 새로운 용적 크기
*/
private void resize(int newCapacity) {
//새로 만들 배열
Object[] newArray = new Object[newCapacity];
//새 배열에 기존에 있던 배열의 요소들을 모두 복사
for (int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
/*
* 현재 배열은 GC 처리를 위해 null로 처리
* 새 배열을 array에 연결
* */
this.array = null;
this.array = newArray;
}
@Override
public boolean offer(E value) {
//배열 용적 Fulled -> Doubling
if (size + 1 == array.length) {
resize(array.length * 2);
}
siftUp(size + 1, value); //idx : 추가 위치, value : 추가되는 값
size++;
return true;
}
/*
* 상향 선별
*
* @param idx 추가할 노드의 인덱스
* @param target 재배치할 노드
* */
private void siftUp(int idx, E target) {
if (comparator != null) {
siftUpComparator(idx, target, comparator);
} else {
siftUpComparable(idx, target);
}
}
/**
* Comparator을 이용한 sift-up
*
* @param : 외부로부터 로직 주입
*/
@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
while (idx > 1) {
int parent = getParent(idx); //삽입할 노드의 부모 index
Object parentVal = array[parent]; //삽입할 노드의 부모 값
//삽입 노드 우선순위(값)이 부모보다 크면 종료
if (comp.compare(target, (E) parentVal) >= 0) {
break;
}
/*
* 부모 노드가 타깃 노드보다 우선순위가 크므로
* 현재 삽입될 위치에 부모노드 값으로 교체
* 타깃 노드의 위치를 부모의 위치로 변경
* */
array[idx] = parentVal;
idx = parent;
}
//최종적으로 삽입 될 위치에 타깃 노드 요소 저장
array[idx] = target;
}
/**
* Comparable을 이용한 sift-up
*
* @param : 외부로부터 로직 주입x(Comparable 클래스 내부에서 처리)
*/
@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {
//Comparable 시그니처는 매개변수가 1개이므로, target을 comp로 만듦
Comparable<? super E> comp = (Comparable<? super E>) target;
while (idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if (comp.compareTo((E) parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = comp;
}
@Override
public E poll() {
//root가 null인 경우
if (array[1] == null) {
return null;
}
return remove();
}
@SuppressWarnings("unchecked")
public E remove() {
//root가 null인 경우
if (array[1] == null) {
throw new NoSuchElementException();
}
E result = (E) array[1]; //삭제된 요소 임시 저장
E target = (E) array[size]; //재배치할 요소
array[size] = null; //타겟 노드를 비움
size--;
siftDown(1, target); //루트 노드가 삭제되므로 1을 넘김
return result;
}
/**
* 하향 선별
*
* @param idx 삭제할 노드의 인덱스
* @param target 재배치할 노드
* */
private void siftDown(int idx, E target) {
if (comparator != null) {
siftDownComparator(idx, target, comparator);
} else {
siftDownComparable(idx, target);
}
}
/**
* Comparator을 이용한 sift-down
*
* @param : 외부로부터 로직 주입
*/
@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
array[idx] = null; //노드 삭제
int parent = idx; //삭제 노드의 위치 = 재배치가 시작되는 인덱스
int child; //교환될 자식 인덱스
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을 때까지 반복
while ((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent); //오른쪽 자식 노드 인덱스
Object childVal = array[child];//왼쪽 자식 노드 값
/*
* 왼쪽 자식이 오른쪽 자식보다 큰 경우
* 왼쪽 자식으로 비교를 할 것이므로 오른쪽 자식으로 교체
* */
if (right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
child = right;
childVal = array[child];
}
//재배치할 노드가 자식 노드보다 작을 경우 반복문 종료
if (comp.compare(target, (E) childVal) <= 0) {
break;
}
/*
* 재배치할 노드가 자식 노드보다 큰 경우
* 부모와 자식 노드 스왑
* */
array[parent] = childVal;
parent = child;
}
//최종적으로 재배치되는 위치에 타겟 값을 넣음
array[parent] = target;
/*
* 요소의 개수가 전체 1/4 미만이 된 경우
* 용적 절반 감소시킴(단, Baseline = 최소 용적)
* */
if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length) / 2);
}
}
/**
* Comparable을 이용한 sift-down
*
* @param : 외부로부터 로직 주입x(Comparable 클래스 내부에서 처리)
*/
@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
//Comparable 시그니처는 매개변수가 1개이므로, target을 comp로 만듦
Comparable<? super E> comp = (Comparable<? super E>) target;
array[idx] = null;
int parent = idx;
int child;
//parent << 1 : parent * 2^1
while ((child = (parent << 1)) <= size) {
int right = child + 1;
Object c = array[child];
if (right <= size && ((Comparable<? super E>) c).compareTo((E) array[right]) > 0) {
child = right;
c = array[child];
}
if (comp.compareTo((E) c) <= 0) {
break;
}
array[parent] = c;
parent = child;
}
array[parent] = comp;
if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
@Override
@SuppressWarnings("unchecked")
public E peek() {
//root 요소가 null
if (array[1] == null) {
throw new NoSuchElementException();
}
return (E) array[1];
}
public int size() {
return this.size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
for (int i = 1; i <= size; i++) {
if (array[i].equals(value)) {
return true;
}
}
return false;
}
public void clear() {
Arrays.fill(array, null);
size = 0;
}
public Object[] toArray() {
return toArray(new Object[size]);
}
public <T> T[] toArray(T[] a) {
//a 배열(붙여넣을 배열)이 size보다 작은 경우 -> 요소 전체 복사
if (a.length <= size) {
return (T[]) Arrays.copyOfRange(array, 1, size + 1, a.getClass());
}
System.arraycopy(array, 1, a, 0, size);
return a;
}
}
우선순위 큐의 삽입
- 사용자가 Comparator을 사용하여 정렬 방법을 PriorityQueue 생성단계에서 넘겨받은 경우(comparator가 null이 아닌 경우)
- 클래스 내에 정렬 방식을 Comparable로 구현했거나 기본 정렬 방식을 따르는 경우(comparator가 null인 경우)
toArray 메소드
큐를 반환하기 위한 메소드로 크게 2가지로 나뉩니다.
1. 아무런 인자 없이 현재 있는 큐의 요소들을 Object 배열로 반환(size만큼)
2. 큐를 이미 생성된 다른 배열에 복사(직접 크기 지정)PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // get priorityQueue to array (using toArray()) Object[] q1 = priorityQueue.toArray(); // get priorityQueue to array (using toArray(T[] a) Integer[] q2 = new Integer[10]; q2 = priorityQueue.toArray(q2);1번은 우선순위 큐에 들어 있는 요소 개수만큼만 배열이 할당되어 반환되고, 2번은 객체 클래스로 상속 관계에 있는 타입이거나 Wrapper(Integer -> int) 같이 데이터 타입을 유연하게 캐스팅할 여지가 있습니다. 또한, 새로 담을 배열에 데이터가 있더라도 큐의 데이터가 0번 인덱스부터 복사되고, 그 외의 원소는 기존 배열에 초기화되어있던 그대로 남습니다.
T[] toArray(T[] a) 메소드는 제네릭 메소드로, E 타입과 차이점은 상위 타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭 메소드로 구성한 것입니다.
그리고 중요한 점은 기본적으로 toArray(T[] a) 에서 a로 들어오는 파라미터 배열의 길이가 우선순위 큐에 들어있는 요소 개수보다 작은 경우 요소 개수를 모두 복사할 수 있도록 고려해야 합니다. 그렇지 않으면 일부 요소는 복사되지 않습니다.
a : 새로 담을 배열, array : 우선순위 큐, size : 요소 개수
Arrays.copyOfRange(src, srcPos, destPos, type)
src 배열의 src 인덱스부터 dest-1 인덱스까지 데이터를 type 형태 데이터로 새 배열로 복사
System.arraycopy(src, srcPos, dest, destPos, length)
src 배열의 srcPos 인덱스부터 length만큼의 데이터를 dest 배열의 destPost부터 복사한 데이터를 삽입
🌿 테스트
코드package priorityQueue;
import java.util.Comparator;
import java.util.Random;
public class PriorityQueueApplication {
public static void main(String[] args) {
PriorityQueue<Student> pq1 = new PriorityQueue<>();
PriorityQueue<Student> pq2 = new PriorityQueue<>(comp);
Random rnd = new Random();
char name = 'A';
for (int i = 0; i < 10; i++) {
int math = rnd.nextInt(10);
int science = rnd.nextInt(10);
pq1.offer(new Student(name, math, science));
pq2.offer(new Student(name, math, science));
name++;
}
System.out.println("[pq1 내부 배열 상태]");
for (Object val : pq1.toArray()) {
System.out.print(val);
}
System.out.println();
System.out.println();
System.out.println("[pq2 내부 배열 상태]");
Object[] q = new Object[15];
for (Object val : pq2.toArray(q)) {
System.out.print(val);
}
System.out.println();
System.out.println();
System.out.println("[수학-과학-이름순 뽑기]");
System.out.println("name\tmath\tscience");
while (!pq1.isEmpty()) {
System.out.print(pq1.poll());
}
System.out.println();
System.out.println("[과학-수학-이름순 뽑기]");
System.out.println("name\tmath\tscience");
while (!pq2.isEmpty()) {
System.out.print(pq2.poll());
}
}
private static Comparator<Student> comp = new Comparator<Student>() {
/*
* 과학 점수가 높은 순
* 과학 점수가 같을 경우 수학 점수가 높은 순
* 둘 다 같을 경우 이름 순
* */
@Override
public int compare(Student o1, Student o2) {
if (o1.science == o2.science) {
if (o1.math == o2.math) {
return o1.name - o2.name; //이름 오름차순
}
return o2.math - o1.math; //수학 내림차순
}
return o2.science - o1.science; //과학 내림차순
}
};
static class Student implements Comparable<Student> {
char name;
int math;
int science;
public Student(char name, int math, int science) {
this.name = name;
this.math = math;
this.science = science;
}
/*
* 수학점수가 높은 순
* 수학점수가 같을 경우 과학 점수가 높은 순
* 둘 다 같은 경우 이름순
* */
@Override
public int compareTo(Student o) {
if (this.math == o.math) {
if (this.science == o.science) {
return this.name - o.name; //이름 오름차순
}
return o.science - this.science; //과학 내림차순
}
return o.math - this.math; //수학 내림차순
}
@Override
public String toString() {
return name + "\t" + math + "\t" + science + "\n";
}
}
}
🌱 해시 테이블
🌿 Hash란
임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환(매핑)하는 것입니다. 그리고 이러한 기능을 하는 함수를 해시 함수라고 합니다.
16진수는 4bit당 한 묶음이므로 16진수로 32bit를 표현하면 8개의 문자를 얻게 됩니다. 즉, 해시함수를 돌리기 전 문자열의 길이가 얼마든 일정한 길이를 얻는다는 것입니다. 이러한 과정을 '해싱(hashing)'한다고 하며, 해시함수에 의해 얻어진 값을 보통 다이제스트(digest)라고 합니다.
🌿 Hash를 사용하는 이유
해시를 사용하면 특정 값을 찾기 위해 배열 혹은 노드를 순회할 필요가 없습니다. 그 이유는 동일한 메시지(값)에 대해서 동일한 다이제스트를 갖기 때문입니다. 즉, 동일한 해시 알고리즘을 사용하는 경우 동일한 값에 대하여 동일한 다이제스트를 얻게 된다는 것입니다.
특정 값에 대한 다이제스트는 변하지 않기 때문에 이 다이제스트의 값을 배열의 위치(index)로 활용하는 것입니다.
Set은 중복 원소를 허용하지 않습니다. 이 말은 중복되는 원소인지 아닌지를 검사해야 한다는 것입니다. 그럴 때마다 모든 원소를 검사하는 것은 매우 비효율적입니다. 그래서 고안한 방법이 Hash 함수를 통해 특정 값에 대한 고유의 다이제스트를 얻고 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만 검사하면 되는 것입니다.
🌿 HashCode()
자바에서는 hashCode() 라는 매우 간편한 함수가 있어 이를 통해 hash 값을 얻을 수 있습니다. hashCode()는 객체의 주소 값을 이용하여 해시 알고리즘에 의해 생성된 고유의 정수 값을 반환합니다. 즉, 객체가 같은 메모리 주소를 가리키고 있다면 같은 정수 값을 얻을 것입니다.
객체가 같은 내용을 지니더라도 가리키는 주소가 다르면 다른 값을 지닙니다. 그래서 우리가 쓰는 String, int, double 등의 자료형들은 hashCode()를 override하여 객체 내용이 비교될 수 있도록 재정의를 하고 있습니다. 그렇기 때문에 기본적으로 HashSet을 쓸 때 기본 자료형으로는 같은 내용일 경우 동일한 값을 갖습니다. 만약에 사용자 클래스를 사용하게 될 경우 해당 클래스 내에 hashCode 메소드를 override를 해주지 않으면 메모리 주소를 기반으로 해싱된 값이 나오기 때문에 객체 내용을 비교해주기 위해서는 반드시 hashCode()를 오버라이드 해주어야 합니다.
🌿 해시 충돌
hashCode()를 사용하더라도 1차적인 문제점이 있습니다. 일단 int형의 범위입니다. int형은 32bit로 표현되는 자료형이므로, 2^32(약 42억) 경우의 수를 가질 수 있습니다. 하지만, 우리가 생성 가능한 경우의 수를 훨씬 많을 것입니다. 2^32로 모든 객체를 다 표현(대응)할 수 없다는 한계가 있는 것입니다. 위와 같이 서로 다른 문자열임에도 해싱된 값이 같은 경우를 해시 충돌이라고 합니다.
설령 생성되는 객체가 우연하게 모두가 2^32로 표현 가능하더라도 그 만큼의 버킷(배열) 공간을 생성해야 한다는 것입니다. 이는 메모리 낭비가 심할 뿐더러 Java에서는 대략 단일 배열에 대해 약 21억 크기까지만 생성이 가능합니다.
(2^32 만큼의 버킷 공간 생성이 불가)
그렇기 때문에 메모리의 낭비를 줄이기 위해 배열의 사이즈를 줄여서 사용합니다. 예를 들어 M개의 index를 갖고 있는 배열(테이블)이 있을 때 다음과 같이 index를 지정합니다.
int index = X.hashCode() % M;이 때, 자바에서는 hashCode()가 음수 값이 나올 수도 있습니다. 그렇기 때문에 hashCode()를 사용하는 경우 절댓값으로 변환하여 양수로 변환해주는 것이 필요합니다.
int index = Math.abs(X.hashCode()) % M;📌 해결 방법
위와 같이 해주어도 해시 충돌의 경우와 버킷(배열)의 크기에 따른 같은 index를 참조하는 일이 발생할 수 밖에 없습니다. 이를 해결하는 방법은 크게 두 가지로 나뉩니다.
📌 Open Addressing
[장점]
- 해시 충돌이 일어날 가능성이 적기 때문에 데이터의 개수가 작을수록 속도가 빨라짐
- 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋아짐
- 외부 저장 공간 없이 해시 테이블 내에서 데이터 저장 및 처리 가능
[단점]
- 해시 충돌이 발생하면 해당 객체의 인덱스 값이 바뀜
- 부하율(load factor) 즉, 테이블에 저장된 데이터의 개수가 많아질수록(=밀도가 높아질수록) 성능이 급격히 저하됨
- 2차 충돌 가능성이 있음
- 해시 함수의 성능이 전체 해시 테이블의 성능을 좌우함
[종류]
- 선형 조사법(Linear Probing)
충돌 발생 시, 그 옆자리가 비어있는지 조사하고 비었을 경우 그 자리에 대신 저장하는 방법입니다. 문제점은 충돌 횟수가 증가함에 따라서 특정 영역에 데이터가 몰리는 클러스터 현상이 발생합니다.
f(k)+1 -> f(k)+2 -> f(k)+3 ...
- 이차 조사법(Quadratic Probing)
선형 조사법의 문제점을 극복하기 위해 등장한 방법으로 바로 옆 자리가 아닌 좀 더 멀리서 빈 공간을 탐색합니다. 문제점은 충돌 시 빈 슬롯을 찾기 위해 접근하는 위치가 늘 동일하다는 것입니다.
f(k)+1^2 -> f(k)+2^2 -> f(k)+3^2 ...
- 이중 해시(Double Hash)
이차 조사법의 문제점을 극복하기 위해 등장한 방법으로 빈 공간 탐색을 좀 더 불규칙하게 만든 조사 방법입니다.
- 1차 해시 함수 h1(k) = k % size(배열 크기)
- 2차 해시 함수 h2(k) = 1 + (k % c) (c는 보통 size보다 작은 소수)
통계를 근거로 소수를 사용했을 때 충돌 확률이 적다고 알려져 있습니다.
📌 Separate Chaining
[장점]
- 해시 충돌이 일어나더라도 연결 리스트로 노드가 연결되기에 index가 변하지 않음
- 테이블의 각 인덱스는 연결 리스트로 구현되기 때문에 데이터 개수의 제약을 거의 받지 않음
[단점]
- 부하율(load factor)에 따라 선형적으로 성능이 저하됨. 즉, 부하율이 작을 경우에는 Open Addressing 방식이 빠름
(기본적으로 연결 리스트는 탐색을 위해 모든 노드를 순회하여 느림)
Java에서는 바로 Separate Chaining을 채택했습니다.
보통 데이터가 부하율 0.7 ~ 0.8(70 ~ 80%) 정도 채워질 경우 성능이 저하된다고 합니다. 그래서 Java에서는 load factor 값을 0.75 로 두고 있습니다.
또한, 최악의 경우 해시 충돌에 의해 한 개의 index에 여러 개의 노드가 연결 될 경우도 있습니다. Java 내부에서는 이 경우에 해당 인덱스의 LinkedList를 Binary Tree(이진 트리)로 변환하여 데이터의 색인 속도를 높입니다.
ref :
https://yiyj1030.tistory.com/347
https://st-lab.tistory.com/240
