Структура данных Стек

Стек данных очень часто встречается в программировании и вообще во всем, что связано с компьютерами. Эта структура данных работает по принципу LIFO: Last In First Out, то есть последний пришёл, первый вышел.

Возможно, вы не задумывались об этом, но вы часто пользуетесь возможностью браузеров, реализованной с применением стека. Речь о кнопке «назад». Нажмёте один раз — вернётесь на предыдущую страницу, нажмёте снова — попадёте на страницу, где были до неё.

Во многих текстовых редакторах также есть возможность отмены последних операций. Данная функция тоже реализована при помощи стека.

Если одна функция вызывает другую, эти операции в памяти компьютера тоже помещаются в стек. Во многих текстовых редакторах тоже можно отменить последнюю операцию.

Стек играет очень важную роль в рекурсии, об этом мы подробнее поговорим далее в курсе.

Представьте стопку книг в коробке. Взять можно только верхнюю.

Рассмотрим реализацию стека на языке Python. Для этого создадим класс Stack и определим в нём методы:

push() — добавляет элемент на вершину стека

pop() — удаляет элемент

peak() — возвращает элемент из вершины стека (без удаления);

size() — возвращает размер стека;

isEmpty() — определяет, пуст ли стек.

Реализуем стек на основе списка — поместим все элементы в эту структуру данных. В конструкторе для экземпляра класса создадим пустой список. Далее при вызове методов класса этот список будет меняться:

Скопировать кодPYTHON
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 = Stack()