Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double ended queue) allows insertion and deletion at both ends. Write four $O(1)$ time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.
