[자료구조] 큐(QUEUE)

큐(Queue)란?

서브웨이에 샌드위치를 사려고 사람들이 줄을 서고 있다. 이때 이 사람들이 서있는 줄을 영어로 뭐라 표현할까? 바로 큐(queue) 이다.

 

5명의 사람이 샌드위치를 사려고 기다리고 있다고 가정할때, 샌드위치를 가장 먼저 살 수 있는 사람은 큐(queue) 의 맨 앞 (front) 첫번째 사람일 것이고, 마지막으로 샌드위치를 구매 할 수 있는 사람은 가장 늦게 온 5번째 사람일 것이다. 또한 구매가 끝난 첫번째 사람은 샌드위치를 들고 큐(queue) 를 벗어날 것이고, 만약 새로운 사람이 샌드위치를 구매하려 왔다면 마지막 다섯번째 사람 뒤 (rear) 에 줄을 서야 할 것이다.

 

Queue 역시 이 경우와 같은 선입선출(First in, First Out)방식의 자료구조라고 할 수 있다.

큐의 특징

위 예시에서 언급한 바와 같이 샌드위치를 구매한 후 사람들이 빠져나가는 곳은 큐의 맨 앞이 되고, 새로운 사람이 줄을 서는 곳은 큐의 맨 뒤가 된다. 또한 가장 마지막에 온 사람이 큐의 맨앞에 설 수가 없고, 가장 나중에 줄에 선 사람이 앞의 사람들을 무시하면서 구매를 먼저하고 큐를 빠져 나갈 수도 없다.

 

이처럼 queue에서도 한쪽 끝에서는 삭제 작업만 이루어지며, 다른쪽 끝에서는 삽입 작업만이 이루어진다. 또한 원소가 들어온 순서대로 큐를 빠져나가게 된다.

 

이때 삭제연산만이 이루어 지는 곳을 프론트(front: 줄의 맨 앞)라고 하며, 삽입연산만 이루어지는 곳을 리어(rear: 줄의 맨 뒤)라고 한다. 나아가 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue: 사람들이 줄을 서는 것), 프론트에서 이루어지는 삭제연산을 디큐(deQueue: 사람들이 줄을 빠져 나가는 것)라고 한다.

Swift에서 큐 구현하기 (Array 기반)

struct CalculatorItemQueue<T> {
    private var queue: [T] = []
    // 사람들이 서 있는 줄을 말함
    mutating func enqueue(data: T) {
        list.append(data)
    }
    // 샌드위치를 사러 온 사람이 맨 뒤에 줄을 서는 것
    mutating func dequeue() -> T? {
        list.removeFirst()
    }
    // 샌드위치를 구매 완료한 맨 앞의 사람의 줄을 떠나는 것
    mutating func removeAll() {
        list.removeAll()
    }
    // 구현 필수 조건 아님
}