Программирование на языке Ruby

  @store,shift
  end

  def peek
  @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. Деревья

Я не увижу никогда, наверное, Поэму столь прекрасную как дерево. Джойс Килмер, «Деревья» [11]

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

11

Пер. Я. Фельдмана. — Прим. ред.

Терминология, описывающая деревья, богата, но понять ее легко. Элементы дерева называются узлами; верхний или самый первый узел называется корневым или корнем. У узла могут быть потомки, расположенные ниже него, а непосредственные потомки называются детьми или дочерними узлами. Узел, не имеющий потомков, называется листовым или просто листом. Поддерево состоит из некоторого узла и всех его потомков. Посещение всех узлов дерева (например, с целью распечатки) называется обходом дерева.

Нас будут интересовать в основном двоичные деревья, хотя в принципе узел может иметь произвольное число детей. Мы покажем, как создавать дерево, добавлять в него узлы и выполнять обход. Рассмотрим также некоторые реальные задачи, при решении которых используются деревья.

Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.

9.3.1. Реализация двоичного дерева

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

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

В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс Tree.

В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод insert будет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор traverse, который обходит дерево в том же порядке.

Листинг 9.1. Вставка и обход дерева в ширину

 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
  loop do
  node = list.shift
  if node.left == nil
  node.insert(x)
  break
  else
  list << node.left
  end
  if node.right == nil
  node.insert(x)
  break
  else
  list << node.right
  end
  end
  end
  end

  def traverse
  list = []
  yield @data
  list << @left if @left != nil
  list << @right if @right != nil
  loop do
  break if list.empty?
  node = list.shift
  yield node.data
  list << node.left if node.left != nil
  list << node.right if node.right != nil
  end