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 stack.

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.