Что такое очередь?

список элементов данных, команд и т. д., хранящихся таким образом, чтобы их можно было извлечь в определенном порядке, обычно в порядке вставки.

Итак, без определения, как мы можем его реализовать? Что ж, мы могли бы создать оболочку вокруг списка и реализовать метод, который нам нужен, вот так:

class Queue {

    private var items: [Int] = []
    
    var isEmpty: Bool {
        get {
            return items.isEmpty
        }
    }
    
    func add(value: Int) {
        items.append(value)
    }
    
    func peek() -> Int? {
        return items[0]
    }
    
    func poll() -> Int? {
        if items.isEmpty { return nil }
        let value = items[0]
        items.remove(at: 0)
        return value
    }
}

Достаточно просто написать, а в чем проблема? Во-первых, он жестко запрограммирован для работы только с целыми числами (но об этом мы можем побеспокоиться позже). Проблема в том, что при опросе наша временная сложность равна O (n), а преимущество очереди в том, что она должна быть O (1). Сложность от https://developer.apple.com/documentation/swift/array/1641390-remove

Сложность: O (n), где n - длина массива.

Как мы можем это реализовать?

Я буду использовать связанный список для реализации очереди, потому что он даст нам O (1) операции вставки, просмотра и опроса.

Сначала подумайте, что нам нужен класс узла.

class Node<T> {
    var value: T
    var next: Node?
    var prev: Node?

    init(value: T) {
        self.value = value
    }
}

Мы объявляем узел со значением типа T, где T - любое значение, которое мы хотим. Мы будем использовать дженерики, чтобы нам нужно было объявить только один класс Node, и он будет работать для любого типа, будь то Int, String, User и т. Д.

Теперь давайте создадим класс Queue, нам потребуются следующие методы

var isEmpty: Bool
func add(value: T)
func peek() -> T?
func poll() -> T?

Это все, что нам нужно для создания простого класса Queue, но прежде чем мы объявим функции, давайте проследим за элементами в нашей Queue, и для этого мы будем использовать узел головы и хвоста, например

private var head: Node<T>?
private var tail: Node<T>?

Мы объявляем их частными, потому что о них должен знать только класс.

var isEmpty: Bool

var isEmpty: Bool {
    get {
       return head == nil
    }
}

func add (значение: T)

Добавляем значение в очередь

func add(value: T) {
    if head == nil {
        let node = Node(value: value)
        head = node
        tail = node
        head?.next = tail
        tail?.prev = head
    } else {
        let curr = tail
        tail = Node(value: value)
        curr?.next = tail
        tail?.prev = curr
    }
}

Это самая беспорядочная из функций.
1. Первая часть проверяет, является ли голова равной нулю, и запускает и голову, и хвост.
2. Мы добавляем элемент, превращая его в новый хвост и сохраняя цепочку, идущую до головы.

func peek () - ›T?

Получаем следующий элемент в очереди

func peek() -> T? {
    return head?.value
}

func poll () - ›T?

Мы получаем значение следующего элемента, который нужно удалить, удаляем значение и, наконец, возвращаем значение

func poll() -> T? {
    if let value = head?.value {
        head = head?.next
        return value
    }
    return nil
}

Все вместе

class Node<T> {
    var value: T
    var next: Node?
    var prev: Node?

    init(value: T) {
        self.value = value
    }
}

class Queue<T> {

    private var head: Node<T>?
    private var tail: Node<T>?

    var isEmpty: Bool {
        get {
            return head == nil
        }
    }

    func add(value: T) {
        if head == nil {
            let node = Node(value: value)
            head = node
            tail = node
            head?.next = tail
            tail?.prev = head
        }  else {
            let curr = tail
            tail = Node(value: value)
            curr?.next = tail
            tail?.prev = curr
        }
    }

    func peek() -> T? {
        return head?.value
    }

    func poll() -> T? {
        if let value = head?.value {
            head = head?.next
            return value
        }
        return nil
    }
}

Тестирование

let q1 = Queue<Int>()
q1.add(value: 1)
q1.add(value: 2)
q1.add(value: 3)
q1.add(value: 4)
q1.add(value: 5)
q1.poll() // 1
q1.poll() // 2
q1.poll() // 3
q1.poll() // 4
q1.add(value: 6)
q1.isEmpty // false
q1.peek() // 5
q1.poll() // 5
q1.poll() // 6
q1.poll() // nil
q1.isEmpty // true
let q2 = Queue<String>()
q2.add(value: "Hello")
q2.peek() // "Hello"
q2.add(value: "World!")
q2.poll() // "Hello"
q2.add(value: "Hello!")
q2.poll() // "World!"
q2.poll() // "Hello!"
q2.poll() // nil
q2.isEmpty // true

Спасибо, что заглянули