Более удачным решением таких проблем может оказаться ин кап суля- ция, то есть обертывание, реализаций стеков в интерфейсы с помощью инструментов Python — для организации повторного использования программного кода. Пока клиенты продолжают использовать интерфейсы, мы легко можем изменить реализацию этих интерфейсов произвольным образом и избежать необходимости изменять все инструкции обращения к ним. Начнем с реализации стека в виде модуля, содержащего список Python вместе с функциями, действующими над ним. В примере 18.1 представлена одна из возможных реализаций.
Пример 18.1. PP4E\Dstruct\Basic\stack1.py
"модуль реализации стека"
stack = [] # при первом импортировании
class error(Exception): pass # локальные исключения, stack1.error
def push(obj):
global stack # ‘global’, чтобы иметь возм. изменять
stack = [obj] + stack # добавить элемент в начало
def pop():
global stack if not stack: raise error(‘stack underflow‘) # возбудить локальное исключение top, *stack = stack # удалить элемент в начале
return top
def top(): if not stack: # возбудить локальное исключение
raise error(‘stack underflow’) # или позволить возбудить IndexError return stack[0]
def empty(): return not stack # стек пуст?
def member(obj): return obj in stack # элемент имеется в стеке?
def item(offset): return stack[offset] # элемент стека по индексу
def length(): return len(stack) # количество элементов на стеке
def dump(): print(‘<Stack:%s>’ % stack)
Этот модуль создает объект списка (stack) и экспортирует функции для управления доступом к нему. Стек объявляется глобальным в функциях, которые его изменяют, но не в тех, которые только читают его. В модуле также объявлен объект ошибки (error), с помощью которого можно перехватывать исключения, возбуждаемые локально в этом модуле. Некоторые ошибки стека являются встроенными исключениями: метод item вызывает IndexError при выходе индексов за пределы списка.
Большинство функций в модуле stack просто передают выполнение операции встроенному списку, представляющему стек. В действительности модуль служит просто оболочкой, в которую заключен список Python. Но этот дополнительный слой логики интерфейса обеспечивает независимость клиентов от фактической реализации стека, поэтому в дальнейшем можно будет изменить стек, не затрагивая его клиентов.
Как всегда, лучший способ разобраться в таком программном коде — посмотреть на него в деле. Ниже приводится листинг интерактивного сеанса, иллюстрирующий интерфейсы модуля, — он реализует стек, способный принимать произвольные объекты Python:
C:\…\PP4E\Dstruct\Basic> python
> >> import stack1
> >> stack1.push(‘spam’)
> >> stack1.push(123)
> >> stack1.top()
123
> >> stack1.stack
[123, ‘spam’]
> >> stack1.pop()
123
> >> stack1.dump()
<Stack:[‘spam’]>
> >> stack1.pop()
‘spam’
> >> stack1.empty()
True
> >> for c in ‘spam’: stack1.push(c)
…
> >> while not stack1.empty():
… print(stack1.pop(), end=’ ‘)
…
m a p s
>>>
> >> stack1.pop()
stack1.error: stack underflow
Другие операции действуют аналогично, но главное, на что здесь нужно обратить внимание, — все операции со стеком являются функ циями модуля. Например, можно совершить обход стека, но нужно использовать счетный цикл и вызывать функцию обращения по индексу (item). Ничто не мешает клиенту обращаться (и даже изменять) стек stack1. stack непосредственно, но при этом теряется весь смысл таких интерфейсов, как показано ниже:
> >> for c in ‘spam’: stack1.push(c)
…
> >> stack1.dump()
<Stack:[‘m’, ‘a’, ‘p’, ‘s’]>
>>>
> >> for i in range(stack1.length()):
… print(stack1.item(i), end=’ ‘)
m a p s >>>
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
