백준 5430번 AC문제를 풀다가 Array로 구현을 하려고 했는데, 생각보다 막히는 부분이 많았다.
여러가지 방안을 찾아보면서 꾸역꾸역 구현을 하면 만들기는 했겠지만, 그렇게 구현하는 것 보다 제대로 구현하는게 더 낫겠다 싶어서 풀이를 찾아보게 되었다.
풀이를 보니 Queue를 직접 구현해보고 아는 것이 중요하다고 해서
직접 따라해보고, 이해하기로 했다.
물론 Queue의 자료구조를 모르는 것도 아니고 구현을 안해본 것도 아니지만,
이전에 Queue를 구현했던 것은 C언어를 통해서 구현한 것이 전부였기 때문에 java를 통해서 구현을 해보기로 했다.
"안다고 생각하는 순간 알려고 하지 않는다" 가 나의 모토이기 때문에 직접 해보고 알아야한다고 생각.
또한, 직접구현을 해봄으로써 어떻게 동작을 하는지 뜯어보는 것은 매우 중요하다고 생각함
front
로 들어와 rear
로 나간다.@SuppressWarnings("unchecked")
가 나오는데, 이 코드를 붙이지 않으면 type safe(타입 안정선)에 대해 경고를 보낸다.ClassCastException
이 뜨지 않으니 이 경고들을 무시하겠다는 것이다.조금은 알고있던 Queue도 다시보니 새로운 부분이 많았고, 자료구조 공부뿐만 아니더라도 Java를 공부할 수단으로도 자료구조 구현은 정말 좋은 것 같다.
Priority Queue (우선순위 큐)
Array Deque (배열 덱)
Circular Queue (원형 큐)
등의 다양한 것도 있으니까 기회가 되면 또 구현을 해봐야겠다.
resize()
는 크기를 늘려주는 메소드입니다.offer()
는 원소를 넣어주는 메소드입니다.resize(array.length * 2);
메소드를 실행시킵니다. array[rear] = item;
size ++;
E poll()
은 앞의 원소를 꺼내서 Queue에서 제거하는 메소드이다. array[front] = null;
size--;
remove()
는 원소 하나를 제거합니다.peek()
은 가장 앞에 있는 원소를 확인합니다. 제거가 되지는 않습니다.element()
는 peek과 같이 가장 앞의 원소를 확인합니다.size()
는 size를 확인합니다.isEmpty()
는 Queue가 비었는지 확인합니다.contains(Object value)
는 찾는 값과 일치하는 값이 있는지 확인합니다.clear()
는 Queue를 비우는 메소드입니다.
마지막 Iter class는 Deque을 iterator
로 출력하기 위한 class입니다.
Deque을 전체 출력하기 위해 Iterator를 사용하면 전체를 출력할 수 있습니다.
바로 toString()을 사용하면 주소값이 출력됩니다.
package Interface_form; // Queue구현 인터페이스 public interface Queue<E> { /** * @param e 큐에 추가할 요소 * @return 큐에 요소가 정상적으로 추가되었을 경우 true를 반환 */ boolean offer(E e); E poll(); E peek(); }
import java.util.Arrays; import java.util.NoSuchElementException; import Interface_form.Queue; public class ArrayQueue<E> implements Queue<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=0, j = front + 1; i<=size; i++, j++) { newArray[i] = array[j % arrayCapacity]; } this.array = null; this.array = newArray; front = 0; rear = size; } public boolean offer(E item) { // 용적이 가득 찼을 경우 if( (rear + 1) % array.length == front ) { resize(array.length * 2); // queue의 사이즈를 2배로 늘려준다. } rear = (rear + 1) % array.length; // rear를 rear의 다음 위치로 갱신 array[rear] = item; size ++; return true; } public E poll() { // 삭제할 원소가 없을 경우 null을 반환 if(size == 0) { return null; } front = (front + 1) % array.length; // front를 한 칸 옮긴다. // @SuppressWarnings를 붙이지 않으면 type safe(타입 안정성)에 대한 경고를 보낸다. // 반환되는 것을 보면 E타입으로 캐스팅하고 있고 그 대상이 되는 것은 Object[]배열의 Object데이터이다. // 즉, Object -> E로 타입을 변환하는 것 @SuppressWarnings("unchecked") E item = (E) array[front]; array[front] = null; size--; // 용적이 최소 크기(64)보다 크고, 요소 개수가 1/4 미만일 경우 if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) { // 아무리 작아도 최소용적 미만으로 작아지지는 않도록 한다. resize(Math.max(DEFAULT_CAPACITY, array.length / 2)); } return item; } // poll()을 호출하여 null일 경우에만 예외를 던진다. public E remove() { E item = poll(); if(item == null) { throw new NoSuchElementException(); } return item; } // poll()과 마찬가지로 Queue에서 꺼내 E타입의 원소를 반환해야하기 때문에 // @SuppressWarnings("unchecked")를 붙여준다. public E peek() { if(size == 0) { return null; } @SuppressWarnings("unchecked") E item = (E) array[(front) + 1 % array.length]; return item; } // remove와 같은 과정 public E element() { E item = peek(); if(item == null) { throw new NoSuchElementException(); } return item; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public boolean contains(Object value) { int start = (front + 1) % array.length; 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 Iterator<E> iterator() { return new Iter(); } private class Iter implements Iterator<E> { private int count = 0; private int len = array.length; private int now = (front + 1) % len; @Override public boolean hasNext() { return count < size; } @SuppressWarnings("unchecked") @Override public E next() { int cs = count; int ns = now; if (cs >= size) { throw new NoSuchElementException(); } Object[] data = ArrayQueue.this.array; count = cs + 1; now = (ns + 1) % len; return (E) data[ns]; } } public static void main(String[] args) { ArrayQueue<Integer> que = new ArrayQueue<>(); que.offer(1); que.offer(2); que.offer(3); System.out.println(que.poll()); Iterator<Integer> it = que.iterator(); while(it.hasNext()) { int num = it.next(); System.out.println(num); } System.out.println(que.toString()); } // End of main } // End of ArrayQueue