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

Метод

аналогичен, но вызывает блок, чтобы выяснить «степень общности» элементов, и возвращает множество, состоящее из множеств.

Если «арность» (число аргументов) блока равна 1, то метод выполняет вызовы вида

, чтобы определить, принадлежат ли и одному подмножеству. Если «арность» равна 2, для той же цели выполняются вызовы вида .

Например, следующий блок (с «арностью» 1) разбивает множество на два подмножества, одно из которых содержит четные числа, а другое — нечетные:

Вот еще один, несколько искусственный пример. Простыми числами-близнецами называются простые числа, отличающиеся на 2 (например, 11 и 13); все прочие называются одиночными (например, 23). Следующий код разбивает множество на группы, помещая числа-близнецы в одно и то же подмножество. В данном случае применяется блок с «арностью» 2:

На мой взгляд, этот метод труден для понимания; я рекомендую пользоваться методом

, более простым и интуитивно очевидным.

Важно понимать, что класс

не всегда требует, чтобы параметр или операнд также был множеством (если вам это кажется странным, вспомните обсуждение «утипизации» в главе 1). На самом деле большая часть методов данного класса принимает в качестве параметра любой перечисляемый объект. Считайте, что так и задумано.

Есть и другие методы, которые применяются в частности к множествам (в том числе все методы из модуля

). Я не стану рассматривать здесь такие методы, как . Дополнительную информацию можно найти на сайте http://ruby-doc.org/ или в любом другом справочном руководстве.

9.2. Стеки и очереди

Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов

и , в отличие от и (впрочем, класс есть в библиотеке , которую мы еще будем рассматривать).

И все же в некотором смысле они встроены в Ruby. Ведь класс

реализует всё, что нужно для того, чтобы рассматривать его как стек или очередь. Стек организован по принципу «последним пришел, первым обслужен» (LIFO — last-in first-out). Традиционный пример — стопка подносов на подпружиненной подставке в кафетерии: подносы кладутся сверху и сверху же снимаются.

Над стеком можно выполнять ограниченный набор операций. Как минимум операции заталкивания (push) и выталкивания (pop), то есть помещения в стек и извлечения из него. Обычно также предоставляется способ проверить, пуст ли стек, и исследовать верхний элемент, не извлекая его из стека. Но никогда реализация не позволяет получить доступ к элементу в середине стека.

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

Но можно без труда определить класс

так, что к элементам можно будет обращаться только законно. И мы покажем, как это сделать.

Стоит отметить, что во многих алгоритмах стек применяется как основа элегантного рекурсивного решения. Причина станет ясна, если чуточку подумать. При вызове функции или метода параметры заталкиваются в системный стек и выталкиваются из него при возврате. Таким образом, рекурсивный алгоритм просто подменяет явно определенный пользователем стек системным. Что лучше? Зависит от того, какое значение вы придаете понятности программы, ее эффективности и другим аспектам.

Очередь организована по принципу «первым пришел, первым обслужен» (FIFO — first-in first-out). Аналогом может служить очередь за билетами в театр: вновь подходящие становятся в конец очереди, а те, кто пришел раньше, обслуживаются первыми. В программировании очереди используются реже, чем стеки.

Очереди полезны в системах реального времени, когда события нужно обрабатывать в порядке возникновения. Находят они применение и в ситуации «производитель-потребитель» (особенно в многопоточных программах и многозадачных средах). Неплохой пример — очередь к принтеру: задания на печать помещаются в один конец и ожидают, пока не будут извлечены с другого конца.

Две основные операции над очередью называются «поместить» (enqueue) и «извлечь» (dequeue). Им соответствуют методы

и в классе .

Отметим, что метод

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

На этом мы закончим введение в стеки и очереди. Самое время рассмотреть некоторые примеры.

9.2.1. Более строгая реализация стека

Мы обещали показать, как можно сделать стек защищенным от некорректного доступа. Выполняем обещание! Вот пример простого класса, который хранит внутри себя массив и управляет доступом к этому массиву. (Есть и другие способы, например делегирование, но описанная реализация проста и прекрасно работает.)