서론

백준 5430번 AC문제를 풀다가 Array로 구현을 하려고 했는데, 생각보다 막히는 부분이 많았다.

여러가지 방안을 찾아보면서 꾸역꾸역 구현을 하면 만들기는 했겠지만, 그렇게 구현하는 것 보다 제대로 구현하는게 더 낫겠다 싶어서 풀이를 찾아보게 되었다.

백준 5430 풀이
Queue구현 글

풀이를 보니 Queue를 직접 구현해보고 아는 것이 중요하다고 해서
직접 따라해보고, 이해하기로 했다.

물론 Queue의 자료구조를 모르는 것도 아니고 구현을 안해본 것도 아니지만,
이전에 Queue를 구현했던 것은 C언어를 통해서 구현한 것이 전부였기 때문에 java를 통해서 구현을 해보기로 했다.

본론

왜 그냥 만들어진 Queue의 메소드를 쓰면 되는데 직접 구현을 하는거야?

"안다고 생각하는 순간 알려고 하지 않는다" 가 나의 모토이기 때문에 직접 해보고 알아야한다고 생각.
또한, 직접구현을 해봄으로써 어떻게 동작을 하는지 뜯어보는 것은 매우 중요하다고 생각함

Queue는 어떤 특징이 있는데?

• Queue는 FIFO(first in fisrt out)이다
  • 일반적으로 우리가 줄을 서는 구조와 똑같다. 선입선출의 구조이다.
  • front로 들어와 rear로 나간다.

• que는 추가, 제거, 꺼내보기의 메소드가 각각 2개씩 있다.
  • add는 사이즈를 넘어설 경우, 예외로 오류가 발생하지만, offer는 false를 반환한다.
  • remove는 삭제할 요소가 없으면 즉, isEmpty이면, NosuchElementException예외가 발생한다. 하지만, poll의 경우는 null을 반환한다.
  • element도 remove와 마찬가지로 비었을 경우 NosuchElementException이 발생한다. 하지만, peek은 null을 반환한다.

짚고갈 부분

• poll메소드에 @SuppressWarnings("unchecked") 가 나오는데, 이 코드를 붙이지 않으면 type safe(타입 안정선)에 대해 경고를 보낸다.
  • 우리는 E타입으로 캐스팅을 하고 있기때문에 Object[] 배열의 Object데이터를 E타입으로 변환할 때
    변환할 수 없는 타입이 있을 수 있다는 경고가 뜨게 된다.
    하지만, 여기서는 E타입만 존재하기 때문에 형 안정성이 보장된다.
  • 즉, ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 것이다.

결론

조금은 알고있던 Queue도 다시보니 새로운 부분이 많았고, 자료구조 공부뿐만 아니더라도 Java를 공부할 수단으로도 자료구조 구현은 정말 좋은 것 같다.

Priority Queue (우선순위 큐)
Array Deque (배열 덱)
Circular Queue (원형 큐)

등의 다양한 것도 있으니까 기회가 되면 또 구현을 해봐야겠다.

동작

• resize()는 크기를 늘려주는 메소드입니다.
  • 일반 Queue도 동적할당이기 때문에 여기서도 동적할당을 구현하기 위해서 크기가 64를 넘었을 때, 크기를 2배 더 늘려주는 메소드입니다.

• offer()는 원소를 넣어주는 메소드입니다.
  • array가 가득찼을 때, 크기를 늘려주기 위해서 resize(array.length * 2); 메소드를 실행시킵니다.
  • 일반적인 경우에는 rear에 값을 넣어주고 size를 증가시켜줍니다.

		array[rear] = item;
		size ++;   

• E poll()은 앞의 원소를 꺼내서 Queue에서 제거하는 메소드이다.
  • 원소를 꺼내고 array의 front자리의 값을 null로 바꿔주고 size를 하나 줄입니다.

		array[front] = null;
		size--;

• remove()는 원소 하나를 제거합니다.
  • 앞서 설명한 것과 같이 poll()과 차이점은 size가 0일 때, NoSuchElementException가 발생합니다.

• peek()은 가장 앞에 있는 원소를 확인합니다. 제거가 되지는 않습니다.
  • size가 0일 때 null을 반환합니다.

• element()는 peek과 같이 가장 앞의 원소를 확인합니다.
  • size가 0일 때는 NoSuchElementException가 발생합니다.

• size()는 size를 확인합니다.

• isEmpty()는 Queue가 비었는지 확인합니다.

• contains(Object value)는 찾는 값과 일치하는 값이 있는지 확인합니다.

• clear()는 Queue를 비우는 메소드입니다.

  • array를 전부 null값으로 바꿔줍니다.

• 마지막 Iter class는 Deque을 iterator로 출력하기 위한 class입니다.

마지막 줄 출력 결과

Deque을 전체 출력하기 위해 Iterator를 사용하면 전체를 출력할 수 있습니다.
바로 toString()을 사용하면 주소값이 출력됩니다.

코드

Quueue.java (인터페이스)

package Interface_form;

// Queue구현 인터페이스
public interface Queue<E> {
	
	/**
	 * @param e 큐에 추가할 요소
	 * @return 큐에 요소가 정상적으로 추가되었을 경우 true를 반환
	 */
	
	boolean offer(E e);
	
	E poll();
	
	E peek();
} 

ArrayQueue.java (Queue 메소드 구현)

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