Swift ;; Queue 구현!

Swift에는 Queue 내장함수가 존재하지 않기 때문에 직접 Queue를 구현해서 사용해야 한다.

swift 알고리즘 문제 BFS 등을 풀 때 필요한 경우가 있다.

 

큐는, 사람들이 줄을 설 때와 같이

먼저 들어간 원소가 먼저 나오게 된다.

이를 선입선출(FIFO, First In First Out) 구조라고 한다.

 

큐의 연산은 삽입(enqueue), 삭제(dequeue), 원소 보기(peek), count(큐에 들어있는 원소의 개수), isEmpty(큐가 비었는지 여부)로 이루어져 있다.

 

• enqueue
  • 큐에 원소를 삽입하는 연산
  • 큐를 배열로 선언하고, append를 통해 삽입한다.
• dequeue
  • 큐의 원소를 삭제하는 연산
  • removeFirst()를 사용 시 O(n)의 시간복잡도를 가진다.
  • 이를 개선하기 위해, head를 옮겨가며 구현함으로써 O(1)의 시간복잡도를 가지도록 할 수 있다.
  • head가 50이 넘어가면 한 번 삭제해준다.
• peek
  • 큐의 원소를 하나 보는 연산
  • first 프로퍼티로 구현
• count
  • 큐에 들어있는 원소의 개수를 알아내는 연산
• isEmpty
  • 큐가 비었는지 아닌지를 확인하는 연산

 

---

Queue 구현 코드 - 기존

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

---

Queue 구현 코드 - 효율성 up!

struct Queue<T> {
    private var queue = [T]()
    private var head = 0
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        if isEmpty { return nil }
        
        let element = queue[head]
        head += 1
        
        if head > 50 {
            queue.removeFirst(head)
            head = 0
        }
        
        return element
    }
    
    public func peek() -> T? {
        return isEmpty ? nil : queue[head]
    }
    
    public var count: Int {
        return queue.count - head
    }
    
    public var isEmpty: Bool {
        return count <= 0 ? true : false
    }
}