mibeon
/ Datenstrukturen

Stack Kapazität

Speicherbedarf eines Stacks bei fester Kapazität: Speicher = Kapazitaet · Elementgroesse. Pre-allokierter Block, kein Overhead pro Element.

Stack Kapazität
01 · Eingabe

Stack Kapazität berechnen

Speicherbedarf eines Stacks bei fester Kapazität: Speicher = Kapazitaet · Elementgroesse. Pre-allokierter Block, kein Overhead pro Element.

Lösen für
Speicher = Kapazitaet · Elementgroesse
Byte

Worum geht es?

Ein Stack (Last In First Out) wird in der Praxis meist als Array fester Größe mit einem top-Index implementiert. Der Speicherbedarf ist dann einfach die Kapazität mal die Elementgröße — push und pop arbeiten in O(1) ohne Allokation.

Klassische Anwendungsfelder sind der Aufrufstapel einer CPU (Funktion-Frames), die Auswertung von Ausdrücken, das Backtracking in rekursiven Algorithmen und Undo-Stacks in Editoren.

Die Formel

Formel Stack-Speicher 
Speicher = Kapazität · Elementgröße

Umstellungen:
    Kapazität     = Speicher / Elementgröße
    Elementgröße  = Speicher / Kapazität

Die Variablen

SymbolBedeutungEinheitErklärung
KapazitätKapazität—Maximale Anzahl Elemente.
ElementgrößeElementgrößeByteGröße eines Elements.
SpeicherSpeicherbedarfByteGesamter belegter Speicher.

Minimal-Beispiel

Ein int32-Stack für 256 Einträge:

Rechnung 256 × int32 
Speicher = 256 · 4
         = 1024 Byte
         = 1 KiB

Praxis-Beispiele

Beispiel 1 — Thread-Aufrufstack

Ein POSIX-Thread bekommt typischerweise 8 MiB Stack (Default unter Linux). Bei einem Frame von 64 Byte ergibt das eine maximale Rekursionstiefe von:

Rechnung Rekursionstiefe 
Kapazität = 8 388 608 / 64
          = 131 072 Frames

Beispiel 2 — Mikrocontroller

Ein AVR mit 2 KiB RAM reserviert oft 256 Byte für den Stack. Bei einem 16-Bit-Frame (Return-Adresse) lassen sich also rund 128 verschachtelte Calls realisieren.

Beispiel 3 — Pointer-Stack

Ein Stack von 64-Bit-Pointern (8 Byte) mit Kapazität 1024:

Rechnung Pointer-Stack 
Speicher = 1024 · 8
         = 8192 Byte
         = 8 KiB