Queue

큐 역시 임시 데이터를 처리하기 위해 디자인된 데이터 구조다. 데이터를 처리하는 순서만 제외하면, 많은 면에서 스택과 비슷하다. 스택처럼 큐도 추상 데이터 타입이다.

극장에 줄 서 있는 사람들을 큐처럼 생각할 수 있다. 줄 맨 앞에 있는 사람이 그 줄을 떠나 가장 먼저 극장에 들어가듯이. 큐는 스택과 반대로 큐에 첫 번째로 추가된 항목이 가장 먼저 제거된다. 그래서 FIFO(First In First Out) 구조이다.

스택과 마찬가지로 큐의 제약이 존재한다.

• 데이터는 큐의 끝에만 삽입할 수 있다. (스택과 동일한 동작)
• 데이터는 큐의 앞에서만 삭제할 수 있다. (스택과 반대)
• 큐의 앞에 있는 원소만을 읽을 수 있다. (스택과 반대)

위의 그림과 같은 구조가 되는 것이다.

큐에 데이터를 삽입하는 것을 인큐(enqueue) 데이터를 추출하는것을 디큐(dequeue) 라고 한다.

다음은 큐를 구현한 코드이다.

## MyQueue.java

package com;

import java.util.List;
import java.util.ArrayList;

public class MyQueue<T> {

    private ArrayList<T> x = new ArrayList<>();
    private int out_idx = 0;

    public void enqueue(T data) {
        x.add(data);
    }

    public T dequeue() {
        T temp = x.get(0);
        x.remove(0);

        return temp;
    }
    
}

매우 간단하게 구현할 수 있다. 무조건 0번째 인덱스에서 데이터를 디큐하고, 인큐는 맨 끝에서 하면 된다.

큐를 활용한 알고리즘은 흔하게 찾아 볼 수 있다. 전화를 건 사람을 잠시 대기시킨 후 연결해주는 알고리즘, 운영체제 단에서는 프로세스를 스케쥴링하는 시스템 콜등을 예로 들 수 있겠다.

큐에 관해선 예제를 직접 만들어보진 않겠다. 다음은, 재귀적 프로그래밍에 대해 알아보자.