Arbeiten mit Stacks

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software Engineer

Stacks

LIFO: Last In, First Out
- Das zuletzt eingefügte Element wird als erstes entfernt

Ein Stapel Bücher.

Stacks

LIFO: Last In, First Out
- Das zuletzt eingefügte Element wird immer als erstes entfernt
Hinzufügen nur oben
- Push auf den Stack

Ein Stapel Bücher mit einem neuen Buch oben.

Stacks

LIFO: Last In, First Out
- Das zuletzt eingefügte Element wird immer als erstes entfernt
Hinzufügen nur oben
- Push auf den Stack
Entnehmen nur oben
- Pop vom Stack

Ein Stapel Bücher, bei dem oben ein Buch entnommen wird.

Stacks

LIFO: Last In, First Out
- Das zuletzt eingefügte Element wird als erstes entfernt
Hinzufügen nur oben
- Push auf den Stack
Entfernen nur oben
- Pop vom Stack
Lesen nur des letzten Elements
- Peek auf den Stack

Ein Stapel Bücher mit einem Pfeil auf das Cover des obersten Buchs.

Stacks – echte Einsätze

Undo-Funktion

Ein Stack mit einem Element.

Stacks – echte Einsätze

Undo-Funktion
- jede Taste pushen

Ein Stack mit einem neuen Element oben.

Stacks – echte Einsätze

Undo-Funktion
- jede Taste pushen

Ein Stack mit einem neuen Element oben.

Stacks – echte Einsätze

Undo-Funktion
- jede Taste pushen

Ein Stack mit einem neuen Element oben.

Stacks – echte Einsätze

Undo-Funktion
- jede Taste pushen

Ein Stack mit einem neuen Element oben.

Stacks – echte Einsätze

Undo-Funktion
- jede Taste pushen
- letzte Taste poppen

Ein Stack, bei dem oben ein Element entfernt wurde.

Stacks – echte Einsätze

Symbol-Checker: ( [ { } ] )
- öffnende Symbole pushen

Ein Stack mit einem öffnenden Symbol.

Stacks – echte Einsätze

Symbol-Checker: ( [ { } ] )
- öffnende Symbole pushen

Ein Stack mit einem neuen öffnenden Symbol oben.

Stacks – echte Einsätze

Symbol-Checker: ( [ { } ] )
- öffnende Symbole pushen

Ein Stack mit einem neuen öffnenden Symbol oben.

Stacks – echte Einsätze

Symbol-Checker: ( [ { } ] )
- öffnende Symbole pushen
- schließendes Symbol prüfen

Ein Stack mit öffnenden Symbolen und dem Wort „check "}"".

Stacks – echte Einsätze

Symbol-Checker: ( [ { } ] )
- öffnende Symbole pushen
- schließendes Symbol prüfen
- passendes öffnendes Symbol poppen

Ein Stack, bei dem oben ein öffnendes Symbol entfernt wurde.

Stacks – echte Einsätze

Funktionsaufrufe
- Speicherblock pushen
- nach Ausführung poppen

Stacks – Implementierung mit einfach verketteten Listen

Ein Stack als verkettete Liste.

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

Stacks – Implementierung mit einfach verketteten Listen

Ein als verkettete Liste dargestellter Stack mit Bezeichnungen der Knotenteile.

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

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

Stacks – Implementierung mit einfach verketteten Listen

Ein als verkettete Liste dargestellter Stack mit „TOP“, das auf die Spitze zeigt.

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

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

Stacks – Push

Eine leere und eine gefüllte Stack-Darstellung.

def push(self, data):

Stacks – Push

Leerer und gefüllter Stack, in den ein neuer Knoten eingefügt wird.

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

  if self.top:

Stacks – Push

Leerer und gefüllter Stack, wobei der neue Knoten mit dem obersten Element verbunden ist.

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

    new_node.next = self.top

Stacks – Push

Leerer und gefüllter Stack, in den der neue Knoten eingefügt wurde.

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:

Ein Stack mit „TOP“, das auf den obersten Knoten zeigt.

Stacks – Pop

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

Ein Stack mit „popped_node“, das auf den obersten Knoten zeigt.

Stacks – Pop

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

Ein Stack mit „popped_node“ am obersten Knoten und „TOP“ am zweiten Knoten.

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

Ein Stack mit „popped_node“ an einem vom Stack getrennten Knoten und „TOP“ am obersten Knoten.

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

Ein Stack mit „TOP“, das auf den obersten Knoten zeigt.

Stacks – Peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue in Python

LifoQueue:
- Pythons queue-Modul
- verhält sich wie ein 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

Lass uns üben!

Datenstrukturen und Algorithmen in Python