[Java] - 자바로 Circular Queue 구현하기

 

 

 

 

Circular Queue란? 

https://ttl-blog.tistory.com/696

[자료구조] - Circular Queue (환형 큐)

 

 

 

 

 

 

 

 

 

Circular Queue 인터페이스

기존 Queue 인터페이스와 동일합니다.

public interface Queue<E> {
   /**
    * 큐가 비어있는지 확인합니다
    */
   boolean isEmpty();

   /**
    * 큐가 가득 찼는지 확인합니다
    */
   boolean isFull();

   /**
    * 큐에 저장된 현재 원소의 수를 반환합니다.
    */
   int size();

   /**
    * 큐의 삭제(dequeue)가 발생하는 지점인 front에 존재하는 원소를 반환합니다.
    */
   E front();


   /**
    * 큐의 삽입(enqueue)가 발생하는 지점인 front에 존재하는 원소를 반환합니다.
    */
   E rear();


   /**
    * offer를 수행합니다.
    * 큐에 요소를 삽입합니다.
    * (== EnQueue)
    */
   boolean offer(E item);

   /**
    * poll을 수행합니다.
    * 큐에 가장 마지막에 들어간 원소를 큐에서 제거한 뒤 반환합니다.
    * 원소가 없다면 null을 반환합니다.
    * (== DeQueue)
    */
   E poll();

   /**
    * peek를 수행합니다.
    * 큐에 가장 마지막에 들어간 원소를 큐에서 제거하지 않고 반환합니다.
    * 원소가 없다면 null을 반환합니다.
    */
   E peek();

   /**
    * 큐을 비웁니다.
    */
   void clear();

}

 

 

 

 

 

 

 

 

 

 

CircularArrayQueue<E> 전체 구현 코드

package queue;

import java.util.Arrays;

/**
 * Created by ShinD on 2022/06/04.
 */
public class CircularArrayQueue<E> implements Queue<E> {

	private static final int DEFAULT_CAPACITY = 10;

	private int capacity;
	private int maxLength;//capacity + 1

	private E[] elements;

	public int frontIdx;
	public int rearIdx;


	//== getter / setter ==//
	private int capacity() {
		return capacity;
	}

	private void setCapacity(int capacity) {
		this.capacity = capacity;
	}

	private E[] elements() {
		return elements;
	}

	private void setElements(E[] elements) {
		this.elements = elements;
	}

	public int frontIdx() {
		return frontIdx;
	}

	public void setFrontIdx(int frontIdx) {
		this.frontIdx = frontIdx;
	}

	public int rearIdx() {
		return rearIdx;
	}

	public void setRearIdx(int rearIdx) {
		this.rearIdx = rearIdx;
	}

	public int maxLength() {
		return maxLength;
	}

	public void setMaxLength(int maxLength) {
		this.maxLength = maxLength;
	}

	//== [Finish] - getter / setter ==//




	//== Constructor ==//
	@SuppressWarnings("unchecked")
	public CircularArrayQueue(int capacity) {
		setCapacity(capacity);
		setMaxLength(capacity + 1);
		setElements((E[])new Object[maxLength()]);
		setFrontIdx(0);
		setRearIdx(0);
	}


	public CircularArrayQueue() {
		this (DEFAULT_CAPACITY);
	}





	private void plusRearIdx(){
		this.rearIdx = (rearIdx + 1) % maxLength;
	}
	private void plusFrontIdx(){
		this.frontIdx = (frontIdx + 1) % maxLength;
	}






	@Override
	public boolean isEmpty() {
		return frontIdx == rearIdx;
	}

	@Override
	public boolean isFull() {
		return ((rearIdx + 1) % maxLength) == frontIdx;
	}


	@Override
	public int size() {
		int size = rearIdx - frontIdx;

		return (size < 0) ? size + maxLength : size;
	}



	@Override
	public E front() {
		return this.elements[this.frontIdx];
	}

	@Override
	public E rear() {
		return this.elements[this.rearIdx];
	}



	@Override
	public boolean offer(E item) {
		if (isFull()) grow();
		this.elements[rearIdx] = item;
		plusRearIdx();
		return true;
	}

	@Override
	public E poll() {
		if (isEmpty()) {return null;}

		E element = this.elements[frontIdx];
		this.elements[frontIdx] = null;
		plusFrontIdx();
		return element;
	}

	@Override
	public E peek() {
		return this.elements[frontIdx];
	}

	@Override
	@SuppressWarnings("unchecked")
	public void clear() {
		setElements( (E[]) new Object[this.capacity()]);
		setFrontIdx(0);
		setRearIdx(0);
	}

	/**
	 * 배열의 크기를 2배로 늘려준다.
	 */
	@SuppressWarnings("unchecked")
	private void grow() {
		setCapacity( capacity() * 2 );
		setMaxLength( capacity() + 1 );
		setElements( Arrays.copyOf( elements(), capacity()) );
	}
}

 

 

대부분 Queue와 동일하지만 차이가 있는 부분을 중심적으로 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

CircularArrayQueue<E> 내부 상태 확인

@Override
public boolean isEmpty() {
   return frontIdx == rearIdx;
}

 

설명

기존 Queue와 동일하게 front의 위치와 rear의 위치가 동일하면 이는 비어있는 상태라 판단합니다.

 

 

 

 

 

 

@Override
public boolean isFull() {
   return ((rearIdx + 1) % maxLength) == frontIdx;
}

설명

CircularQueue는 기존 Queue와는 달리 배열의 끝과 시작이 연결되어 있습니다.

따라서 배열을 가득 채운 상태에서는 rear과 front의 위치가 다시 동일해집니다. (한바퀴를 돈다고 생각)

 

그렇기에 CircularQueue는 배열의 마지막 공간을 사용하지 않습니다. 

 

배열의 마지막을 사용하지 않으므로 용량이 가득 찼는지를 판단하려면

rear의 다음 위치를 배열의 최대 길이로 나눈 나머지가 front와 동일한지를 판단하면 됩니다. (나눠주지 않는다면 배열의 최대 길이를 넘어갈 수 있습니다.)

 

 

 

 

 

 

 

@Override
public int size() {
   int size = rearIdx - frontIdx;

   return (size < 0) ? size + maxLength : size;
}

설명

크기는 rear의 위치에서 front의 위치를 빼준 만큼이 크기가 됩니다.

그러나 CircularQueue는 front가 rear보다 더 클 수 있습니다.

따라서 뺀 값이 음수라면 이를 양수로 바꾸어주는 작업이 필요합니다.

음수인 경우, 해당 값에 배열의 최대 길이를 더해주면 size가 나옵니다.

 

 

 

 

 

 

 

 

 

 

 

CircularArrayQueue<E> 의 rear와 front 증가

private void plusRearIdx(){
   this.rearIdx = (rearIdx + 1) % maxLength;
}
private void plusFrontIdx(){
   this.frontIdx = (frontIdx + 1) % maxLength;
}

 

설명

rear과 front는 증가하는 부분의 코드가 동일합니다. 따라서 rear만 설명하겠습니다.

 

rear는 다음 원소가 삽입될 배열의 인덱스입니다.

그런데 Circular Queue에서는 배열의 마지막 칸을 사용하지 않습니다.

즉 rear가 배열의 최대 길이보다 1 작은 경우, rear을 증가시키면 0으로 바꾸어 주어야 합니다.

 

이를 위해 rear에 1을 더한 후, 이를 배열의 길이로 나눈 나머지 값을 rear에 저장해 주는 것입니다.

 

 

 

 

 

 

 

테스트코드

import java.util.stream.IntStream;

public class Test {
   public static void main(String[] args) {
      
      CircularArrayQueue<Integer> cqueue = new CircularArrayQueue<>();

      IntStream.rangeClosed(0, 100).forEach(cqueue::offer);//초기 Queue 의 용량은 10 -> 10번 추가하여 rearIdx 는 0  (0, 1, ..., 9, 0)
      
      IntStream.rangeClosed(0, 100).forEach( i -> System.out.println(cqueue.poll()));//다 제거하였기에 frontIdx 도 0

   }
}

 

 

 

 

 

 

 

 

Queue와의 비교

Circular Queue는 결국 기존 Queue의 배열의 공간을 낭비하는 문제를 해결하기 위해서 사용한다고 하였습니다.

정말 배열의 공간이 낭비되지 않는지 다음 코드로 확인해 보겠습니다.

public class Test {
   public static void main(String[] args) {

      ArrayQueue<Integer> queue = new ArrayQueue<>();
      IntStream.rangeClosed(0, 9).forEach(queue::offer);//초기 Queue 의 용량은 10
      IntStream.rangeClosed(0, 9).forEach( i -> queue.poll());//다 제거하였지만, rear은 capacity와 동일한 상태
      IntStream.rangeClosed(0, 5).forEach(queue::offer);//이곳에서 하나를 더 추가하면 isFull이 true이므로 용량 증가
      System.out.println(queue.growCount);



      CircularArrayQueue<Integer> cqueue = new CircularArrayQueue<>();

      IntStream.rangeClosed(0, 9).forEach(cqueue::offer);//초기 Queue 의 용량은 10 -> 10번 추가하여 rearIdx 는 0  (0, 1, ..., 9, 0)
      IntStream.rangeClosed(0, 9).forEach( i -> cqueue.poll());//다 제거하였기에 frontIdx 도 0
      IntStream.rangeClosed(0, 5).forEach(cqueue::offer);//이곳에서 하나를 더 추가하면,
      System.out.println(cqueue.growCount);

   }
}

growCount는 grow가 발생하면 1씩 증가하도록 테스트를 위해 잠깐 추가한 것입니다.

결과는 다음과 같습니다.

즉 초기 용량을 둘다 10으로 한 상태에서,  동일하게 원소 10개를 삽입하고, 10개를 삭제한 뒤 다시 5개를 삽입했습니다.

 

기존 Queue의 경우, rear의 위치를 통해 가득 찼다고 판단하여 용량을 증가시켰지만

Circular Array Queue의 경우 용량이 증가되지 않았습니다.