Что такое очередь?
список элементов данных, команд и т. д., хранящихся таким образом, чтобы их можно было извлечь в определенном порядке, обычно в порядке вставки.
Итак, без определения, как мы можем его реализовать? Что ж, мы могли бы создать оболочку вокруг списка и реализовать метод, который нам нужен, вот так:
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
Спасибо, что заглянули