L3_2.2 Dynamische Datenstrukturen: Übung Stapelspeicher

1 Textverarbeitungsprogramm


Ein Textverarbeitungsprogramm speichert jedes getippte Zeichen in einem Stapel-speicher. Bei der Betätigung der Backspace-Taste wird das zuletzt erfasste Zeichen wieder aus dem Stapelspeicher entfernt.
Die Backspace-Taste verschiebt den Cursor um eine Position nach links und entfernt das dort stehende Zeichen.

Folgende Operationen wurden durchgeführt:

1 PUSH("A") 2 PUSH("l") 3 PUSH("h") 4 POP() 5 PUSH("g")
6 PUSH("h") 7 POP() 8 PUSH("o") 9 PUSH("r") 10 PUSH("y")
11 PUSH("h") 12 POP() 13 POP() 14 PUSH("i") 15 PUSH("t")
16 PUSH("m") 17 PUSH("h") 18 POP() 19 POP() 20 PUSH("h")
21 PUSH("m") 22 PUSH("i") 23 PUSH("g") 24 POP() 25 PUSH("k")

Analysieren Sie die Abfolge der Operationen und benennen Sie das Wort, das geschrieben wurde.








2 Würfel

In einem Stapel S1 befinden sich sechs Würfel (W1, W2, W3, W4, W5, W6) in den Farben blau, rot und grün (siehe Abb.).
Die Würfel sollen mit den Operationen PUSH() und POP() in einen Stapel Sgeordnet um-geschichtet werden, so dass sich die roten Würfel (W3 und W5) unten, die grünen Würfel (W2 und W4) in der Mitte und die blauen Würfel (W1 und W6) oben im Stapel Sgeordnet befinden.

Zur Zwischenablage der Würfel steht Ihnen ein Stapel SAblage zur Verfügung.

Notieren Sie in der nachfolgenden Tabelle die Operationen, die notwendig sind, um den geordneten Stapel zu erhalten. 		W6

W5

W4

W3

W2

W1
Notation für die Operationen: S1: POP()
                                                 S geordnet : PUSH(Element)
                                                 SAblage : POP() / PUSH(Element)		 Stapel S1
Data Operation
1
2
3
4
5
6
Data Operation
7
8
9
10
11
12
Data Operation
13
14
15
16

3 Münzautomat

Für einen Münzautomaten wurde eine Software entwickelt, der für die Überwachung der Ein- und Auszahlungen acht Stapelspeicher zur Verfügung stehen.

3.1 Geben Sie für die nachfolgenden Zahlungsvorgänge die notwendigen Operationen an. Gehen Sie bei den Zahlungsvorgängen jeweils von einer größtmöglichen Stückelung der Münzen aus.
Beispiel: 3,89 Euro
               -> 1 x 2 Euro + 1 x 1 Euro + 1 x 50 ct + 1 x 20 ct + 1 x 10 ct + 1 x 5 ct + 2 x 2 ct + 1 x 1 ct
In der Ausgangssituation befinden sich in jedem Stapel jeweils fünf Münzen, also 19,40 Euro.

Notation für die Operationen: S1_euro :     POP()
                                                S20_ct :     PUSH(Münze)

a) Einzahlung: 5,43 Euro


b) Auszahlung: 4,55 Euro

c) Einzahlung: 3,79 Euro

d) Auszahlung: 5,99 Euro

3.2 Wie viele Münzen befinden sich nach den vier Zahlungsvorgängen in den jeweiligen Stapeln.