Modify the array-based queue definition of Figure 4.25 to use a separate Boolean member to keep track of whether the queue is empty, rather than require that one array position remain empty. Write a...

Modify the array-based queue definition of Figure 4.25 to use a separate Boolean member to keep track of whether the queue is empty, rather than require that one array position remain empty.

Write a recursive algorithm to compute the value of the recurrence relation

T(n) = T(dn/2e) + T(bn/2c) + n; T(1) = 1.

Then, rewrite your algorithm to simulate the recursive calls with a stack.