предоставляется способ проверить, пуст ли стек, и исследовать верхний элемент, не извлекая его из стека. Но никогда реализация не позволяет получить доступ к элементу в середине стека.
Как же реализовать стек на базе массива, если к элементам массива можно обращаться в произвольном порядке, а стек таким свойством не обладает? Ответ прост. Стек — более абстрактная структура, чем массив. Он является стеком лишь до тех пор, пока мы обращаемся с ним как с таковым. В тот момент, когда вы пытаетесь обратиться к элементу недопустимым образом, стек перестает быть стеком.
Но можно без труда определить класс Stack так, что к элементам можно будет обращаться только законно. И мы покажем, как это сделать.
Стоит отметить, что во многих алгоритмах стек применяется как основа элегантного рекурсивного решения. Причина станет ясна, если чуточку подумать. При вызове функции или метода параметры заталкиваются в системный стек и выталкиваются из него при возврате. Таким образом, рекурсивный алгоритм просто подменяет явно определенный пользователем стек системным. Что лучше? Зависит от того, какое значение вы придаете понятности программы, ее эффективности и другим аспектам.
Очередь организована по принципу «первым пришел, первым обслужен» (FIFO — first-in first-out). Аналогом может служить очередь за билетами в театр: вновь подходящие становятся в конец очереди, а те, кто пришел раньше, обслуживаются первыми. В программировании очереди используются реже, чем стеки.
Очереди полезны в системах реального времени, когда события нужно обрабатывать в порядке возникновения. Находят они применение и в ситуации «производитель-потребитель» (особенно в многопоточных программах и многозадачных средах). Неплохой пример — очередь к принтеру: задания на печать помещаются в один конец и ожидают, пока не будут извлечены с другого конца.
Две основные операции над очередью называются «поместить» (enqueue) и «извлечь» (dequeue). Им соответствуют методы unpush и shift в классе Array.
Отметим, что метод unshift может использоваться в сочетании с shift при реализации массива, но никак не очереди, поскольку unshift добавляет элемент в тот же конец массива, из которого shift его удаляет. С помощью различных комбинаций этих методов можно реализовать и стек, и очередь, но рассматривать все возможные сочетания мы не будем.
На этом мы закончим введение в стеки и очереди. Самое время рассмотреть некоторые примеры.
9.2.1. Более строгая реализация стека
Мы обещали показать, как можно сделать стек защищенным от некорректного доступа. Выполняем обещание! Вот пример простого класса, который хранит внутри себя массив и управляет доступом к этому массиву. (Есть и другие способы, например делегирование, но описанная реализация проста и прекрасно работает.)
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 возвращает элемент, находящийся на вершине стека, не выталкивая его.
Нижеследующие примеры подтверждают адекватность такого определения класса.
9.2.2. Обнаружение несбалансированных скобок
В силу самой природы употребления различного вида скобок в выражениях проверить корректность написания можно с помощью стека. При открытии каждого следующего уровня вложенности скобок стек растет. Как только встречается закрывающая скобка, соответствующий элемент выталкивается из стека. Если при обнаружении закрывающей скобки в стеке ничего не оказалось или, наоборот, выражение уже закончилось, а в стеке что-то осталось, значит, выражение записано неверно.
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))'
