Стеки и Очереди в Swift
Что такое стек?
Примеры стека из реальной жизни
Итак, что такое стек? К счастью, вы уже знакомы со стеками. Стеки — это повседневные объекты, которые мы видим вокруг в виде стопки. Например, стопка колода карт: вы можете класть вещи на стек и снимать их со стека. Причина, по которой это так удобно в информатике, заключается в том, что действия по добавлению и удалению элементов могут быть очень быстрыми. Это операция с постоянным временем выполнения O (1), и компьютерные ученые используют это при построении таких структур данных, как стеки.
Что такое очередь?
Пример очереди из реальной жизни
Теперь, что касается очередей, они ничем не отличаются. Вы тоже уже знакомы с очередями. Вы становитесь в очередь, когда идете в магазин, вы становитесь в очередь, когда садитесь на автобус. И в информатике принцип очереди такой же: кто-то заходит в очередь, за ним следуют другие, все выстраиваются, и кто первый встал в очередь, тот первый из нее выходит. Порядок входа в очередь определяет порядок выхода из нее.
Что в них особенного?
Теперь, когда вы знаете, что такое стек и очередь, давайте рассмотрим эти понятия немного подробнее на языке компьютерных терминов. В случае со стеком, используется принцип LIFO (последним пришел — первым ушел). Термины, которые используются для добавления элементов в стек и их удаления, — это push (добавить) и pop (удалить). В реальном мире в информатике их можно увидеть в таких функциях, как переходы вперед и назад в вашем браузере или функционал отмены и повтора действий в приложениях вроде Microsoft Word или Adobe Illustrator.
Кнопка отменить в MW
С очередью все аналогично, только терминология немного другая. Здесь мы говорим о FIFO (первым пришел — первым ушел). Когда вы добавляете кого-то в очередь, это операция enqueue (постановка в очередь). А когда что-то убирается из очереди, мы называем это операцией dequeue (выход из очереди). Это очень похоже на отправку задания на печать в очередь принтера или на входные потоки для обработки. Иногда нам нужно, чтобы данные входили и выходили в том же порядке.
Очередь (FIFO)
Когда речь заходит о создании стеков и очередей, у нас есть несколько вариантов. Мы можем построить их, используя массивы или связные списки. В случае с массивом мы можем просто добавлять или удалять элементы в конце. Это будет похоже на операцию добавления. Очень быстро, O (1). И до тех пор, пока нашему массиву не нужно изменять свой размер, это будет происходить очень быстро. Со связным списком все уже знакомо: мы можем быстро добавлять и удалять элементы в начале списка. Это тоже будет операция с постоянным временем выполнения O (1). Так что стеки могут быть очень быстрыми, будь то массивы или связные списки.
Стек
История с очередями аналогична. Мы можем формировать очередь, добавляя элементы в хвост массива, что, как известно, выполняется за время O (1). В то же время, удаление элемента из начала очереди требует больше усилий, так как приходится удалять первый элемент массива, что влечёт за собой необходимость смещения всех остальных элементов на одну позицию назад, что является операцией с временем выполнения O (n). Связные списки демонстрируют похожую производительность: добавление элементов в голову списка занимает время O (1), но для удаления элемента из очереди, представленной связным списком, может потребоваться просмотр всего списка, что также занимает время O (n). Тем не менее, операции с временем выполнения O (n) по-прежнему считаются приемлемыми. Именно поэтому стеки и очереди часто реализуются с использованием массивов или связных списков.
Очередь
Несмотря на все преимущества связных списков, при работе со стеками и очередями мы зачастую отдаем предпочтение массивам. Это объясняется тем, что многие необходимые операции добавления и удаления элементов уже встроены в массивы языка Swift. Кроме того, массивы интуитивно понятны и широко используются в повседневной разработке. Давайте теперь перейдем к практике и узнаем, как можно построить стек и очередь, используя массивы.
Как Стек и Очередь выглядят в коде
Создание стеков и очередей в Swift довольно просто благодаря встроенным возможностям массивов Swift. Возьмем, к примеру, стек на Swift: его можно реализовать как обобщенный класс, что позволяет добавлять в стек объекты различных типов, будь то Int, String или даже пользовательский тип Person.
import UIKit
/*
___ _ _
/ __| |_ __ _ __| |__ ___
\__ \ _/ _` / _| / /(_-<
|___/\__\__,_\__|_\_\/__/
*/
// Last-in first-out (LIFO)
class Stack {
private var array: [T] = []
// Добавляет элемент на вершину стека - O(1)
func push(_ item: T) {
array.append(item)
}
// Удаляет последний добавленный в стек элемент - O(1)
func pop() -> T? {
array.popLast()
}
// Позволяет просмотреть элемент на вершине стека - O(1)
func peek() -> T? {
array.last
}
// Возвращает информацию о том, пуст ли стек или нет - O(1)
var isEmpty: Bool {
array.isEmpty
}
// Количество элементов - O(n)
var count: Int {
array.count
}
}
struct StackStruct {
fileprivate var array = [T]()
mutating func push(_ item: T) {
array.append(item)
}
mutating func pop() -> T? {
array.popLast()
}
var peek: T? {
array.last
}
var isEmpty: Bool {
array.isEmpty
}
var count: Int {
array.count
}
} Основная идея заключается в том, что мы используем массив для хранения элементов стека, а операции стека, такие как push и pop, просто добавляют или удаляют элементы с конца массива, что делает эти операции очень эффективными. Добавление элемента в конец массива, как правило, является операцией с постоянной временной сложностью O (1), хотя в редких случаях, когда требуется изменение размера массива, сложность может возрасти до O (n). Удаление последнего элемента также является быстрой операцией O (1).
Подробнее
https://www.raywenderlich.com/800-swift-algorithm-club-swift-stack-data-structure
Мы также можем включить в стек вспомогательные методы, такие как peek, который позволяет просмотреть верхний элемент без его удаления, а также методы isEmpty и count, которые предоставляют полезную информацию о состоянии стека.
Стек можно также построить с использованием структуры. Основное различие между классами и структурами заключается в том, что структуры в Swift обычно передаются по значению, что означает, что каждый раз, когда вы передаете структуру, создается ее копия. Это отличается от классов, объекты которых передаются по ссылке. Если вы решите использовать структуру для стека, вам может потребоваться пометить некоторые методы как mutating, поскольку они изменяют содержимое структуры. В целом, выбор между классом и структурой зависит от конкретных требований вашего проекта, но классы могут быть предпочтительнее для реализации стека из-за простоты работы с ссылочными типами данных.
С очередями ситуация аналогична стекам. Мы имеем дело с очередью, реализованной как обобщенный тип, работающую по принципу FIFO (первым пришел — первым ушел). Добавление элементов в очередь происходит очень быстро, а их удаление требует времени O (n), так как приходится сдвигать элементы массива. Мы добавляем новые элементы в конец массива, что выполняется за константное время. При удалении элемента из очереди сначала проверяем, не пуст ли массив, и если в нем что-то есть, то удаляем элемент из начала массива, что является операцией со временем O (n) из-за необходимости сдвига элементов.
/*
___
/ _ \ _ _ ___ _ _ ___ ___
| (_) | || / -_) || / -_|_-<
\__\_\\_,_\___|\_,_\___/__/
*/
// First-in first-out (FIFO)
class Queue {
private var array: [T] = []
// Добавить элемент в очередь - O(1)
func enqueue(_ item: T) {
array.append(item)
}
// Возвращает первый элемент из очереди - O(1)
func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
// Возвращает информацию о том, пуста ли очередь - O(1)
var isEmpty: Bool {
return array.isEmpty
}
// Считает количество элеменов в очереди - O(n)
var count: Int {
return array.count
}
// Позволяет просмотреть первый элемент в очереди - O(1)
func peek() -> T? {
return array.first
}
}
struct QueueStruct {
private var array: [T] = []
mutating func enqueue(_ item: T) {
array.append(item)
}
mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
func peek() -> T? {
return array.first
}
} В очередях элементы поступают с одной стороны и покидают ее с другой, сохраняя порядок их поступления, в отличие от стеков, где все действия происходят на вершине. Как и в случае со стеками, можно добавить дополнительные удобные методы для работы с очередью, и аналогично стекам, очередь также можно реализовать с помощью структуры.
Подробнее
https://www.raywenderlich.com/848-swift-algorithm-club-swift-queue-data-structure
Когда речь заходит о стеках и очередях в контексте собеседований, может возникнуть вопрос: нужно ли создавать специализированные структуры данных, или достаточно использовать обычный массив? Часто массив вполне подходит для решения задач на собеседованиях, но знание того, как построить стек или очередь, остается ценным, поскольку это фундаментальные структуры данных. Они могут встречаться в проектах и профессиональной практике, где разработчики создают абстракции на основе массивов, чтобы иметь возможность использовать функциональность стеков и очередей.
Заключение
Что нужно помнить на собеседовании:
Стек отличается своими операциями push и pop, которые выполняются за время O (1). Это делает их очень эффективными для быстрого доступа и удаления элементов, что и обуславливает популярность стеков.
Очередь также эффективна при добавлении элементов с временем выполнения O (1) для операции enqueue. Однако процесс удаления элементов из очереди, или dequeue, может занять время O (n), так как, в зависимости от реализации через массив или связный список, может потребоваться перебрать всю очередь, делая операцию удаления менее эффективной по времени.
