Give a Java implementation of the deque ADT using two stacks as the only instance variables. What are the running times of the methods?

6.3. Double-Ended Queues 249 1 /s Interface for a double-ended queue: a collection of elements that can be inserted 3 and removed at both ends; this interface is a simplified version of java.util.Deque. 5 public interface Deque E> 6 Returns the number of elements in the deque./ 7 int size(): 8 Tests whether the deque is empty. bean isEmpty): 10 Returns, but does not remove, the first element of the deque (null if empty) E first) 12 Returns, but does not remove, the last element of the deque (null if empty). / 13 E last(): 14 Inserts an element at the front of the deque. 15 void addFirst(E e); 16 Inserts an element at the back of the deque./ 7 void addLast(E e): 18 Removes and returns the first element of the deque (null if empty). */ 19 E removeFirst( 20 Removes and returns the last element of the deque (null if empty). / 21 E removeLast