Description:

For this programming assignment, you will implement a deque whose size can grow as elements are inserted into the deque. Specifically, you will implement a deque with a doubly linked list. All of your functions should run in O(1) time.

Coding Portion (100 Points): Start with the following template and fill in all of the member functions. Do NOT modify the definition of the functions of the Deque or put the declarations in a different file.

#ifndef DEQUE_H

#include

#define DEQUE_H

#include using namespace std;

template

class Deque

{

private:

// data here

public:

Deque(void);

~Deque(void);

bool isEmpty(void);

int size(void);

Type first(void) throw(exception);

Type last(void) throw(exception);

void insertFirst(Type o);

void insertLast(Type o);

Type removeFirst(void) throw(exception);

Type removeLast(void) throw(exception);

};

#endif

For the Doubly Linked List, you will need to implement another class for the nodes in the Doubly Linked List.

Be sure to test the correctness of your algorithms and implementations. Your code will be graded based on whether or not it compiles, runs, produces the expected output, produces correct output, and your coding style (does the code follow proper indentation/style and comments). Using C++.