[Data Structures] Queue - Array based implementation

Queue

Queue는 아주 흔한 개념이다. 편의점 알바할 때 가장 많이 썼던 말인 ‘선입선출’…. 먼저 들어온 게 먼저 나간다는 뜻이다. 실제로 Queue는 FIFO의 형태를 가진다고 말하는데, 이것은 First in First out 이란 문장의 약자다. (선입선출..!)

Common Operations

Queue를 구현하는 방법은 여러가지가 있다.

1. Array로 구현하는 방법
2. Double Linked List로 구현하는 방법
3. 링버퍼로 구현하는 방법
4. Stack으로 구현하는 방법

여러가지 방법으로 구현한 Queue를 확인해 볼텐데 우선은 Queue에서 구현해야 하는 항목들을 먼저 프로토콜로 정의해둔다.

protocol Queue {
    associatedtype T
    
    mutating func enqueue(_ element: T) -> Bool
    mutating func dequeue() -> T?
    
    var isEmpty: Bool { get }
    var peek: T? { get }
}

Queue 프로토콜을 정의할 때 Generic Protocol을 정의해서 어떤 타입이든 받아서 사용할 수 있도록 만들었다.

• enqueue: 어떤 값을 Queue의 가장 뒤에 넣는 메서드
• dequeue: Queue의 가장 앞의 값을 제거하는 메서드
• isEmpty: Queue가 비어있는지 확인
• peek: Queue의 가장 앞 부분의 요소를 확인

Array로 Queue 구현해보기

Array로 Queue를 구현해보자. 우선 QueueArray 라는 구조체를 생성해 앞에 만들어두었던 Queue 프로토콜을 채택한다.

struct QueueArray<T>: Queue {
    private var array: [T] = []
}

구조체 내부에서 사용할 array를 하나 선언해두었다. 이제 Queue를 채택했으니 필요한 메서드들을 마저 구현한다.

isEmpty, peek 구현

    var isEmpty: Bool {
        array.isEmpty
    }

    var peek: T? {
        array.first
    }

• isEmpty는 배열이 비었는지를, peek은 배열의 가장 첫 요소를 반환한다.

enqueue 구현

    mutating func enqueue(_ element: T) -> Bool {
        array.append(element)
        return true
    }

배열로 구현하는 Queue에서 enqeue를 구현하는것은 간단하다. array의 가장 마지막에 요소를 추가하는 것이기 때문에 append를 사용하면 된다.

이때 enqueue하는 시간복잡도는 O(1)이다. 왜냐하면 배열은 맨 뒤에가 비어있기 때문이다.(라고한다.) 할당된 만큼의 배열이 꽉 차있는 상태에서 새로운 요소가 들어오면 그때서야 배열의 사이즈가 재조정된다.

리사이징은 O(n)인 동작인데, 리사이징을 하는 작업은 새로운 크기의 배열이 생겨나고, 그 배열에 원래 있던 배열의 요소를 옮겨가는 일을 하기 때문이다. 하지만 배열은 리사이징이 필요할 때마다 아마 두배씩 크기가 늘어나기 때문에(?) 자주 일어나는 일이 아니고 그래서 enqueue의 복잡도를 O(1)로 생각한다.

dequeue

dequeue는 맨 앞에서 요소를 빼오는 동작이다. 배열이 비어있다면 nil을 반환하고 값이 있다면 removeFirst를 사용해 배열에서 값을 제거한다.

    mutating func dequeue() -> T? {
        return isEmpty ? nil : array.removeFirst()
    }

dequeue는 항상 O(n)의 시간복잡도가 되는데, 이것은 배열의 맨 앞 요소를 제거하기 때문이다. 배열의 맨 앞 요소를 제거하면 나머지 요소들을 한칸씩 앞으로 shift해주어야 하기 때문에 O(n)으로 표기한다.

실행 결과 및 복잡도 정리

• 실행 결과

• 복잡도