В Python для реализации стека часто достаточно простого списка: так как списки могут изменяться непосредственно, это позволяет добавлять или удалять элементы с начала (слева) или с конца (справа). В табл. 18.1 приводятся различные встроенные операции, которые могут использоваться для реализации стека на основе списка Python, в зависимости от того, является ли «вершина» стека первым или последним узлом списка. В этой таблице строка ‘b’ является верхним элементом стека.
Табли ца 18.1. Сте ки в ви де спи сков
|
Операция |
Вершина в конце списка |
Вершина в начале списка |
Вершина в начале списка |
|
New |
stack=[‘a’, ‘b’] |
stack=[‘b’, ‘a’] |
stack=[‘b’, ‘a’] |
|
Push |
stack.append(‘c’) |
stack.insert(0,’c’) |
stack[0:0]=[‘c’] |
|
Pop |
top = stack[-1]; |
top = stack[0]; |
top = stack[0]; |
|
|
del stack[-1] |
del stack[0] |
stack[:1] = [] |
Интересно отметить, что со временем в языке Python появился еще более удобный метод pop списков, предназначенный в паре с методом append для реализации стеков и других распространенных структур данных, таких как очереди, что привело к появлению еще более простых способов реализации, перечисленных в табл. 18.2.
Табли ца 18.2. Сте ки в ви де спи сков, аль тер на тив ные реа ли за ции опера ций
|
Операция |
Вершина в конце списка |
Вершина в начале списка |
|
New |
stack=[‘a’, ‘b’] |
stack=[‘b’, ‘a’] |
|
Push |
stack.append(‘c’) |
stack.insert(0,’c’) |
|
Pop |
top = stack.pop() |
top = stack.pop(O) |
По умолчанию метод pop извлекает последний элемент со смещением -1, и затем удаляет его из списка. При вызове с аргументом метод pop удаляет из списка и возвращает элемент с указанным смещением — вызов list.pop(-1) эквивалентен вызову list.pop(). Операции, выполняющие изменения на месте, такие как append, insert, del и pop, не создают новый список, поэтому они действуют быстро (производительность операций может зависеть от того, какой конец списка считается «вершиной» стека, а это, в свою очередь, зависит от текущей реализации списков, а также от способов измерения производительности, которые мы исследуем позднее). Очереди реализуются похожим образом, но выталкивание элементов производится с противоположного конца списка.
Имеются также и другие встроенные схемы реализации. Например, инструкция del stack[:1] является еще одним способом удаления первого элемента стека на основе списка. В зависимости от того, какой конец списка считается вершиной стека, для извлечения и удаления элемента на вершине могут использоваться следующие операции над последовательностями (ценой создания каждый раз нового объекта списка):
# вершиной является начало списка
top, stack = stack[0], stack[1:] # Python 1.X+
top, *stack = stack # Python 3.X
# вершиной является конец списка
stack, top = stack[:-1], stack[-1] # Python 1.X+
# stack, top = stack # Python 3.X
Зачем же тогда реализовывать другие операции при таком богатстве встроенных операций со стеком? С одной стороны, они служат простым и привычным контекстом для исследования понятий структур данных в этой книге. Однако, что более важно, имеется более практический повод. Реализация на основе списка действует, и относительно быстро, но при этом основанные на стеках программы привязываются к избранному представлению стека: все операции со стеком будут жестко определены. Если позднее потребуется изменить представление стека или расширить набор его базовых операций, мы попадем в неприятную ситуацию — придется исправлять все программы, использующие стеки, и все инструкции, реализующие доступ к ним.
Например, чтобы добавить логику, которая контролирует количество операций над стеком, выполняемых программой, пришлось бы добавлять программный код рядом с каждой операцией со стеком. В большой системе решение такой задачи может оказаться нетривиальным. Как будет показано в главе 20, если стеки окажутся узким местом с точки зрения эффективности системы, можно перейти на стеки, реализованные на языке C. Как правило, жестко определенные операции над встроенными структурами данных требуют «ручного» вмешательства при внесении изменений в будущем.
Как мы увидим позднее, встроенные типы, такие как списки, в действительности являются объектами, напоминающими классы, от которых можно порождать подклассы, чтобы настраивать их поведение. Однако это лишь частичное решение — не предполагая изменения в будущем и не создавая экземпляры подкласса, мы все еще можем столкнуться с проблемами, если будем использовать встроенные операции над списками непосредственно и если позднее нам потребуется, чтобы они выполняли какие-либо дополнительные действия.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
