Aufwärmen · Aufgabe 1 von 7
// B4.1 · ca. 25 Min. · Einstieg
Listenmethoden, Stacks und Queues
Nach dieser Lektion ändern Sie Listen mit ihren Methoden, wählen zwischen sort() und sorted() und nutzen eine Liste als Stack und eine deque als Queue.
Lektion 1 von 6 in B4 Datenstrukturen
Anfang des ModulsWeiter
Danach können Sie
- Listen mit append, extend, insert, remove und pop ändern und mit index und count durchsuchen
- Zwischen list.sort(), das an Ort und Stelle sortiert, und sorted(), das eine neue Liste liefert, wählen
- Eine Liste als Stack und collections.deque als Queue verwenden
Vorhersagen · Aufgabe 2 von 7
Sagen Sie es vorher, bevor Sie weiterlesen: Was gibt das aus?
a = [1, 2] a.append([3, 4]) b = [1, 2] b.extend([3, 4]) print(len(a), len(b))Üben · Aufgabe 3 von 7
Setzen Sie die Methode ein, die das letzte Element entfernt und zurückgibt, sodass top 3 ist und stack [1, 2].
stack = [1, 2, 3] top = stack.____()top = stack.()Üben · Aufgabe 4 von 7
Was gibt das aus?
nums = [3, 1, 2] result = nums.sort() print(result, nums)Üben · Aufgabe 5 von 7
Jeder Aufruf beginnt mit einem eigenen nums = [5, 2, 7, 2]. Ordnen Sie jedem Aufruf zu, was er tut.
nums = [5, 2, 7, 2]Denksport · Aufgabe 6 von 7
Knobelaufgabe. Eine deque kann an beiden Enden hinzufügen und entfernen. Was gibt das aus?
from collections import deque line = deque(["ana", "ben"]) line.append("cleo") line.appendleft("dan") print(line.popleft(), line.pop())Anwenden · Aufgabe 7 von 7
Mini-Aufgabe. Schreiben Sie balanced(text), das True liefert, wenn jede Klammer ( [ { in text in der richtigen Reihenfolge von der passenden ) ] } geschlossen wird. Nutzen Sie eine Liste als Stack: Legen Sie jede öffnende Klammer ab und nehmen Sie bei einer schließenden die oberste herunter. Probieren Sie "(a[b]{c})", "(]", "(()" und "x)".
Prüfen Sie Ihr Ergebnis anhand dieser Liste
Selbst programmieren
Lesen Sie das ausgearbeitete Beispiel und lösen Sie dann die Übungen. Ihr Code läuft in Ihrem Browser oder auf Ihrem Computer und wird nie hochgeladen.
Ausgearbeitetes Beispiel
Druckwarteschlange und Rückgängig-Stack
Ein Editor verwaltet zwei Sammlungen. Druckaufträge warten in einer deque und werden in der Reihenfolge ihres Eintreffens gedruckt. Bearbeitungen landen in einer Liste, und Rückgängig nimmt die neueste zuerst zurück. Am Ende sortiert das Programm eine Liste von Seitenzahlen zweimal: einmal mit sorted() in eine neue Liste, einmal mit sort() an Ort und Stelle. Starten Sie es, fügen Sie dann einen Auftrag oder eine Bearbeitung hinzu und starten Sie erneut.
main.py
from collections import deque
# Print jobs are served in the order they arrive: a queue.
jobs: deque[str] = deque()
jobs.append("report.pdf")
jobs.append("photo.png")
jobs.append("invoice.pdf")
# Edits are undone newest first: a stack.
edits: list[str] = []
edits.append("type 'Hello'")
edits.append("make bold")
edits.append("delete line 3")
print("Printing:", jobs.popleft())
print("Next up:", jobs[0])
print("Undo:", edits.pop())
print("Undo:", edits.pop())
print("Edits left:", edits)
pages = [12, 3, 7]
print("Sorted copy:", sorted(pages), "original:", pages)
pages.sort(reverse=True)
print("Sorted in place:", pages)
Ausführen mit
python main.pyAusgabe
Printing: report.pdf
Next up: photo.png
Undo: delete line 3
Undo: make bold
Edits left: ["type 'Hello'"]
Sorted copy: [3, 7, 12] original: [12, 3, 7]
Sorted in place: [12, 7, 3]- popleft() nimmt den ältesten Auftrag, und jobs[0] zeigt den nächsten, ohne ihn zu entfernen.
- pop() nimmt die neueste Bearbeitung, die Bearbeitungen kommen also in umgekehrter Reihenfolge zurück.
- sorted(pages) ließ pages unverändert; pages.sort(reverse=True) hat es geändert.
Ändern und ausführen
Tab rückt ein, Umschalt+Tab rückt aus. Um den Editor mit der Tastatur zu verlassen, drücken Sie Esc und dann Tab.
Beim ersten Ausführen lädt Ihr Browser Python herunter (bis zu 6.5 MB) und speichert es im Cache. Ihr Code bleibt auf Ihrem Gerät.
Übungen
Übung 1 von 2
Die besten drei ohne Nebenwirkung
top_three(scores) soll die drei höchsten Punktzahlen liefern, die höchste zuerst. Der Startcode liefert das richtige Ergebnis, ordnet dabei aber auch die Liste um, die der Aufrufer übergeben hat. Ändern Sie ihn so, dass die Liste des Aufrufers genau so bleibt, wie sie war.
Tab rückt ein, Umschalt+Tab rückt aus. Um den Editor mit der Tastatur zu verlassen, drücken Sie Esc und dann Tab.
Beim ersten Ausführen lädt Ihr Browser Python herunter (bis zu 6.5 MB) und speichert es im Cache. Ihr Code bleibt auf Ihrem Gerät.
Hinweise
Hinweis 1
scores.sort() ändert die Liste des Aufrufers, denn die Funktion bekommt dasselbe Listenobjekt, keine Kopie.
Hinweis 2
sorted() liefert eine neue Liste und lässt sein Argument unverändert.
Hinweis 3
return sorted(scores, reverse=True)[:3]
Eine Lösung zeigen
Ein möglicher Lösungsweg. Ihrer kann anders aussehen und trotzdem alle Prüfungen bestehen.
def top_three(scores: list[int]) -> list[int]:
"""Return the three highest scores, highest first."""
return sorted(scores, reverse=True)[:3]
Auf dem eigenen Computer ausführen
Installieren Sie Python 3.14 oder neuer. Speichern Sie diese Dateien in einem Ordner, öffnen Sie dort ein Terminal und führen Sie die Befehle unten aus.
main.py
def top_three(scores: list[int]) -> list[int]:
"""Return the three highest scores, highest first."""
scores.sort(reverse=True)
return scores[:3]
test_main.py
from main import top_three
def test_highest_first():
"""Liefert die drei höchsten Punktzahlen, die höchste zuerst"""
got = top_three([40, 90, 10, 70, 55])
assert got == [90, 70, 55], f"top_three([40, 90, 10, 70, 55]) lieferte {got!r}, erwartet: [90, 70, 55]"
def test_list_unchanged():
"""Lässt die Liste des Aufrufers in ihrer Reihenfolge"""
scores = [40, 90, 10, 70, 55]
top_three(scores)
assert scores == [40, 90, 10, 70, 55], f"nach dem Aufruf ist die Liste des Aufrufers {scores!r}; sie darf sich nicht ändern"
def test_short_list():
"""Funktioniert mit weniger als drei Punktzahlen"""
got = top_three([5, 8])
assert got == [8, 5], f"top_three([5, 8]) lieferte {got!r}, erwartet: [8, 5]"
Unter macOS und Linux tippen Sie python3, wo in diesen Befehlen python steht, wie in der ersten Lektion.
Programm ausführen:
python main.pyPrüfungen ausführen (learnrun.py muss im selben Ordner liegen):
python learnrun.py testÜbung 2 von 2
Eine faire Warteschlange
serve_all(commands) führt eine Liste von Befehlen aus. "join ana" stellt ana in die Schlange; "serve" bedient, wer am längsten wartet, und vermerkt den Namen, oder vermerkt "nobody", wenn die Schlange leer ist. Geben Sie die vermerkten Namen in Reihenfolge zurück. Der Startcode bedient stattdessen die neueste Person und stürzt bei leerer Schlange ab. Verwenden Sie collections.deque.
Tab rückt ein, Umschalt+Tab rückt aus. Um den Editor mit der Tastatur zu verlassen, drücken Sie Esc und dann Tab.
Beim ersten Ausführen lädt Ihr Browser Python herunter (bis zu 6.5 MB) und speichert es im Cache. Ihr Code bleibt auf Ihrem Gerät.
Hinweise
Hinweis 1
waiting.pop() nimmt den neuesten Namen. Eine Queue muss den ältesten nehmen, von vorne.
Hinweis 2
from collections import deque, dann waiting = deque() und waiting.popleft().
Hinweis 3
Prüfen Sie if waiting: vor popleft(); eine leere deque ist falsch.
Eine Lösung zeigen
Ein möglicher Lösungsweg. Ihrer kann anders aussehen und trotzdem alle Prüfungen bestehen.
from collections import deque
def serve_all(commands: list[str]) -> list[str]:
"""Run join and serve commands; return who was served, in order."""
waiting: deque[str] = deque()
served = []
for command in commands:
if command.startswith("join "):
waiting.append(command[5:])
elif command == "serve":
if waiting:
served.append(waiting.popleft())
else:
served.append("nobody")
return served
Auf dem eigenen Computer ausführen
Installieren Sie Python 3.14 oder neuer. Speichern Sie diese Dateien in einem Ordner, öffnen Sie dort ein Terminal und führen Sie die Befehle unten aus.
main.py
def serve_all(commands: list[str]) -> list[str]:
"""Run join and serve commands; return who was served, in order."""
waiting = []
served = []
for command in commands:
if command.startswith("join "):
waiting.append(command[5:])
elif command == "serve":
# Serve the person who has waited longest,
# or record "nobody" when no one is waiting.
served.append(waiting.pop())
return served
test_main.py
from main import serve_all
def test_first_come_first_served():
"""Bedient in der Reihenfolge des Eintreffens"""
got = serve_all(["join ana", "join ben", "serve", "join cleo", "serve", "serve"])
assert got == ["ana", "ben", "cleo"], f"bedient wurden {got!r}, erwartet: ['ana', 'ben', 'cleo']"
def test_nobody_waiting():
"""Vermerkt nobody, wenn die Schlange leer ist"""
got = serve_all(["serve", "join ana", "serve", "serve"])
assert got == ["nobody", "ana", "nobody"], f"bedient wurden {got!r}, erwartet: ['nobody', 'ana', 'nobody']"
def test_no_commands():
"""Bedient niemanden, wenn es keine Befehle gibt"""
got = serve_all([])
assert got == [], f"serve_all([]) lieferte {got!r}, erwartet: []"
Unter macOS und Linux tippen Sie python3, wo in diesen Befehlen python steht, wie in der ersten Lektion.
Programm ausführen:
python main.pyPrüfungen ausführen (learnrun.py muss im selben Ordner liegen):
python learnrun.py testHäufige Fehler
Das Ergebnis von sort() behalten
scores = [30, 10, 20]
scores = scores.sort()
print(scores[0])
Was Python ausgibt
TypeError: 'NoneType' object is not subscriptableWarum, und die Lösung
sort() sortiert die Liste an Ort und Stelle und gibt None zurück; scores = scores.sort() wirft die Liste also weg und behält None. Rufen Sie scores.sort() in einer eigenen Zeile auf, oder schreiben Sie scores = sorted(scores), wenn Sie eine neue Liste wollen.
Einen Wert entfernen, der nicht da ist
guests = ["ana", "ben"]
guests.remove("zoe")
Was Python ausgibt
ValueError: list.remove(x): x not in listWarum, und die Lösung
remove löst ValueError aus, wenn kein Element dem Wert gleicht. Prüfen Sie vorher mit if "zoe" in guests: guests.remove("zoe"). index verhält sich bei einem fehlenden Wert genauso.
pop auf einem leeren Stack
undo = []
last = undo.pop()
Was Python ausgibt
IndexError: pop from empty listWarum, und die Lösung
Eine leere Liste hat nichts zum Herunternehmen. Schützen Sie den Aufruf mit if undo: …, denn eine leere Liste ist falsch. Auch eine deque löst IndexError aus, mit der Meldung "pop from an empty deque".
Python im Browser: Pyodide 314.0.7, MPL-2.0. Lizenz und Quellcode
Abschlussquiz
5 Fragen, ohne Hinweise. Ab 80 % ist die Lektion abgeschlossen.
Erledigen Sie zuerst alle Aufgaben oben, um das Abschlussquiz freizuschalten.