Section 15.7.1 showed that the Standard Library’s stack
adapter class can use various containers to store its elements. Of course, a stack
requires insertions and deletions only at its top. So, for example, a vector
or a deque
could be used to store the stack
’s elements. A vector
supports fast insertions and deletions at its back. A deque
supports fast insertions and deletions at its front and its back. A deque
is the default representation for the Standard Library’s stack
adapter because a deque
grows more efficiently than a vector
. A vector
is maintained as a contiguous block of memory—when that block is full and a new element is added, the vector
allocates a larger contiguous block of memory and copies the old elements into that new block. A deque
, on the other hand, is typically implemented as list of fixed-size, built-in arrays—new fixed-size built-in arrays are added as necessary and none of the existing elements are copied when new items are added to the front or back. For these reasons, we use a deque
(line 42) as the underlying container for our Stack
class.