(Deque) A deque is a data structure consisting of a list of items on which

the following operations are possible:

a. push(x): Insert item x on the front end of the deque.

b. pop(): Remove the front item from the deque and return it.

c. inject(x): Insert item x on the rear end of the deque.

d. eject(): Remove the rear item from the deque and return it.

Write routines to support the deque that take O(1) time per operation (the operations that

take O(n) will be given 0 point).

Write an application file a2q3.cpp containing main() function to test if Deque class

works correctly.

Three files should be submitted for this program question.

1) the file Deque.h which contains the definition and implementation of Deque

class template,

2) the application file a2q3.cpp containing main() function,

3) a script file a2q3result containing result.

Here are the sample runs:

Push values in deque: 1 2 3 4 5

Inject values in deque: 1 2 3 4 5

The front element popped out is 5

The rear element ejected out is 5

The front element popped out is 4

The rear element ejected out is 4