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

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

Очередь организована по принципу «первым пришел, первым обслужен» (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 и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.

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