[자료구조]QUEUE

QUEUE

---

전후/선후 관계가 1:1로 선형 자료구조

 

FIFO(first in first out) 먼저 입력된 Data가 먼저 출력된다. 

주로 우선순위가 따로 없이 순서대로 진행되어야 할 때 사용한다. 

 

입력/추가(Enqueue)는 끝(Rear or Tail)에서만 가능하고 

출력/제거(Dequeue)는 처음(Front or Head)에서만 가능

 

 

큐 구조에서 가능한 작업들은 Enqueue, Dequeue, Peek 정도가 있다.
Enqueue - 큐에 데이터를 추가하는 작업으로 Rear 쪽으로 추가된다.
Dequeue - 큐에서 데이터를 반환 및 삭제하는 작업으로 front에서 삭제된다.
peek - 현재 반환될 데이터를 확인한다. 데이터를 확인만 할 뿐 큐에서 제거는 안 함

 

큐의 구현 방법에는 링크드 리스트를 이용하는 방법과 배열을 이용하는 방법이 있다.

 

 

 

자바에서의 QUEUE

---

자바에서 제공하는 Queue 클래스는 아래와 같이 링크드 리스트를 이용해 생성할 수 있다.
Queue<Integer> queue = new LinkedList<>();

 

Queue 클래스는 아래와 같은 메서드들이 있다.

 

이 중 add, remove, element는 큐가 비어있거나 꽉 차 있을 때 예외가 발생하고

offer, poll, peek는 null 혹은 boolean 값을 반환한다.

 

 

 

배열로 QUEUE 구현

---

아래는 위에 정리된 내용을 토대로 배열을 이용해 큐를 구현한 코드다.

 

 

큐의 크기와 큐에 들어갈 타입을 넣어서 생성하면 해당 크기와 타입의 배열을 내부적으로 생성해
저장소를 만들고 큐와 동일한 작업을 수행하도록 구현했다.

 

링크드 리스트와 다르게 배열은 각 위치마다 인덱스가 있어 

맨 앞의 데이터를 출력하면 Array[0]이 비어지게 되는데
비어질 때마다 해당 공간을 다시 사용하기 위해 한 칸씩 쉬프트를 할 수 없으므로 

index를 통해 저장 위치를 조절한다.

 

index를 배열의 size로 나눈 나머지를 통해 저장 위치가 순환되도록 구현했다.

 

아래는 저장되는 예시다.

head와 tail의 mod size 값이 실제 배열에 저장되는 index 값

 

 

 

실제 구현 코드

import java.lang.reflect.Array;
import java.util.function.Consumer;
 
/**
 * 배열로 Queue 구현 테스트<br>
 * 선형 구조, FIFO<br>
 * 큐에 값이 추가 삭제가 계속 이루어지는데<br>
 * Head 위치의 값을 삭제할 때 마다 값들을 한칸씩 쉬프트하기 어려우므로<br>
 * Head 나 Tail 위치를 나타내는 index 값을 size로 나누어<br>
 * 배열의 index가 0,1,2,3...size,0,1,2... 순환되도록 구현<br>
 * 배열은 고정되고 index 값만 조절 하여 큐와 같이 동작하도록 함
 * */
public class QueueArray<T> {
    /**
     * head queue의 시작, Head 또는 Front로 불림<br>
     * tail queue의 끝, Tail 또는 Rear로 불림<br>
     * size Queue를 구현할 배열의 사이즈<br>
     * queue 입력받은 클래스 타입과 사이즈에 따라 생성된 배열
     * */
    private int head;
    private int tail;
    private int size;
    private T[] queue;
    
    /**
     * Queue 배열 생성
     * @param size Queue를 구현할 배열의 사이즈
     * @param type Queue를 구현할 배열의 타입
     */
    @SuppressWarnings("unchecked")
    public QueueArray(int size, Class<T> type) {
        this.size = size;
        this.head = 0;
        this.tail = -1;
        queue = (T[]) Array.newInstance(type,size);
    }
    
    /**
     * 큐의 끝(Tail)에  data를 입력/추가<br>
     * 큐가 꽉 차있을 경우 더이상 추가하지 않음
     * @param data 입력할 값
     */
    public void enqueue(T data) {
        if(!isFull()) {
            tail++;
            queue[getMod(tail)] = data;
        }
    }
    
    /**
     * 큐의 시작부분(Head) 값을 출력/제거<br>
     * 큐가 비어있을 경우 null을 반환
     * @return T 큐의 시작부분 값 or null
     */
    public T dequeue() {
        if(!isEmpty()) {
            T returnData = queue[getMod(head)];
            queue[getMod(head)] = null;
            head++;
            return returnData;            
        }else {
            return null;
        }
    }
 
    /**
     * 큐의 시작부분(Head) 값만 반환 큐는 변화가 없음<br>
     * 큐가 비어있을 경우 null을 반환
     * @return T 큐의 시작부분 값 or null
     */
    public T peek() {
        if(!isEmpty()) {
            return queue[getMod(head)];            
        }else {
            return null;
        } 
    }
    
    /**
     * 큐가 비어있는지 여부를 나타낸다.<br>
     * 비어있으면 true, 비어있지 않으면 false를 반환
     * @return boolean 큐가 비어있는지 여부
     */
    public boolean isEmpty() {
        //[tail][head] tail과 head 위치가 연속되고 head위치의 값이 비어있으면 비어있는 큐
        if(getMod(head) == getMod(tail+1) && queue[getMod(head)] == null) {
            return true;            
        }else {
            return false;
        }
    }
    
    /**
     * 큐가 꽉 차있는지 여부를 나타낸다.<br>
     * 꽉 차있으면 true, 꽉 차있지 않으면 false를 반환
     * @return boolean 큐가 꽉 차있는지 여부
     */
    public boolean isFull() {
        //[tail][head] tail과 head 위치가 연속되고 head위치의 값이 있으면 꽉 차있는 큐
        if(getMod(head) == getMod(tail+1) && queue[getMod(head)] != null) {
            return true;            
        }else {
            return false;
        }
    }
    
    /**
     * value 값을 size로 나눈 나머지 값을 반환
     * @param value 입력 값
     * @return 입력값을 size로 나눈 나머지 값  
     */
    private int getMod(int value) {
        return value % size;
    }
    
    /**
     * 큐를 순환하며 값들을 순차적으로 제공함
     * @param consumer 순차적으로 제공되는 값들을 처리할 FunctionInterface
     */
    public void forEach(Consumer<T> consumer) {
        for(int i = head; i <= tail; i++ ) {
            consumer.accept(queue[getMod(i)]);
        }
    }
}