Реализация стека на Python¶

Теперь, когда у нас есть чёткое определение АТД стека, обратим своё внимание на использование Python для его реализации. Напомним, что когда мы даём физическую реализацию абстрактного типа данных, то подразумеваем реализацию структуры данных.

Как мы уже говорили в главе 1, в Python (как и в любом объектно-ориентированном языке) реализация выбранного абстрактного типа данных (например, стека) - это создание нового класса. Стековые операции воплотятся в его методах. Далее, чтобы реализовать стек, который суть - коллекция элементов, имеет смысл воспользоваться мощью и простотой примитивных коллекций, предоставляемых Python. Мы будем использовать список.

Напомним, что класс списка в Python предоставляет механизм и набор методов для упорядоченной коллекции. Например, если у нас есть список [2, 5, 3, 6, 7, 4], то нам нужно только определиться, который из его концов принять за вершину стека, а который - за базу. Как только решение принято, можно начинать реализовывать операции, используя такие списковые методы, как append и pop

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

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)

Реализация класса Stack с использованием списков Python (stack_1ac)

Помните, что с нажатием кнопки run не произойдёт ничего, кроме объявления класса. Мы должны создать объект Stack, а затем его использовать. ActiveCode 2 демонстрирует класс Stack в действии, которое мы представили последовательностью операций из таблицы 1

from pythonds.basic.stack import Stack

s=Stack()

print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

(stack_ex_1)

Важно отметить, что мы можем выбрать реализацию стека через список, где вершиной считается первый, а не последний элемент. В этом случае предыдущие методы append и pop работать не будут. Мы должны будем явно использовать pop и insert для позиции с индексом 0 (первый элемент в списке). Реализация показана в CodeLens 1

Альтернативная реализация класса Stack (stack_cl_1)

Эта возможность изменять физическое воплощение абстрактного типа данных при поддержке логических характеристик - пример того, как работает абстракция. Однако, даже если стек будет вести себя аналогично, рассмотрение производительности этих двух реализаций покажет их несомненное различие. Напомним, что операции append и pop обе являются О(1). Это означает, что первая реализация будет выполнять добавление и выталкивание за постоянное время, независимо от количества элементов в стеке. Производительность второго варианта страдает, поскольку и insert(0), и pop(0) для стека, размером n, являются O(n). Очевидно, что даже если в реализации логически эквивалентны, то при тестировании они будут иметь очень разные затраты по времени.

Самопроверка

Q-43: Дана следующая последовательность стековых операций. Что будет на вершине стека, когда она завершится?

m = Stack()
m.push('x')
m.push('y')
m.pop()
m.push('z')
m.peek()

Q-44: Дана следующая последовательность стековых операций. Что будет на вершине стека, когда последовательность завершится?

m = Stack()
m.push('x')
m.push('y')
m.push('z')
while not m.isEmpty():
   m.pop()
   m.pop()

Напишите функцию revstring(mystr), используя стек для изменения порядка символов в строке на противоположный.

(stack_stringrev)

Next Section - Простые сбалансированные скобки