If we know an upper bound for the number of elements in a queue in advance and this upper bound is not too large, we should use the class b_queue instead of the class queue (“bounded queue”).

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

b_queue<int> BS(N);

This class has exactly the same interface as the class queue; however, it is implemented by circular C++ arrays. Therefore it gets by on less storage in general, and the access to the first and last element is particularly fast: All operations take time O(1). The space consumption is O(N) with N elements stored.

The same we already said about the relationship of b_stack to stack in Section 2.4.2 also applies to this class: With a “known upper bound” we do not mean a possibly astronomically large number N that has been the result of a mathematical analysis of the algorithm but is never reached in concrete program runs as the actual number of elements. Rather some time, the corresponding queue should actually have (almost) N elements and this N should not be exorbitantly large.

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