Стэк

Январь 11, 2019  · 2 мин. чтения

Стек (Stack)


Стек (англ. stack – стопка; читается стэк) – абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in – first out, «последним пришёл – первым вышел»). [3] Данная особенность означает, что доступ возможен только к последнему добавленному элементу (Рисунок 3). В отличие от массива, стек не позволяет получить доступ к произвольному элементу. Допустимо только добавление или удаление элементов стека с помощью специальных методов. Также следует отметить, что у стека нет итератора.

Рисунок 3 – Пример стека


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

В стеке предусмотрены классические методы, которые позволяют взаимодействовать и управлять элементами стека.

  1. Операция добавления элемента (push).
  2. Операция удаления элемента (pop).
  3. Операция считывания верхнего элемента стека (peek).
  4. Операция проверки стека на наличие в нем элементов (isEmpty).

Ниже приведена реализация стека и его методов на языке программирования Swift.

import UIKit

struct stack {
    var array: [String] = []

    mutating func push(element: String) {
        array.insert(element, at: 0)
    }

    mutating func pop() -> String {
        if array.count == 0 {
            fatalError("The stack is empty")
        } else {
            return array.removeFirst()
        }
    }

    func peek() -> String {
        guard let firstElement = array.first else { fatalError("The stack is empty") }
        return firstElement
    }

    func isEmpty() -> Bool {
        if array.isEmpty {
            return true
        } else {
          return false
        }
    }
}

var testStack = stack()

testStack.isEmpty()

testStack.push(element: "Дерево")
testStack.push(element: "Лист")
testStack.push(element: "Цветок")
testStack.push(element: "Куст")

print(testStack)

testStack.isEmpty()

testStack.pop()

print(testStack)

testStack.peek()
Рисунок 4 – Результаты выполнения операций над стеком