A

deque

is a data structure consisting of a list of items, on which the following

operations are possible:

push(x)

: Insert item

x

on the front end of the deque.

pop()

: Remove the front item from the deque and return it.

inject(x)

: Insert item

x

on the rear end of the deque.

eject()

: Remove the rear item from the deque and return it.

Write routines to support the deque that take

O

(1) time per operation.

(JAVA)