*Learning objectives*

The classb_stack |

If we know an upper bound for the number of elements on a
stack in advance and if this bound is not too large, we should
use the class * b_stack*
(“bounded stack”) instead of the class

The upper bound N of the number of elements must be specified in the constructor of the class, like for example by

b_stack<int> BS(N);

This class has exactly the same interface as the class
`stack`. However, it is implemented by C++
arrays. Therefore it generally gets by on less storage and the
access to the topmost element is particularly fast: All
operations take time O(1). The space consumption with N elements
in the stack is O(N).

Of course, by “known upper bound” we do not mean a possibly astronomically large number N here, which has been the result of a mathematical analysis of the algorithm, yet is never reached in concrete program runs as the actual number of elements. Rather, the corresponding stack should, eventually, have (almost) N elements actually, and this N should not be exorbitantly large.

More about stacks with a bounded number of elements can be found on the corresponding manual page.