For our fourth project we’ll be implementing the Deque (double-ended queue) ADT. A Deque is a generalization
of a queue that allows for enqueueing/dequeueing from both the front and back of the queue (Figure 1).
A couple of points to note:
1. You must implement the ADT deque by using a dynamic array to contain the items in the deque; average
complexity must be O(1) with worst case O(n).
2. The array implementation will feature dynamic memory. The default constructor will create a deque
capable of storing 64 items. Once the capacity is exceeded you must implement an array growing strategy
that doubles the size of the array.
3. You must follow the rule of three
As always, you need to write unit tests for your class.
1 The Deque Class
The file abstract_deque.hpp in the stater code defines the templated interface, AbstractDeque. You should
define a template Deque that publicly inherits from the interface in the header file Deque.hpp. This template
should override the following methods from the interface (see abstract_deque.hpp for details)
You will need to define the methods and implement all methods in the Deque.hpp/.txx file. You should add
appropriate comment blocks to each method, as well. You will need to write tests in the student_tests.cpp
using the Catch testing framework, as described in class. The included CMakeLists.txt file sets up everything
for you. Just generate your build directory for your development environment as described in the course work
We will be using an automatic grader to help you determine your assignment’s completeness and correctness.
A portion of each assignment grade will be determined by the number of passing tests as determined by the
autograder, with our evaluation filling in the rest. This means you know before you turn in your submission that
all is well. You can submit to the autograder as many times as you like, but it is rate limited (five submissions
every hour) to keep you from using it as your compiler. See this canvas for a summary of how to use the grader
(Note is is not WebCAT, which many of you may be familiar with).
For this assignment you should upload a zip file containing only the files: Deque.hpp, Deque.txx and
student_tests.cpp. There is a build target called “submission” configured by default to create this file with
the correct contents in your build directory