@store.first
end
def length
@store.length
end
def empty?
@store.empty?
end
end
Отметим, что класс Queue имеется в библиотеке thread для поддержки многопоточных программ. Имеется даже вариант SizedQueue для организации очереди ограниченного размера.
В упомянутых классах методы имеют короткие имена: enq и deq. У них есть также синонимы push и pop, что лично мне кажется неоправданным. Это структура данных FIFO, а не LIFO, то есть именно очередь, а не стек.
Разумеется, класс Queue в библиотеке thread.rb безопасен относительно потоков. Если вы хотите реализовать такой же класс Stack, рекомендую взять Queue в качестве отправной точки. Потребуется внести не так много изменений.
В первом издании книги был длинный пример, демонстрирующий работу с очередями. Но, как и некоторые примеры, касающиеся стеков, он был исключен ради экономии места.
9.3. Деревья
В информатике идея дерева считается интуитивно очевидной (правда, изображаются они обычно с корнем наверху, а листьями снизу). И немудрено, ведь в повседневной жизни мы постоянно сталкиваемся с иерархическими данными: генеалогическое древо, организационная схема компании, структура каталогов на диске.
Терминология, описывающая деревья, богата, но понять ее легко. Элементы дерева называются
Нас будут интересовать в основном двоичные деревья, хотя в принципе узел может иметь произвольное число детей. Мы покажем, как создавать дерево, добавлять в него узлы и выполнять обход. Рассмотрим также некоторые реальные задачи, при решении которых используются деревья.
Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.
9.3.1. Реализация двоичного дерева
Ruby позволяет реализовать двоичное дерево разными способами. Например, хранить значения узлов можно в массиве. Но мы применим более традиционный подход, характерный для кодирования на С, только указатели заменим ссылками на объекты.
Что нужно для описания двоичного дерева? Понятно, что в каждом узле должен быть атрибут для хранения данных. Кроме того, в каждом узле должны быть атрибуты для ссылки на левое и правое поддерево. Еще необходим способ вставить новый узел в дерево и получить хранящуюся в дереве информацию. Для этого нам потребуется два метода.
В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс Tree.
В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод insert будет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор traverse, который обходит дерево в том же порядке.
class Tree
attr_accessor :left
attr_accessor :right
attr_accessor :data
def initialize(x=nil)
@left = nil
@right = nil
@data = x
end
def insert(x)
list = []
if @data == nil
@data = x
elsif @left == nil
@left = Tree.new(x)
elsif @right == nil
@right = Tree.new(x)
else
list << @left
list << @right
