Praca ze stosami

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software Engineer

Stosy

LIFO: Last-In First-Out
- Element ostatnio dodany będzie pierwszym do usunięcia

Stos książek.

Stosy

LIFO: Last-In First-Out
- Element ostatnio dodany jest zawsze pierwszym do usunięcia
Można tylko dodawać na szczycie
- Pushing onto the stack

Stos książek z nową książką dodaną na szczycie.

Stosy

LIFO: Last-In First-Out
- Element ostatnio dodany jest zawsze pierwszym do usunięcia
Można tylko dodawać na szczycie
- Pushing onto the stack
Można tylko pobierać ze szczytu
- Popping from the stack

Stos książek z książką pobraną ze szczytu.

Stosy

LIFO: Last-In First-Out
- Element ostatnio dodany jest zawsze pierwszym do usunięcia
Można tylko dodawać na szczycie
- Pushing onto the stack
Można tylko usuwać ze szczytu
- Popping from the stack
Można tylko odczytać ostatni element
- Peeking from the stack

Stos książek ze strzałką wskazującą na okładkę książki na szczycie stosu.

Stosy – zastosowania

Funkcja cofania (Undo)

Stos z jednym elementem.

Stosy – zastosowania

Funkcja cofania (Undo)
- push każde naciśnięcie klawisza

Stos z nowym elementem dodanym na szczycie.

Stosy – zastosowania

Funkcja cofania (Undo)
- push każde naciśnięcie klawisza

Stos z nowym elementem dodanym na szczycie.

Stosy – zastosowania

Funkcja cofania (Undo)
- push każde naciśnięcie klawisza

Stos z nowym elementem dodanym na szczycie.

Stosy – zastosowania

Funkcja cofania (Undo)
- push każde naciśnięcie klawisza

Stos z nowym elementem dodanym na szczycie.

Stosy – zastosowania

Funkcja cofania (Undo)
- push każde naciśnięcie klawisza
- pop ostatnio dodane naciśnięcie

Stos, z którego usunięto element ze szczytu.

Stosy – zastosowania

Sprawdzanie symboli: ( [ { } ] )
- push symbole otwierające

Stos z symbolem otwierającym.

Stosy – zastosowania

Sprawdzanie symboli: ( [ { } ] )
- push symbole otwierające

Stos z nowym symbolem otwierającym dodanym na szczycie.

Stosy – zastosowania

Sprawdzanie symboli: ( [ { } ] )
- push symbole otwierające

Stos z nowym symbolem otwierającym dodanym na szczycie.

Stosy – zastosowania

Sprawdzanie symboli: ( [ { } ] )
- push symbole otwierające
- check symbol zamykający

Stos z symbolami otwierającymi i słowem "check "}"".

Stosy – zastosowania

Sprawdzanie symboli: ( [ { } ] )
- push symbole otwierające
- check symbol zamykający
- pop pasujący symbol otwierający

Stos, z którego usunięto symbol otwierający ze szczytu.

Stosy – zastosowania

Wywołania funkcji
- push blok pamięci
- pop po zakończeniu wykonania

Stosy – implementacja z użyciem list jednokierunkowych

Stos reprezentowany jako lista wiązana.

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

Stosy – implementacja z użyciem list jednokierunkowych

Stos reprezentowany jako lista wiązana z nazwami części węzłów.

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

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

Stosy – implementacja z użyciem list jednokierunkowych

Stos reprezentowany jako lista wiązana ze słowem "TOP" wskazującym szczyt stosu.

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

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

Stosy – push

Reprezentacja pustego stosu i stosu z elementami.

def push(self, data):

Stosy – push

Reprezentacja pustego stosu i stosu z elementami, gdzie nowy węzeł ma zostać wstawiony.

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

  if self.top:

Stosy – push

Reprezentacja pustego stosu i stosu z elementami, gdzie nowy węzeł jest połączony z elementem na szczycie.

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

    new_node.next = self.top

Stosy – push

Reprezentacja pustego stosu i stosu z elementami, gdzie nowy węzeł został wstawiony.

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

Stosy – pop

def pop(self):

  if self.top is None:

    return None

  else:

Reprezentacja stosu ze słowem "TOP" wskazującym węzeł na szczycie.

Stosy – pop

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

Reprezentacja stosu ze słowem "popped_node" wskazującym węzeł na szczycie.

Stosy – pop

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

Reprezentacja stosu ze słowem "popped_node" wskazującym węzeł na szczycie oraz słowem "TOP" wskazującym drugi węzeł.

Stosy – 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

Reprezentacja stosu ze słowem "popped_node" wskazującym węzeł odłączony od stosu oraz słowem "TOP" wskazującym szczyt stosu.

Stosy – 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

Reprezentacja stosu ze słowem "TOP" wskazującym węzeł na szczycie.

Stosy – peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue w Pythonie

LifoQueue:
- Moduł queue w Pythonie
- działa jak stos

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

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie