Как разработчик, вы, возможно, сталкивались с концепцией стека — структуры данных, которая следует принципу «последний пришел — первый ушел» (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)