Queue는 무엇인가?

 - Queue는 '선입선출(first-in fisrt out) 자료구조를 구현한 자바 인터페이스이다.

 - java.util에서 제공

 

 

http://www.jroller.com/VelkaVrana/resource/java16collections/queues090524-final.png

http://www.jroller.com/velkaVrana/entry/java_1_6_collections_class

 

 - Iterable과 Collection의 기능을 가지고 있다는게 Queue의 특징

 - Queue의 기능을 활용한 클래스 중 대표적인 클래스로 LinkedList가 있음

@Test
public void queueInsertion() {
   Queue<String> queue = new LinkedList<>();
   queue.add("first");
   queue.add("second");
   queue.add("third");

   assertEquals("first", queue.remove());
   assertEquals("second", queue.remove());
   assertEquals("third", queue.peek());
   assertEquals("third", queue.remove());
}

@Test
public void test_queue_poll_peek() {
   Queue<String> queue = new LinkedList<>();

   assertEquals(null, queue.poll());
   assertEquals(null, queue.peek());
}

@Test(expected = NoSuchElementException.class)
public void test_queue_remove() {
   Queue<String> queue = new LinkedList<>();
   queue.remove();
}

 

 - 새 원소를 추가하는 add 메서드, 오래된 원소를 제거하는 remove 메서드, 가장 오래된 원소를 반환하지만 삭제하지 않는 peek 메소드 가 있다. poll은 원소를 꺼내는 메소드 이다.

항목     자료구조	삽입 연산		삭제 연산
	연산자	삽입 위치	연산자	삭제 위치
스택	push	top	pop	top
큐	enQueue	rear	deQueue	front

1 공백 큐 생성 : createQueue();

2. 원소 A 삽입: enQueue(Q, A);

3. 원소 B 삽입 : enQueue(Q, B);

4. 원소 삭제 : deQueue(Q);

5. 원소 C 삽입 :  enQueue(Q, C);

6. 원소 삭제 : deQueue(Q);

7. 원소 삭제 : deQueue(Q);

 

public interface Queue {
   boolean isEmpty();
   void enQueue(char item);
   char deQueue();
   void delete();
   char peek();
}

 

public class ArrayQueue implements Queue {
   private int front;
   private int rear;
   private int queueSize;
   private char itemArray[];

   public ArrayQueue(int queueSize) {
      front = -1;
      rear = -1;
      this.queueSize = queueSize;
      itemArray = new char[this.queueSize];
   }

   @Override
   public boolean isEmpty() {
      return front == rear;
   }

   public boolean isFull() {
      return rear == this.queueSize - 1;
   }

   @Override
   public void enQueue(char item) {
      if (isFull()) {
         System.out.println("Queue is Full.");
         return;
      }

      itemArray[++rear] = item;
      System.out.println("Inserted Item" + item);
   }

   @Override
   public char deQueue() {
      if (isEmpty()) {
         System.out.println("Queue is Empty.");
         return 0;
      }
      return itemArray[++front];
   }

   @Override
   public void delete() {
      if (isEmpty()) {
         System.out.println("Queue is Empty.");
         return;
      }

      ++front;
   }

   @Override
   public char peek() {
      if(isEmpty()) {
         System.out.println("Queue is Empty.");
         return 0;
      }

      return itemArray[front + 1];
   }

   public void printQueue() {
      if(isEmpty()) {
         System.out.println("Queue is Empty.");
         return;
      }

      System.out.print("Array Queue>>");

      for(int i= front + 1; i <= rear; i++) {
         System.out.printf("%c ",  itemArray[i]);
      }
      System.out.println();
      System.out.println();
   }
}

 

 

 

public static void main(String[] args) {
   ArrayQueue Q = new ArrayQueue(3);

   Q.enQueue('A');
   Q.printQueue();

   Q.enQueue('B');
   Q.printQueue();

   System.out.println("delete item" + Q.deQueue());
   Q.printQueue();

   Q.enQueue('C');
   Q.printQueue();

   System.out.println("delete item" + Q.deQueue());
   Q.printQueue();

   System.out.println("delete item" + Q.deQueue());
   Q.printQueue();

}

결과

 

 

1. 큐에 최대로 저장할 수 있는 원소 개수를 배열의 크기로 하는 1차원 배열 선언, front 와 rear는 -1로 초기화

2. front와 rear가 같으면 Empty,배열 사이즈 -1과 rear가 같으면 Full.

3. 큐에 삽입하려면 마지막 원소의 다음 자리에 삽입 해야 하므로 마지막 원소의 인덱스를 저장한 rear 값을 하나 증가시켜 삽입할 자리를 준비,

   그 인덱스에 해당하는  배열 원소 Q[rear] 에 item 저장

4. 삭제는 가장 먼저 큐에 들어와 있는 원소를 가장 먼저 삭제, 그러기 위해서 front의 위치를 한 자리 조정하고 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리를 준비하고 그 자리의 원소를 삭제하여 반환

delete 연산은 front의 원소를 삭제하고 deQueue() 연산은 front의 원소를 삭제하고 삭제한 원소를 반환

5. peek은 원소중 가장 먼저 들어와 있는 원소, 즉Q[front + 1]에 있는 원소를 검색하여 반환 하는 연산.

 

 

참고 URL :http://neleader.tistory.com/archive/201406

참고서적 : 자바로 배우는 쉬운 자료구조 - 이지영 저