Queue

 

Queue 란?

먼저 넣은 데이터가 먼저 나오는 형태로 저장하는 자료구조

 

 

Queue 특징

1. FIFO (First In First Out)
   • 먼저 들어간 데이터가 제일 먼저 나오는 선입선출의 자료구조
2. 데이터는 하나씩 넣고 뺄 수 있다.
3. 두 개의 입출력 방향을 가지고 있다. 
   • 한쪽 끝에서는 삽입 작업, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어진다. 
   • rear : 삽입 연산(인큐, Enqueue)이 이루어지는 곳 
   • front : 삭제 연산(디큐, Dequeue)이 수행되는 곳

 

 

Queue 의 사용 사례

• 프로세스 관리
• 프린터 인쇄 작업
• 은행 업무나 서비스센터의 대기열
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Chche) 구현

 

 

Queue 메서드

• Queue 를 구현한 실제 구현 객체로는 LinkedList 가 있다. 

리턴 타입	메서드	설명
boolean	add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true 반환. (저장공간이 부족하면 IllegalStateException 발생(?))
QObject	remove()	Queue에서 가장 먼저 저장된 객체를 꺼내 반환. (비어있으면 NoSuchElementException 발생)
Object	element()	삭제 없이 가장 먼저 저장된 요소를 읽어온다.  (peek() 와 달리 Queue가 비었을 때 NoSuchElementException 발생)
Object	poll()	Queue에서 객체를 꺼내서 반환. 비어있으면 null 반환
Object	peek()	삭제없이 가장 먼저 저장된 요소를 읽어온다.  Queue이 비어있으면 null 반환
boolean	offer(Object o)	Queue에 객체 저장. 성공하면 true, 실패하면 false 반환

 

 

Queue 직접 구현해보기

• LinkedList로 구현되어 있지만, Queue의 동작을 이해한다는 관점에서 ArrayList로 구현
• 구현하려는 기능
  • add() : 큐에 데이터 추가
  • poll() : 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴
  • peek() : 큐에 가장 먼저 추가된 데이터 리턴 (삭제X)

public class MignonQueue {

    private ArrayList<Integer> listQueue = new ArrayList<>();

    public void add(Integer data) {
        listQueue.add(data);
    }

    public Integer poll() {
        if(listQueue.size() == 0) {
            return null;
        }
        return listQueue.remove(0);
    }

    public Integer peek() {
        if(listQueue.size() == 0) {
            return null;
        }
        return listQueue.get(0);
    }
    
}