[Java] 큐(Queue)

큐(Queue)의 개념

 - 스택과는 다르게 먼저 들어온 데이터가 먼저 나가는 FIFO( First In First Out)로 저장하는 자료 구조이다.

 - 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 유리하다.

 

큐(Queue)의 기본 메서드 4가지

1. add(item) : item을 리스트의 마지막에 추가한다.

2. remove() : 리스트의 첫 번째 항목을 제거한다.

3. peek()    : 큐의 가장 첫 번째 항목을 반환한다.

4. isEmpty() : 큐가 비어있을 경우 true를 반환한다.

 

Java API 에서 큐(Queue)의 FIFO 처리 시 유사한 메서드들의 차이점

	예외 발생	값 반환
추가(Enqueue)	add(item)	offer(item)
삭제(Dequeue)	remove()	poll()
검사(Peek)	element()	peek()

위의 표를 예로 들면 add,remove,element의 경우 예외를 발생시키지만 offer, poll, peek은 true, false를 반환한다.

 

큐(Queue)의 사용 사례

• 너비 우선 탐색 (BFS, Breath-First Search)
• 캐시(Cache) 구현 - LRU 알고리즘을 주로 확인
• 게임 매칭 시스템
• 프린터의 출력 처리

큐(Queue)의 구현

큐(Queue)의 구현에는 다양한 방법이 있다. 선형 큐,  환형 큐 , 링크드리스트를 이용한 큐 등의 다른 블로그들이 정리해놓은 것이 있지만 동작 원리는 front, rear를 통해 Insertion 연산 일 때 rear가 증가하고 Deletion 연산 일 때 front가 증가하며 데이터를 저장하는 것이다.

 

아래 소스는 Youtube 엔지니어대한민국님의 Queue 구현하기 in java에서 사용된 코드이다.

 

class Queue<T> // 객체를 만들 때 데이터 타입을 명시 하도록 선언
{    
    class Node<T>{
        private T data;
        private Node<T> next;
        
        public Node(T data) {
            this.data = data;
        }        
    }
    
    private Node<T> first;
    private Node<T> last;
    
    public void add(T item) {
        Node<T> t = new Node<>(item);
        
        if(last != null) {
            last.next = t;
        }
        last = t;
        if(first == null) {
            first = last;
        }
    }
    
    public T remove() {
        if(first == null) {
          throw new NoSuchElementException();
        }
        
        T data = first.data;
        first = first.next;
        
        if(first == null) {
            last = null;
        }
        return data;
    }
    
    public T peek() {
        if(first == null) {
            throw new NoSuchElementException();   
        }
        return first.data;
    }
    
    public boolean isEmpty() {
        return first == null;
    }
}