Chapter 19 Exercise Set 0: Chapter Review

1. Create a full set of unit tests using doctest in a file named test_queues.cpp as we have been doing since Chapter 10 Exercise Set 2: Introducing DOCTEST and TDD. Then add a Makefile as we have been doing since Chapter 13 Exercise Set 1: Introducing Make.

2. Change #define MAX_SIZE 1024 to #define MAX_SIZE 10 and then run the following test_queue.cpp doctests against this implementation:

   #define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
   #include <doctest.h>
   #include <string>
   #include "Queue.h"
   using namespace std;
   
   TEST_CASE("Test basic queue operations on queue of strings") {
       Queue<string> queue;
       CHECK(queue.empty() == true);
       queue.insert("first");
       CHECK(queue.empty() == false);
       queue.insert("second");
       queue.insert("third");
       CHECK(queue.remove() == "first");
       queue.insert("forth");
       queue.insert("fifth");
       queue.insert("sixth");
       queue.insert("seventh");
       queue.insert("eight");
       queue.insert("nineth");
       CHECK(queue.remove() == "second");
       CHECK(queue.remove() == "third");
       queue.insert("tenth");
       queue.insert("eleventh");
       CHECK(queue.remove() == "forth");
       queue.insert("twelfth");
       queue.insert("thirteenth");
       CHECK(queue.remove() == "fifth");
   }
   
   TEST_CASE("Test queue handles overflow and underflow") {
       Queue<int> q;
       for (int i = 1; i < 10; i++)
           q.insert(i);
       CHECK(q.empty() == false);
       CHECK_THROWS_WITH(q.insert(11), "No more space in queue");
       for (int i = 1; i < 10; i++)
           CHECK(q.remove() == i);
       CHECK_THROWS_WITH(q.remove(), "Can't remove from empty queue");
   }
   

   Why did we have to change MAX_SIZE to 10 to use these tests? Could the tests be made more flexible so that the specific value of 10 is not required?

3. Write an implementation of Queue that wraps LinkedList (hint use Implementing stacks by wrapping a list as an example to help you.) Test your new implementation using the same test suite you created in the test_queues.cpp file in the previous exercise.

4. Write an array implementation of Queue that is does not use a circular buffer (so no % operator ;-), but instead shifts all items to the beginning of the array whenever an item is removed from the queue.

5. Modify the Queue implementation from the previous exercise so that it defers shifting items in the array until the end of the array is reached. Can you think of a reason why this approach is “better” than the previous one?