GATE CS 1996 Q1.12 — Arrays, Stacks and Queues

Let us analyze each statement individually:

• Statement (i): "First-in-first-out (FIFO) types of computations are efficiently supported by STACKS."
  False. Stacks support Last-In-First-Out (LIFO) operations. Queues are used to support FIFO computations.
• Statement (ii): "Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations."
  True. For dynamic list operations, inserting or deleting elements at arbitrary positions (such as the beginning or middle) requires shifting elements in an array, which takes $O(n)$ time. In a linked list, these operations require only pointer updates and can be performed in $O(1)$ time once the node position is accessed.
• Statement (iii): "Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices."
  True. In a linear array queue, once the rear index reaches the end of the array, no further insertions are possible even if there is empty space at the beginning (due to prior deletions). To reuse this space, elements must be shifted, which takes $O(n)$ time. A circular array avoids this overhead by wrapping indices around, allowing continuous enqueue and dequeue operations in $O(1)$ time.
• Statement (iv): "Last-in-first-out (LIFO) type of computations are efficiently supported by QUEUES."
  False. Queues support FIFO computations, whereas stacks support LIFO computations.

Therefore, only statements (ii) and (iii) are true, which corresponds to Option A.