Impressum
Inhalt Queue >

Stack

Der Stack ist ein Stapelspeicher, d.h. neue Elemente werden oben draufgelegt und von oben entnommen.
Wir haben hier also einen LIFO-Puffer (Last-In-First-Out), da das was als letztes eingefügt wurde als erstes entnommen wird.
Wir kennen Stapelspeicher aus dem Alltag: In der Technik werden Stacks verwendet:

Operationen

Ein Stack hat folgende Opterationen:

Stack in Python

Man kann in Python einen Stack mittels eines Arrays realisieren:
Wenn man sich für die Stack-Operationen in Python Unterprogramm schreibt, sieht das so aus: 
def push(stack, ding):
    stack.append(ding)
    
def pop(stack):
    return stack.pop()

def isEmpty(stack):
    return len(stack)==0

stack = [] # leeren Stack anlegen
# Elemente 1 bis 9 auf den Stack pushen
for i in range(1,10):
    push(stack, i)
    print(stack)
    
# alle Elemente vom Stack holen
while not isEmpty(stack):
    print(pop(stack))

Ausprobieren

Arithmetische Ausdrücke mit einem Stack auswerten

Wenn man einen arithmetischen Ausdruck so schreibt, dass das Rechnenzeichen nach den Zahlen kommt, kann man es leicht mit einem Stack auswerten.
Statt 3*5 schreibt man: 3 5 *
Statt 3+5 schreibt man: 3 5 +
Statt 1+2+3 schreibt man: 1 2 + 3 + oder 1 2 3 + +
Den Ausdruck 2*(1+4)+7 würde man als 2 1 4 + * 7 +

Auswerten

Zuerst legt man einen leeren Stack an. Dann werden die Zahlen/Rechenzeichen eins nach dem anderen eingelesen.
Beispiel: Eingabe 2 1 4 + * 7 + also (1+4)*2+7
Ablauf:
gelesen 2
2
Stack
gelesen 1
1
2
Stack
gelesen 4
4
1
2
Stack
gelesen +
5
2
Stack
gelesen *
10
Stack
gelesen 7
7
10
Stack
gelesen +
17
Stack

Aufgaben

  1. Stack einfügen:
    1. Fügen Sie folgende Namen in einen leeren Stack ein:
      Eva, Bob, Lea und Ina


    2. Entnehmen Sie jetzt zweimal ein Element vom Stack und fügen sie danach Horst hinzu.


  2. Ein Supermarktregalfach wird nach dem LIFO Prinzip aufgefüllt.
    1. Das leere Fach wird am Montag vor Ladenöffnung mit 5 Artikeln aufgefüllt, diese haben das Verfallsdatum 1.

    2. Am Montag werden 3 dieser Artikel verkauft und am Dienstag-Morgen wird das Regalfach wirder voll aufgefüllt. Die Auffüllung erfolgt mit Artikel mit Verfallsdatum 2.

    3. Wenn jeden Tag 3 Artikel verkauft und aufgefüllt werden, wann werden dann die letzten Artikel mit MHD 1 verkauft?

  3. Auf einem Stack werden folgende Operationen ausgeführt: 
    push("Du")
push("bist")
pop()
push("eine")
push("Heldin")
pop()
pop()
push("Hallo")

  4. Berechne folgende arithmetische Ausdrücke mittels eines Stacks
    1. 1 3 2 * +

    2. 1 3 + 4 2 + +

    3. 2 3 + 1 2 + *

    4. 2 2 * 3 2 * +

    5. Wie könnte man eine Operation **2 realisieren, die den letzten Wert quadriert?