Работа со стеками

Структуры данных и алгоритмы на Python

Miriam Antona

Software Engineer

Стеки

  • LIFO: Last-In First-Out
    • Последний добавленный элемент будет первым удалён

Стопка книг.

Структуры данных и алгоритмы на Python

Стеки

  • LIFO: Last-In First-Out
    • Последний добавленный элемент всегда будет первым удалён
  • Добавление только сверху
    • Помещение в стек (push)

Стопка книг с новой книгой, добавленной сверху.

Структуры данных и алгоритмы на Python

Стеки

  • LIFO: Last-In First-Out
    • Последний добавленный элемент всегда будет первым удалён
  • Добавление только сверху
    • Помещение в стек (push)
  • Извлечение только сверху
    • Извлечение из стека (pop)

Стопка книг, из которой забирают верхнюю книгу.

Структуры данных и алгоритмы на Python

Стеки

  • LIFO: Last-In First-Out
    • Последний добавленный элемент всегда будет первым удалён
  • Добавление только сверху
    • Помещение в стек (push)
  • Удаление только сверху
    • Извлечение из стека (pop)
  • Чтение только последнего элемента
    • Просмотр верхушки стека (peek)

Стопка книг со стрелкой, указывающей на обложку верхней книги.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Функция отмены действия

Стек с одним элементом.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Функция отмены действия
    • push каждого нажатия клавиши

Стек с новым элементом, добавленным сверху.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Функция отмены действия
    • push каждого нажатия клавиши

Стек с новым элементом, добавленным сверху.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Функция отмены действия
    • push каждого нажатия клавиши

Стек с новым элементом, добавленным сверху.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Функция отмены действия
    • push каждого нажатия клавиши

Стек с новым элементом, добавленным сверху.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Функция отмены действия
    • push каждого нажатия клавиши
    • pop последнего нажатия

Стек, из которого удалён верхний элемент.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Проверка скобок: ( [ { } ] )
    • push открывающих скобок

Стек с открывающей скобкой.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Проверка скобок: ( [ { } ] )
    • push открывающих скобок

Стек с новой открывающей скобкой, добавленной сверху.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Проверка скобок: ( [ { } ] )
    • push открывающих скобок

Стек с новой открывающей скобкой, добавленной сверху.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Проверка скобок: ( [ { } ] )
    • push открывающих скобок
    • check закрывающей скобки

Стек с открывающими скобками и надписью «check "}"».

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Проверка скобок: ( [ { } ] )
    • push открывающих скобок
    • check закрывающей скобки
    • pop парной открывающей скобки

Стек, из которого удалена верхняя открывающая скобка.

Структуры данных и алгоритмы на Python

Стеки — практическое применение

  • Вызовы функций
    • push блока памяти
    • pop после завершения выполнения
Структуры данных и алгоритмы на Python

Стеки — реализация через односвязный список

Стек, представленный в виде связного списка.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None
Структуры данных и алгоритмы на Python

Стеки — реализация через односвязный список

Стек в виде связного списка с подписями частей узлов.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None
Структуры данных и алгоритмы на Python

Стеки — реализация через односвязный список

Стек в виде связного списка с надписью «TOP», указывающей на вершину стека.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None
Структуры данных и алгоритмы на Python

Стеки — операция push

Схема пустого стека и стека с элементами.

def push(self, data):
Структуры данных и алгоритмы на Python

Стеки — операция push

Схема пустого стека и стека с элементами, куда будет добавлен новый узел.

def push(self, data): 
  new_node = Node(data)

  if self.top:
Структуры данных и алгоритмы на Python

Стеки — операция push

Схема пустого стека и стека с элементами: новый узел связан с верхним элементом стека.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top
Структуры данных и алгоритмы на Python

Стеки — операция push

Схема пустого стека и стека с элементами после добавления нового узла.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node
Структуры данных и алгоритмы на Python

Стеки — операция pop

def pop(self):

  if self.top is None:

    return None

  else:

Схема стека с надписью «TOP», указывающей на верхний узел.

Структуры данных и алгоритмы на Python

Стеки — операция pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

Схема стека с надписью «popped_node», указывающей на верхний узел.

Структуры данных и алгоритмы на Python

Стеки — операция pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

Схема стека: «popped_node» указывает на верхний узел, а «TOP» — на второй узел.

Структуры данных и алгоритмы на Python

Стеки — операция pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

Схема стека: «popped_node» указывает на узел, отсоединённый от стека, а «TOP» — на новый верхний узел.

Структуры данных и алгоритмы на Python

Стеки — операция pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

Схема стека с надписью «TOP», указывающей на верхний узел.

Структуры данных и алгоритмы на Python

Стеки — операция peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None
Структуры данных и алгоритмы на Python

LifoQueue в Python

  • LifoQueue:
    • Модуль queue в Python
    • ведёт себя как стек
import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True
Структуры данных и алгоритмы на Python

Давайте потренируемся!

Структуры данных и алгоритмы на Python

Preparing Video For Download...