Wenn wir im Voraus eine Obergrenze für die Anzahl der Elemente auf einem Stack kennen, und diese Obergrenze nicht allzu groß ist, so sollten wir statt der Klasse stack die Klasse b_stack verwenden („bounded stack“ = begrenzter Stapel).

Im Konstruktor der Klasse muss die Obergrenze N der Anzahl der Elemente angegeben werden, also etwa

b_stack<int> BS(N);

Diese Klasse besitzt genau dieselbe Schnittstelle wie die Klasse stack, ist aber durch C++-Arrays implementiert. Daher kommt sie i. Allg. mit weniger Speicherplatz aus, und der Zugriff auf das oberste Element ist besonders schnell: Alle Operationen benötigen Zeit O(1). Der Platzverbrauch bei N Elementen ist O(N).

Mit „bekannte Obergrenze“ ist hier natürlich nicht eine möglicherweise astronomisch hohe Zahl N gemeint, die sich durch eine mathematische Analyse des Algorithmus ergeben hat, die aber in konkreten Programmläufen als Elementanzahl nie erreicht wird. Vielmehr sollte der entsprechende Stack irgendwann einmal tatsächlich (fast) N Elemente besitzen und dieses N eben nicht exorbitant groß sein.

Mehr zu Stacks mit begrenzter Elementanzahl kann auf der entsprechenden Manualseite gefunden werden.