A deque (pronounced “deck”) is like a queue, except that items may be added and removed from both the front and the rear. Write either an array-based or linked implementation for the deque.