[Java] - 자바로 Queue 구현하기 (배열 사용)

 

 

 

Queue란?

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

[자료구조] - 큐(Queue)

 

 

 

 

 

 

 

 

 

 

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();

}

 

 

 

 

 

 

 

 

 

 

Queue 전체 구현 코드

import java.util.Arrays;

public class ArrayQueue<E> implements Queue<E> {

   private static final int DEFAULT_CAPACITY = 50;

   private int capacity;
   private E[] elements;

   private int frontIdx;
   private 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;
   }

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




   //== Constructor ==//
   @SuppressWarnings("unchecked")
   public ArrayQueue(int capacity) {
      this.capacity = capacity;
      setElements((E[])new Object[capacity]);
      setFrontIdx(0);
      setRearIdx(0);
   }


   public ArrayQueue() {
      this (DEFAULT_CAPACITY);
   }






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

   @Override
   public boolean isFull() {
      return rearIdx == capacity;
   }

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

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

   @Override
   public E rear() {
      return this.elements[this.rearIdx-1];//rear은 원소가 들어오면 1 증가하여 비어있는 위치 가리킴
   }



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

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

      E element = this.elements[frontIdx];
      this.elements[frontIdx] = null;
      this.frontIdx ++;
      return element;
   }

   @Override
   public E peek() {
      return null;
   }

   @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 );
      setElements( Arrays.copyOf( elements(), capacity()) );
   }
}

 

 

 

 

 

 

 

 

 

 

 

 

세부 구현

 

 

ArrayQueue<E>의 필드

public class ArrayQueue<E> implements Queue<E> {

   private static final int DEFAULT_CAPACITY = 50;

   private int capacity;
   private E[] elements;

   private int frontIdx;
   private int rearIdx;

 

설명

• DEFAULT_CAPACITY : 기본 용량입니다.
• capacity : 설정된 Queue의 용량입니다.
• elements : Queue의 원소를 저장할 배열입니다.
• frontIdx : Queue의 삭제 연산이 발생하는 front의 인덱스입니다.
• rearIdx : Queue의 삽입 연산이 발생하는 rear의 인덱스입니다.

 

 

 

 

 

 

 

 

 

 

ArrayQueue<E>의 생성자

//== Constructor ==//
@SuppressWarnings("unchecked")
public ArrayQueue(int capacity) {
   this.capacity = capacity;
   setElements((E[])new Object[capacity]);
   setFrontIdx(0);
   setRearIdx(0);
}


public ArrayQueue() {
   this (DEFAULT_CAPACITY);
}

 

설명

• setFrontIdx(0) : 초기 front의 인덱스 값은 0입니다.
• setRearIdx(0) : 초기 rear의 인덱스 값은 0입니다.

 

 

 

 

 

 

 

 

내부적으로 사용할 Getter, Setter

//== 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;
}

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

 

 

 

 

 

 

 

 

 

 

ArrayQueue<E>의 내부 상태 확인하기

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

@Override
public boolean isFull() {
   return rearIdx == capacity;
}

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

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

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

 

설명

• isEmpty() : front와 rear의 위치가 같을 때, Queue가 비었다고 판단합니다.
  • 삽입 시에는 rear가 증가하고, 삭제 시에는 front가 증가합니다. 즉 삽입과 삭제가 동일한 횟수만큼 발생했을 때, front와 rear의 위치가 같아지며, 이때가 Queue가 빈 상태입니다.
• isFull() : rear의 위치가 capacity와 같다면 스택이 가득 찼다고 판단합니다.
  • 만약 초기 용량이 1이라 생각하면, 삽입이 1번 발생하면 rearIdx는 1이 됩니다. 즉 이 경우 capacity == rearIdx이므로 스택이 가득 찬 상태입니다.
• size () : rear의 위치와 front의 위치의 차이가 size가 됩니다. 
  • 삽입이 발생하지 않으면 삭제를 할 수 없습니다.  front는 삭제 시에 값이 커지므로, front는 항상 rear과 같거나 작습니다.
  • 삽입이 2번 발생하고, 삭제가 1번 발생했다고 하면 rear은 2, front는 1이 됩니다. 따라서 rear - front는 1이며, 이는 size와 동일합니다.

 

 

 

 

 

 

 

 

 

 

 

ArrayQueue<E> 초기화하기

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

 

설명

• Setter를 통해 기존의 배열을 비어있는 새로운 배열로 대체합니다. 기존의 배열은 참조를 잃어 GC(Garbage Collectior)에 의해 수거됩니다.
• front와 rear의 인덱스를 0으로 옮겨주어야 합니다.

 

 

 

 

 

 

 

 

 

 

ArrayQueue<E>의 삽입과 삭제

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

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

   E element = this.elements[frontIdx];
   this.elements[frontIdx] = null;
   this.frontIdx ++;
   return element;
}

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

 

설명

• offer(E item) :  큐에 원소를 삽입합니다.
  • 삽입은 rear 위치에서 발생하므로, rear 위치에 삽입한 후, rear을 1 증가시켜줍니다.
• poll() : 큐에 가장 먼저 들어온 원소를 제거하여 반환합니다.
  • 삭제는 front 위치에서 발생하므로, front 위치에서 원소를 제거한 후, front를 1 증가시켜줍니다.
• peek() : 큐에 가장 먼저 들어온 원소를 제거하지 않고 반환합니다 
  • 큐에 가장 먼저 들어온 원소는 front에 존재합니다.

 

 

 

 

 

 

 

 

 

 

 

테스트코드

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

      Queue<Integer> queue = new ArrayQueue<>();

      IntStream.rangeClosed(0, 100).forEach(queue::offer);

      StringBuilder sb = new StringBuilder();
      while (!queue.isEmpty()){
         sb.append(queue.poll());
         sb.append("\n");
      }
      System.out.println(sb.toString());

   }
}