[Swfit] 큐(Queue) 구현하기

Queue를 구조체와 배열을 이용해 구현할 수 있습니다.

먼저 제네릭을 활용해 Queue 구조체를 정의하고, 주요 기능을 구현해보겠습니다.

 

struct Queue<T> {
    private var queue: [T] = []
    
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    var count: Int {
        return queue.count
    }
    
    var peek: T? {
    	return queue.first
    }
    
    mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }    
}

 

위 코드에서는 Queue의 기본 동작을 구현했습니다.

1. enqueue(_:): 큐의 뒤에 새 요소를 추가합니다. 시간 복잡도는 O(1)입니다.
2. dequeue(): 큐의 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 nil을 반환합니다. 배열의 첫 번째 요소를 제거할 때 나머지 요소들을 앞으로 이동시켜야 하기 때문에 시간 복잡도는 O(n)입니다.
3. peek: 큐의 첫 번째 요소를 반환하되, 요소를 제거하지는 않습니다. 시간 복잡도는 O(1)입니다.
4. isEmpty: 큐가 비어 있는지 여부를 확인합니다. 시간 복잡도는 O(1)입니다.
5. count: 큐에 있는 요소의 개수를 반환합니다. 시간 복잡도는 O(1)입니다.

이렇게 구현한 Queue는 다음과 같이 사용할 수 있습니다.

var intQueue = Queue<Int>()
intQueue.enqueue(1)
intQueue.enqueue(2)
intQueue.enqueue(3)

print(intQueue.dequeue() ?? 0)  // 출력: 1
print(intQueue.peek ?? 0)     	// 출력: 2
print(intQueue.count)           // 출력: 2
print(intQueue.isEmpty)         // 출력: false