10 Dec 2014 - 8:35pm

I beg to differ. Option d) is the only correct answer.

c) If we have to implement a Queue of size $n$, a linked list representation needs space for both pointers and data. But an array just needs data space.

Note: We are asked to implement a Q of size $n$, and not told to find out the space efficiency when the Q is only partially full.

d) If we need to implement multiple Queues, that need to hold n elements in total, using a linked list representation allows the lists to grow and shrink independently. So, if one Queue is completely full, the others can still be of length $0$.

However, if we use an array, and we do not know how the input will be distributed among the Queues behore-hand, we will have to make all the Queues of capacity $n$. So, even though we will be storing $n$ elements in total, we will be allocating $n \times k$ space ($k$ is the number of lists that need to be implemented).

more less