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

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

Miriam Antona

Software Engineer

Стеки

LIFO: Last-In First-Out
- Останній доданий елемент буде першим, який видалять

Зображення стопки книжок.

Стеки

LIFO: Last-In First-Out
- Останній доданий елемент завжди буде першим, який видалять
Можна додавати лише згори
- Push у стек

Зображення стопки книжок з новою книжкою, доданою зверху.

Стеки

LIFO: Last-In First-Out
- Останній доданий елемент завжди буде першим, який видалять
Можна додавати лише згори
- Push у стек
Можна брати лише згори
- Pop зі стека

Зображення стопки книжок із книжкою, знятою зверху.

Стеки

LIFO: Last-In First-Out
- Останній доданий елемент завжди буде першим, який видалять
Можна додавати лише згори
- Push у стек
Можна видаляти лише згори
- Pop зі стека
Можна читати лише останній елемент
- Peek у стеку

Зображення стопки книжок зі стрілкою, що вказує на обкладинку книжки зверху.

Стеки — реальні застосування

Функція «Скасувати»

Стек з одним елементом.

Стеки — реальні застосування

Функція «Скасувати»
- push кожного натискання клавіші

Стек із новим елементом, доданим зверху.

Стеки — реальні застосування

Функція «Скасувати»
- push кожного натискання клавіші

Стек із новим елементом, доданим зверху.

Стеки — реальні застосування

Функція «Скасувати»
- push кожного натискання клавіші

Стек із новим елементом, доданим зверху.

Стеки — реальні застосування

Функція «Скасувати»
- push кожного натискання клавіші

Стек із новим елементом, доданим зверху.

Стеки — реальні застосування

Функція «Скасувати»
- push кожного натискання клавіші
- pop останнього введеного символу

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

Стеки — реальні застосування

Перевірка символів: ( [ { } ] )
- push відкривальних символів

Стек із відкривальним символом.

Стеки — реальні застосування

Перевірка символів: ( [ { } ] )
- push відкривальних символів

Стек із новим відкривальним символом, доданим зверху.

Стеки — реальні застосування

Перевірка символів: ( [ { } ] )
- push відкривальних символів

Стек із новим відкривальним символом, доданим зверху.

Стеки — реальні застосування

Перевірка символів: ( [ { } ] )
- push відкривальних символів
- check закривальний символ

Стек із відкривальними символами та словом "check "}"".

Стеки — реальні застосування

Перевірка символів: ( [ { } ] )
- push відкривальних символів
- check закривальний символ
- pop відповідного відкривального символу

Стек, з якого видалено відкривальний символ зверху.

Стеки — реальні застосування

Виклики функцій
- push блоку пам'яті
- pop після завершення виконання

Стеки — реалізація на однозв'язних списках

Стек, поданий як зв'язаний список.

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

Стеки — реалізація на однозв'язних списках

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

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

class Stack:
  def __init__(self):
    self.top = None

Стеки — реалізація на однозв'язних списках

Стек як зв'язаний список зі словом "TOP", що вказує на верхівку.

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

class Stack:
  def __init__(self):
    self.top = None

Стеки — push

Зображення порожнього стека і стека з елементами.

def push(self, data):

Стеки — push

Зображення порожнього стека і стека з елементами, куди буде вставлено новий вузол.

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

  if self.top:

Стеки — push

Зображення порожнього стека і стека з елементами, де новий вузол з'єднано з верхнім елементом.

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

    new_node.next = self.top

Стеки — push

Зображення порожнього стека і стека з елементами, де вставлено новий вузол.

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

Стеки — pop

def pop(self):

  if self.top is None:

    return None

  else:

Зображення стека зі словом "TOP", що вказує на верхній вузол.

Стеки — pop

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

Зображення стека зі словом "popped_node", що вказує на вузол зверху.

Стеки — pop

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

Зображення стека зі словом "popped_node", що вказує на вузол зверху, і словом "TOP" — на другий вузол.

Стеки — 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" — на верхній вузол.

Стеки — 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", що вказує на верхній вузол.

Стеки — peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue в Python

LifoQueue:
- модуль Python queue
- поводиться як стек

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