Освоение структур данных в Ruby — Стеки

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

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

Виртуальные машины на основе стека, такие как YARV (виртуальная машина Ruby), используют стеки для хранения и оценки инструкций байт-кода.

Давайте посмотрим, как растет стек, когда мы сохраняем (вталкиваем) в него элементы.

push(1) push(2) push(3) 
--- --- ---
 1   2   3 
--- --- --- 
 1   2 
--- --- 
 1 
---

Теперь давайте посмотрим, как он сжимается, когда мы удаляем (извлекаем) из него элементы.

pop pop pop
--- --- --- 
 3   2   1
--- --- --- 
 2   1
--- --- 
 1 
---

Интерфейс стеков

Интерфейс для стеков похож на хвосты в том смысле, что у них не так много методов, что приятно, потому что интерфейс прост в освоении и его трудно не использовать.

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

Интерфейс стека. Имена методов, резюме и сложность.

Детали реализации

Элементы в стеке представлены узлами, которые содержат два атрибута:

• Значение, которое содержит текущий узел.
• Указатель на следующий узел в стеке.

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

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

Далее следует краткое описание каждого метода, его сложности и исходного кода.

Инициализировать

Этот метод является конструктором стека. Он создает пустой стек, устанавливает головной узел в nil и длину стека в 0.

Сложность этого метода составляет O(1).

def initialize
  self.head = nil
  self.length = 0
end

Толкать

Создает новый узел для вставки значения в стек. Новый узел перемещает элемент, стоящий во главе списка, и становится новым главой списка.

Поскольку стек хранит указатели на его голову и хвост, сложность этого метода составляет O(1).

def push data
  node = Node.new data
  if length == 0
    self.tail = node
  end

  node.next = self.head
  self.head = node
  self.length += 1
end

Поп

Удаляет элемент из стека. Как и в случае с очередями, удаление выполняется просто, потому что оно всегда происходит в начале стека.

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

Сложность этого метода составляет O(1).

def pop
  return nil unless self.length > 0
  self.head = self.head.next
  self.tail = nil if self.length == 1
  self.length -= 1
end

заглянуть

Возвращает узел, находящийся во главе стека, не удаляя его, или nil, если стек пуст.

Поскольку pop не возвращает удаленный элемент, peek — это путь, если вам нужно что-то сделать с этим элементом.

Сложность этого метода составляет O(1).

def peek
  self.head
end

чистый

Извлекает все элементы из стека.

Сложность этого метода составляет O(n).

def clear
  while self.peek
    pop
  end
end

Каждый

Этот метод просматривает стек, возвращая по одному, пока не достигнет последнего элемента.

Сложность получения следующего элемента в стеке составляет O (1). Сложность получения всего стека составляет O(n).

def each
  return nil unless block_given?
  current = self.head
  while current
    yield current
    current = current.next
  end
end

Распечатать

Распечатайте содержимое стека, пройдя его элементы.

Сложность этого метода составляет O(n).

def print
  if self.length == 0
    puts "empty"
  else
    self.each { |node| puts node.data }
  end
end

Когда использовать стеки

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

Стеки отлично подходят для управления последовательностями инструкций, анализа выражений и определения приоритета операторов; назвать несколько.

Так что это в значительной степени о стеках. Я надеюсь, что вам понравилось!

В следующий раз мы рассмотрим Хэш-таблицы.

Спасибо за чтение!

PS: если вы являетесь участником программы Kindle Unlimited, вы можете прочитать немного отполированную версию этой серии бесплатно на вашем устройстве Kindle.

Структуры данных с нуля — Ruby Edition.