Queue

[Taehyeon-Kim]

Implement queue simply

import Foundation

// Array로 Queue 구현
public struct Queue<T> {
  private var array: [T] = []
  
  // 비어있는지 검사
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  // 개수
  public var count: Int {
    return array.count
  }
  
  // enqueue
  // 배열의 마지막에 원소를 추가하는 것이기 때문에 O(1)
  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  // dequeue
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  // 맨 앞 원소
  public var front: T? {
    return array.first
  }
}

Enqueue - Insert(Append)

• 항상 끝에 원소를 추가하기 때문에 O(1)의 시간 복잡도

Dequeue - Remove

• 첫 번째 요소를 대기열에서 빼는 작업은 항상 O(N)의 시간 복잡도 (Array를 사용했을 경우)
• 첫 번째 요소를 빼고 난 뒤 나머지 요소를 재배치 해주는 작업을 수행해야 하기 때문

Efficient queue

import Foundation

public struct EfficientQueue<T> {
  
  // 배열 요소를 비어 있는 것으로 표시해야 하기 때문에 옵셔널 타입의 요소를 저장
  public var array = [T?]()
  // 배열의 맨 앞에 있는 요소의 인덱스
  public var head = 0
  
  public init() {}
  
  public var isEmpty: Bool {
    return count == 0
  }

  public var count: Int {
    return array.count - head
  }
  
  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    guard head < array.count, let element = array[head] else { return nil }

    array[head] = nil
    head += 1

    // 사용하지 않는 공간
    let percentage = Double(head)/Double(array.count)
    
    // Array의 25% 이상이 사용되지 않으면 낭비되는 공간 제거
    if array.count > 50 && percentage > 0.25 {
      // removeFirst: 컬렉션의 시작 부분에서 지정된 수의 요소를 제거
      array.removeFirst(head)
      head = 0
    }
    
    return element
  }
  
  public var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

[Taehyeon-Kim]

• array의 removeFirst(_:) 메서드
• 인자가 0보다 크거나 같아야 하고 컬렉션의 크기를 초과하면 안 됨 -> error return