220310Queue.md

TIL 220310Queue

🔥학습 내용

Queue

• FIFO 형태의 자료구조

struct Queue<Element> {
    private var queue = [Element]()

    var isEmpty: Bool {
        return queue.isEmpty
    }

    var count: Int {
        return queue.count
    }

    var front: Element? {
        return queue.first
    }

    mutating func enqueue(_ element: Element) {
        queue.append(element)
    }

    mutating func dequeue() -> Element? {
        isEmpty ? nil : queue.removeFirst()
    }
}
    
var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(20)
queue.dequeue()
print(queue)
    

• 이러한 경우 dequeue에서 element들이 하나씩 당겨지는 과정때문에 O(n)이 됨.
• 따라서 아래와 같이 개선이 가능

struct Queue<Element> {
    private var queue = [Element?]()
    private var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return queue.count - head
    }

    var front: Element? {
        isEmpty ? nil : queue[head]
    }

    mutating func enqueue(_ element: Element) {
        queue.append(element)
    }

    mutating func dequeue() -> Element? {
        guard head < queue.count, let element = queue[head] else {
            return nil
        }

        queue[head] = nil
        head += 1

        let percentage = Double(head) / Double(queue.count)
        if queue.count > 50 && percentage > 0.25 {
            queue.removeFirst(head)
            head = 0
        }

        return element
    }
}

• queue[head]를 nil로 변경하고, head를 증가시켜 포인트를 이동
• dequeue된 element를 적정한 때에 삭제시켜주는 작업을 추가해서 낭비된 공간을 제거
• 따라서 이전과 같이 dequeue할 때 앞으로 당겨주는 작업이 없어지면서 O(1)이 됨

---

• 참고
  • swift-algorithm-club/Queue