This exercise is available at https://study.find-santa.eu/exercises/algorithms/deque/.
For the sake of the environment, please avoid printing these instructions in the future. Thank you!

Double-ended Queue (Deque)

Your task is to implement a double-ended queue (deque). It is up to you to decide which underlying data structure to pick (array or linked list). Your Deque has to offer the following API:

void push_back(.);  // append new element to end
void push_front(.);  // append new element to beginning
Type pop_back();  // remove and return last element
Type pop_front();  // remove and return first element

In case the Deque is empty, the pop_* methods must return NULL (depending on your language, this may also be something like nullptr, None or the like).

Using a Deque that stores integers could look like this

Deque d;
d.push_back(15);
d.push_back(7);
d.push_front(5);

The image below shows the deque implemented as a doubly linked list, but you may use other low level data structures as well. Explain your choice as comment or docstring. After the structure is implemented, test it by

  1. inserting 50 random elements
  2. 20 million times:
    using a randomizer, perform either push_front(.) or pop_back() given a 50 / 50 chance for each
Finally, measure the time of running your test code using the time shell command.

deque