Как разработчик, вы, возможно, сталкивались с концепцией стека — структуры данных, которая следует принципу «последний пришел — первый ушел» (LIFO). Стек позволяет помещать в него элементы и извлекать их в порядке, обратном их добавлению. Это может быть полезно в различных сценариях, таких как реализация функции отмены или ведение истории посещенных страниц в веб-браузере.

Существует несколько способов создания стека в Swift, каждый из которых имеет свои преимущества и недостатки. В этом руководстве мы рассмотрим три подхода: использование массива, использование связанного списка и использование класса стека.

Вариант 1: использование массива

Один из самых простых способов реализации стека — использование массива. Массивы встроены в Swift и обеспечивают быстрый доступ к элементам, но они могут быть неэффективными, когда речь идет о вставке и удалении элементов в начале или середине списка.

Чтобы построить стек с использованием массива, мы можем просто определить переменную типа [T], где T — это тип элементов, которые мы хотим хранить в стеке. Вот пример стека, в котором хранятся целые числа:

var stack: [Int] = []

Чтобы добавить элемент в стек, мы можем использовать метод append:

stack.append(5)
stack.append(3)
stack.append(8)

Чтобы удалить верхний элемент из стека, мы можем использовать метод popLast:

if let last = stack.popLast() {
    print(last) // prints 8
}

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

if let top = stack.last {
    print(top) // prints 3
}

Вариант 2. Использование связанного списка

Другой вариант построения стека — использование связанного списка. Связанные списки — это тип структуры данных, состоящей из последовательности узлов, где каждый узел хранит значение и ссылку на следующий узел в списке. Связанные списки более эффективны, чем массивы, когда дело доходит до вставки и удаления элементов, но они менее эффективны для доступа к элементам по индексу.

Чтобы построить стек, используя связанный список, мы можем определить класс или структуру, представляющую узел в списке. Вот пример класса узла, в котором хранится целочисленное значение:

class Node {
    let value: Int
    var next: Node?
    
    init(value: Int) {
        self.value = value
    }
}

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

class Stack {
    private var top: Node?
    
    func push(value: Int) {
        let newNode = Node(value: value)
        newNode.next = top
        top = newNode
    }
    
    func pop() -> Int? {
        let currentTop = top
        top = top?.next
        return currentTop?.value
    }
}

Чтобы использовать стек, мы можем создать экземпляр и вызвать методы push и pop:

let stack = Stack()
stack.push(5)