Werken met stacks

Datastructuren en algoritmen in Python

Miriam Antona

Software Engineer

Stacks

LIFO: Last-In First-Out
- Laatst toegevoegd wordt als eerste verwijderd

Een stapel boeken.

Stacks

LIFO: Last-In First-Out
- Laatst toegevoegd wordt als eerste verwijderd
Alleen toevoegen aan de top
- PUSH op de stack

Een stapel boeken met een nieuw boek bovenop.

Stacks

LIFO: Last-In First-Out
- Laatst toegevoegd wordt als eerste verwijderd
Alleen toevoegen aan de top
- PUSH op de stack
Alleen nemen van de top
- POP van de stack

Een stapel boeken met een boek van de top gehaald.

Stacks

LIFO: Last-In First-Out
- Laatst toegevoegd wordt als eerste verwijderd
Alleen toevoegen aan de top
- PUSH op de stack
Alleen verwijderen van de top
- POP van de stack
Alleen lezen van het laatste element
- PEEK op de stack

Een stapel boeken met een pijl naar het boek bovenop.

Stacks - echte toepassingen

Ongedaan maken-functie

Een stack met één element.

Stacks - echte toepassingen

Ongedaan maken-functie
- push elke toetsaanslag

Een stack met een nieuw element bovenop.

Stacks - echte toepassingen

Ongedaan maken-functie
- push elke toetsaanslag

Een stack met een nieuw element bovenop.

Stacks - echte toepassingen

Ongedaan maken-functie
- push elke toetsaanslag

Een stack met een nieuw element bovenop.

Stacks - echte toepassingen

Ongedaan maken-functie
- push elke toetsaanslag

Een stack met een nieuw element bovenop.

Stacks - echte toepassingen

Ongedaan maken-functie
- push elke toetsaanslag
- pop laatste toetsaanslag

Een stack waar een element van de top is verwijderd.

Stacks - echte toepassingen

Symboolcontrole: ( [ { } ] )
- push openingssymbolen

Een stack met een openingssymbool.

Stacks - echte toepassingen

Symboolcontrole: ( [ { } ] )
- push openingssymbolen

Een stack met een nieuw openingssymbool bovenop.

Stacks - echte toepassingen

Symboolcontrole: ( [ { } ] )
- push openingssymbolen

Een stack met een nieuw openingssymbool bovenop.

Stacks - echte toepassingen

Symboolcontrole: ( [ { } ] )
- push openingssymbolen
- check eindsymbool

Een stack met openingssymbolen en het woord "check "}"".

Stacks - echte toepassingen

Symboolcontrole: ( [ { } ] )
- push openingssymbolen
- check eindsymbool
- pop bij passend openingssymbool

Een stack waar een openingsymbool van de top is verwijderd.

Stacks - echte toepassingen

Functieaanroepen
- push geheugenblok
- pop na einde uitvoering

Stacks - implementatie met enkelvoudig gelinkte lijsten

Een stack voorgesteld als een gelinkte lijst.

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

Stacks - implementatie met enkelvoudig gelinkte lijsten

Een stack als gelinkte lijst met de namen van de delen van de nodes.

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

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

Stacks - implementatie met enkelvoudig gelinkte lijsten

Een stack als gelinkte lijst met het woord "TOP" naar de top.

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

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

Stacks - push

Een lege stack en een stack met elementen.

def push(self, data):

Stacks - push

Een lege stack en een stack waar een nieuwe node wordt ingevoegd.

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

  if self.top:

Stacks - push

Een lege stack en een stack waar de nieuwe node is verbonden met de top.

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

    new_node.next = self.top

Stacks - push

Een lege stack en een stack waar de nieuwe node is ingevoegd.

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

Stacks - pop

def pop(self):

  if self.top is None:

    return None

  else:

Een stack met het woord "TOP" bij de bovenste node.

Stacks - pop

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

Een stack met "popped_node" bij de bovenste node.

Stacks - pop

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

Een stack met "popped_node" bij de bovenste node en "TOP" bij de tweede node.

Stacks - 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

Een stack met "popped_node" bij een losgekoppelde node en "TOP" bij de bovenste node.

Stacks - 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

Een stack met het woord "TOP" bij de bovenste node.

Stacks - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue in Python

LifoQueue:
- Python’s queue-module
- gedraagt zich als een stack

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

Laten we oefenen!

Datastructuren en algoritmen in Python