1.3.38.md

Develop implementation of GeneralizedQueue used linked list and resizable array. It must support delete(at:) method.

Linked List

struct LinkedListGeneralizedQueue<T> {
    private let linkedList = LinkedList<T>()

    mutating func dequeue() -> T? {
        return linkedList.removeHead()?.value
    }

    mutating func enqueue(_ value: T) {
        linkedList.appendTail(value)
    }

    mutating func delete(at index: Int) -> T? {
        return linkedList.remove(at: index)?.value
    }
}

Resizable Array

struct ArrayGeneralizedQueue<T> {
    private var array = Array<T?>(repeating: nil, count: 1)
    private var headIndex = 0
    private var tailIndex = 0
    private var count: Int {
        return tailIndex - headIndex
    }

    mutating func dequeue() -> T? {
        guard count > 0 else { return nil }

        defer {
            array[headIndex] = nil
            headIndex += 1
            resizeIfNeed()
        }

        return array[headIndex]
    }

    mutating func enqueue(_ value: T) {
        array[tailIndex] = value
        tailIndex += 1
        resizeIfNeed()
    }

    mutating private func resizeIfNeed() {
        if tailIndex >= array.count {
            resizeTo(size: count * 2)
        } else if count <= array.count / 4 {
            resizeTo(size: array.count / 2)
        }
    }

    mutating private func resizeTo(size: Int) {
        var newArray = Array<T?>(repeating: nil, count: size)
        newArray[0..<count] = array[headIndex..<tailIndex]
        array = newArray
        tailIndex = count
        headIndex = 0
    }

    mutating func delete(at index: Int) -> T? {
        guard array.count > index else { return nil }
        defer {
            tailIndex -= 1
            resizeIfNeed()
        }

        return array.remove(at: index)
    }
}