|The class b_queue|
The upper bound N of the number of elements must be specified in the constructor of the class, like for example in
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 here, which has been the result of a mathematical analysis of the algorithm, which is, however, 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.