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 dequeue implemented by an array.

ENQUEUE-TAIL(Q, x)

1 if Q.tail + 1 == Q.head or (Q.tail == Q.length and Q.head == 1):

2     error "overflow"

3 Q[Q.tail] = x

4 if Q.tail == Q.length:

5     Q.tail = 1

6 else Q.tail = Q.tail + 1

ENQUEUE-HEAD(Q, x)

1 if Q.tail + 1 == Q.head or (Q.tail == Q.length and Q.head == 1):

2     error "overlow"

3 if Q.head == 1:

4     Q.head = Q.length

5 else Q.head = Q.head - 1

6 Q[Q.head] = x

DEQUEUE-TAIL(Q)

1 if Q.tail == Q.head:

2     error "underflow"

3 if Q.tail == 1:

4     Q.tail = Q.length

5 else Q.tail = Q.tail - 1

6 return Q[Q.tail]

DEQUEUE-HEAD(Q)

1 if Q.tail == Q.head:

2     error "underflow"

3 x = Q[Q.head]

4 if Q.head == Q.length:

5     Q.head = 1

6 else Q.head = Q.head + 1

7 return x