Queue.swift

public class Queue<T> {
  public private(set) var size: Int = 0
  private var head: QueueNode<T>? = nil
  private var tail: QueueNode<T>? = nil
  
  public func enqueue(_ value: T) {
    let newTail = QueueNode(value: value)
    if let oldTail = tail {
      newTail.prev = oldTail
      oldTail.next = newTail
    } else {
      head = newTail
    }
    tail = newTail
    size += 1;
  }
  
  public func dequeue() -> T? {
    guard let oldHead = head else { return nil }
    let value = oldHead.value
    if let newHead = oldHead.next {
      newHead.prev = nil
      head = newHead
    } else {
      head = nil
    }
    oldHead.next = nil
    size -= 1
    return value
  }
  
  public var peek: T? {
    return head?.value
  }
  
  public var isEmpty: Bool {
    return head == nil
  }
  
  public func clear() {
    head = nil
    tail = nil
    size = 0
  }
}

private class QueueNode<T> {
  var value: T
  var next: QueueNode<T>?
  weak var prev: QueueNode<T>?
  
  public init(value: T) {
    self.value = value
  }
}