[자료구조*알고리즘] 7.Java 큐(Queue) 정리

 

Java 큐(Queue) 정리

 

1. 큐(Queue)의 개요

2. 큐(Queue)의 동작

3. 배열을 이용한 큐 구현

 

 

1. 큐(Queue)의 개요

1) 가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO - First In First Out) 형태의 자료구조

2) 가장 오래전에 입력된 데이터를 front 라고 하며 가장 최근에 입력된 데이터를 rear라고 한다. 데이터의 삽입은 rear에서 이루어지고 삭제는 front에서 이루어지기 때문에 큐를 구현하기 위해서는 front와 rear를 관리하는 배열을 이용하거나 front 노드와 rear 노드를 관리하는 연결 리스트를 이용할 수 있다.

 

 

 

 

2. 큐(Queue)의 동작

1) 삽입 - insert

큐에 새로운 데이터를 삽입하는 작업을 insert라고 한다. 이는 리스트의 끝 부분을 가리키는 rear에서 발생하며 데이터가 삽입 될 때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

 

2) 삭제(추출) - remove

큐에서 데이터를 제거하는 작업을 remove라고 하며 이는 항상 front에서 발생한다.
front가 가리키고 있는 데이터를 꺼낸 후 front 값을 하나 증가 시키도록 구현한다.
front 값이 rear를 추워랗게 되면 더이상 제거할 데이터가 없는 상태 즉, 자료가 하나도 없는 빈 큐임을 의미한다.

 

3) 읽기 - Peek

큐에서 front가 가리키는 데이터를 읽는 작업을 peek라고 하며 데이터를 제거하지 않고 읽는 작업만 수행하므로 front 값을 변경시키지 않는다.

 

 

 

 

3. 배열을 이용한 큐 구현

public class ArrayQueue {
    
    // 큐 배열은 front와 rear 그리고 maxSize를 가진다.
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
    
    // 큐 배열 생성
    public ArrayQueue(int maxSize){
        
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }
    
    // 큐가 비어있는지 확인
    public boolean empty(){
        return (front == rear+1);
    }
    
    // 큐가 꽉 찼는지 확인
    public boolean full(){
        return (rear == maxSize-1);
    }
    
    // 큐 rear에 데이터 등록
    public void insert(Object item){
        
        if(full()) throw new ArrayIndexOutOfBoundsException();
        
        queueArray[++rear] = item;
    }
    
    // 큐에서 front 데이터 조회
    public Object peek(){
        
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        
        return queueArray[front];
    }
    
    // 큐에서 front 데이터 제거
    public Object remove(){
        
        Object item = peek();
        front++;
        return item;
    }

}

가장 먼저 삽입한 데이터이며 데이터를 추출할 때 사용할 인덱스이기도 한 front 와 마지막에 삽입한  데이터의 인덱스를 가리키는 rear, 큐의 최대 크기인 maxSize와 실제 데이터를 저장할 배열인 queueArray를 선언하고 생성자를 통해 이를 초기화 한다.

 

empty() 메소드는 front가 rear를 추월했을 경우 더이상 꺼낼 데이터가 없으므로 true를 반환하며
full() 메소드는 데이터를 저장할 위치인 rear가 배열의 크기에 도달했을 때 true를 반환하여 배열이 다 찼음을 의미한다.

 

insert() 메소드는 리스트에 데이터를 삽입하는 메소드로 rear 값을 하나 증가시키고 배열의 rear 위치에 삽입할 데이터를 지정한다.
peek() 메소드는 리스트의 데이터 중 가장 먼저 삽입된 데이터를 가리키는 front에 위치한 데이터를 꺼내어 반환하며 
remove() 메소드는 peek() 메소드를 통해 데이터를 하나 반환하고 front를 하나 증가시키면서 데이터의 삭제(추출) 작업을 수행한다.

 

배열을 이용하여 큐를 구현할 때의 단점으로는 그 크기가 고정되었다는 점과 데이터의 삽입과 삭제가 반복 될 수록 rear와 front가 계속 증가되므로 이미 꺼낸 데이터가 들어있던 배열의 인덱스를 다시 활용할 수 없다는 점이다.
그리고 데이터가 다 차있지 않더라도 rear와 front가 계속 증가되다 보면 언젠가는 배열의 사이즈까지 도달하여 더이상 사용할 수 없게 된다는  문제점이 발생한다.

 

이러한 문제점을 해결하기 위하여 이동 큐(moving queue)를 사용할 수 있는데 이는 큐가 다 찼을 경우 앞부분에 사용할 수 있는 공간만큼 전체 데이터들을 앞쪽으로 이동시키고 rear와 front를 수정하여 남은 공간을 사용하는 방법이다.
하지만 자료를 이동하면서 발생하는 시간을 고려해 보면 효율적이지 않다는 것을 알 수 있다.
최악의 경우 남은 공간이 하나밖에 없을 경우 하나의 데이터를 큐에 넣기 위해 매번 maxSize-1 만큼의 데이터를 이동시켜야 할 수도 있기 때문이다.
이를 보완하기 위해 원형 큐(Circular Queue)를 사용할 수 있다.