3.17. Using a Deque in C++¶
As we have done in previous sections, we will use the Standard Template Library (STL) of C++ to use a Deque. Again, the Deque library from STL will provide a very nice set of methods upon which to build the details of the deque. Our code (Listing 1) will assume that the front of the deque is at position 0 in the array.
You can see many similarities to C++ code already used for stacks and queues. You are also likely to observe that in this implementation adding and removing items from the back is O(1) whereas adding and removing from the front is O(n). This is to be expected given the common operations that appear for adding and removing items. Again, the important thing is to be certain that we know where the front and rear are assigned in the implementation.