[메이드 인 스위프트] 자료구조 - 큐 Queue 구현해보기

개요

지난 Stack과 유사하게 기본적인 Queue를 구현하면서 자료구조 개념을 익혀보자

이번에도 함수형 & 제네릭으로 작성해봤다.

 

---

코드 구현

public struct KJQueue<Element> {
    private let queue: [Element]

    public var count: Int { queue.count }
    public var isEmpty: Bool { queue.isEmpty }
    public var peek: Element? { queue.first }

    // MARK: Initializer
    public init(_ queue: [Element] = []) {
        self.queue = queue
    }

    public func enqueue(_ value: Element) -> KJQueue {
        return KJQueue(queue + [value])
    }

    public func dequeue() -> KJQueue {
        guard !isEmpty else { return self }
        return KJQueue(Array(queue.dropFirst()))
    }

    public func dequeueValue() -> Element? {
        return queue.first
    }
}

// MARK: Equatable
extension KJQueue: Equatable where Element: Equatable {
    public static func == (lhs: KJQueue<Element>, rhs: KJQueue<Element>) -> Bool {
        lhs.queue == rhs.queue
    }
}

// MARK: CustomStringConvertible
extension KJQueue: CustomStringConvertible {
    public var description: String {
        "Current KJQueue: \(queue)"
    }
}

 

실행 코드

var queue = KJQueue<Int>()
print(queue) // Current KJQueue: [], Count: 0, Is Empty: true

queue = queue.enqueue(1)
queue = queue.enqueue(2)
queue = queue.enqueue(3)
print(queue) // Current KJQueue: [1, 2, 3], Count: 3, Is Empty: false

// Dequeue 테스트
let dequeuedValue = queue.dequeueValue()
print("Dequeued Value: \(dequeuedValue ?? -1)") // Dequeued Value: 1

queue = queue.dequeue()
print(queue) // Current KJQueue: [2, 3], Count: 2, Is Empty: false

// Equatable 테스트
let queue1 = KJQueue([1, 2, 3])
let queue2 = KJQueue([1, 2, 3])
print(queue1 == queue2) // true

 

구현 후 느낀점

원형 큐, 연결리스트 큐.. 등등 할 게 많은데 일단 기본적인 큐부터 해봤다.

이 또한 지금 구조는 메모리 관점에서는 많이 비효율적이다.

함수형에 의해 Enqueue든 Dequeue든 전체 복사를 하고 새로 객체를 반환해주기 때문이다.