Хэл Фултон - Программирование на языке Ruby

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

Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов Stackи Queue, в отличие от Arrayи Hash(впрочем, класс Queueесть в библиотеке thread.rb, которую мы еще будем рассматривать).

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

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

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

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

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

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

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

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

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

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

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

class Stack

def initialize

@store = []

end

def push(x)

@store.push x

end

def pop

@store.pop

end

def peek

@store.last

end

def empty?

@store.empty?

end

end

Мы добавили одну операцию, которая для массивов не определена; метод peekвозвращает элемент, находящийся на вершине стека, не выталкивая его.

Нижеследующие примеры подтверждают адекватность такого определения класса.

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

def paren_match(str)

stack = Stack.new

lsym = "{I(<"

rsym = "}])>"

str.each_byte do |byte|

sym = byte.chr

if lsym.include? sym

stack.push(sym)

elsif rsym.include? sym

top = stack.peek

if lsym.index(top) != rsym.index(sym)

return false

else

stack.pop

end

# Игнорируем символы, отличные от скобок...

end

end

# Убедимся, что стек пуст...

return stack.empty?

end

str1 = "(((a+b))*((c-d)-(e*f))"

str2 = "[[(a-(b-c))], [[x,y]]]"

paren_match str1 # false

paren_match str2 # true

Наличие вложенности естественным образом наводит на мысль о применении стека. Чуть сложнее распознать несбалансированные теги в HTML- или XML-документе. Лексемы состоят из нескольких символов, но логическая структура задачи остается той же самой. Вот еще типичные примеры задач, требующих стека: преобразование выражений из инфиксной формы в постфиксную (и наоборот), вычисление постфиксного выражения (как делается в виртуальной машине Java и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.

В качестве примера изоморфизма, существующего между стеком и рекурсией, рассмотрим классическую задачу о Ханойской башне.

По легенде где-то далеко на востоке существует старинный храм. Обитающие в нем монахи заняты решением единственной задачи: перемещением дисков с одного шеста на другой с соблюдением определенных правил. Первоначально на первом шесте было 64 диска. Когда все диски будут перемещены, настанет конец света.