The deque ADT is defined to support the following methods: addFirst(e): Insert a
ID: 3796819 • Letter: T
Question
The deque ADT is defined to support the following methods: addFirst(e): Insert a new element e at the front of the deque. addLast(e): Insert a new element e at the back of the deque. removeFirst(): Remove and return the first element of the deque (null if empty). removeLast(): Remove and return the last element of the deque (null if empty). first(): Returns the first element of the deque, without removing it (null if empty). last(): Returns the last element of the deque, without removing it (null if empty). size(): Returns the number of elements in the deque. is Empty(): Returns a boolean indicating whether the deque is empty Describe how to implement the deque ADT using two stacks as the only instance variables. What are the running times of the methods?Explanation / Answer
A deque represents a list using two arraystack.so the places are called front and back back to back so that operations are fast at either end
//n= front.size()+back.size();
running time complexities are
running complexity add(i,x)<={O(i+1) if i<n/4
O(n) if n/4<=i<=3n/4
O(1+n-i) i<3n/4