STACK-WERKSTATT

Oben rein. Oben raus.

08 / 17

Mission

Baue init, clear, push und pop mit einer durchgehenden tos-Regel.

s->x heißt: „Nimm beim Stack, auf den s zeigt, das Feld x.“

struct stack {
    int* vec;   // Array
    int depth;  // maximale Elementzahl
    int tos;    // top of stack
};

void stack_init(stack* s, int d);
void stack_clear(stack* s);
void stack_push(stack* s, int a);
int  stack_pop(stack* s);

Dein erster Zug

Der Stack ist leer. Welchen Wert bekommt tos, wenn tos immer den Index des obersten Elements bezeichnet?

Index 0 gehört schon zum ersten echten Element. Leer braucht daher einen Wächterwert davor.

tos = −1 bedeutet leer; nach dem ersten Push wird erst auf 0 erhöht und dann in vec[0] geschrieben.

Manipuliere den Stack

Tiefe 5. Schiebe Werte hinein und hole sie wieder heraus. Beobachte tos.

tos = −1

4leer
3leer
2leer
1leer
0leer

Wert Noch leer: tos = −1.

Mechanik-Check: Nach push(2), push(4), push(3): Was liefert der erste pop()?

Vier Funktionen zusammensetzen

Wähle pro Lücke die Zeile, die zur Konvention „tos = Index des obersten Elements“ passt.

init · leer markieren clear · Speicher freigeben push · Overflow prüfen push · Index und Schreiben pop · Underflow prüfen pop · oberstes Element

++tos erhöht vor dem Zugriff: −1 wird 0. tos-- liest erst oben und senkt danach.

Voll ist der Stack beim letzten gültigen Index depth−1. Leerer Stack: tos == −1. Array-Speicher wird mit delete[] freigegeben.

Teil (b): Endlosschleife traceen

Die Musterlösung pusht nacheinander 0, 1, 2, 3, 4 und poppt dann in while(true). Welche Ausgabe entsteht vor dem Programmende?

Ausgabe mit Leerzeichen

Prüfungsabschluss

Erst nach deinem Versuch: vollständiger, konsistenter Code für beide Teilaufgaben.

(a) Vier Stack-Funktionen

void stack_init(stack* s, int d) {
    s->depth = d;
    s->tos = -1;
    s->vec = s->depth == 0 ? nullptr : new int[s->depth];
}

void stack_clear(stack* s) {
    delete[] s->vec;
    s->vec = nullptr;
    s->tos = -1;
    s->depth = 0;
}

void stack_push(stack* s, int a) {
    if (s->tos == s->depth - 1)
        throw std::runtime_error("stack overflow");
    s->vec[++s->tos] = a;
}

int stack_pop(stack* s) {
    if (s->tos == -1)
        throw std::runtime_error("stack underflow");
    return s->vec[s->tos--];
}

(b) Inhalt von main()

stack s;
stack_init(&s, 5);
for (int i = 0; i < 5; ++i)
    stack_push(&s, i);

while (true) {
    int val = stack_pop(&s);
    cout << val << " ";
}
cout << endl;

Randfälle: Der sechste Push wirft stack overflow. Der sechste Pop wirft stack underflow; dadurch endet das Programm nach 4 3 2 1 0. Bei Tiefe 0 setzt init den Arrayzeiger auf nullptr.