Data Structures Multiple Choice Questions and Answers on Queue using Array

1. Which of the following properties is associated with a queue?

a) First In Last Out
b) First In First Out
c) Last In First Out
d) None of the mentioned

Answer: b

Explanation: Queue follows First In First Out structure.

2. In a circular queue, how do you increment the rear end of the queue?

a) rear++
b) (rear+1) % CAPACITY
c) (rear % CAPACITY)+1
d) rear–

Answer: b

Explanation: Ensures rear takes the values from 0 to (CAPACITY-1).

3. What is the term for inserting into a full queue known as?

a) overflow
b) underflow
c) null pointer exception
d) all of the mentioned

Answer: a

Explanation: Just as stack, inserting into a full queue is termed overflow.

4. What is the time complexity of enqueue operation?

a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)

Answer: d

Explanation: Enqueue operation is at the rear end, it takes O(1) time to insert a new item into the queue.

5. What does the following piece of code do?

public Object function()
{
 if(isEmpty())
 return -999;
 else
 {
  Object high;
  high = q[front];
  return high;
 }
}

a) Dequeue
b) Enqueue
c) Return the front element
d) None of the mentioned

Answer: c

Explanation: q[front] gives the element at the front of the queue, since we are not moving the ‘front’ to the next element,
it is not a dequeue operation.

6. What is the need for a circular queue?

a) effective usage of memory
b) easier computations
c) all of the mentioned
d) none of the mentioned

Answer: a

Explanation: In a linear queue, dequeue operation causes the starting elements of the array to be empty, and there is no way you can use that space, while in a circular queue, you can effectively use that space.

7. Which of the following represents a dequeue operation? (count is the number of elements in the queue)

a)

public Object dequeue()
{
 if(count == 0)
 {
  System.out.println("Queue underflow");
  return 0;
 }
 else
 {
  Object ele = q[front];
  q[front] = null;
  front = (front+1)%CAPACITY;
  count--;
  return ele;
 }
}

b)

public Object dequeue()
{
 if(count == 0)
 {
  System.out.println("Queue underflow");
  return 0;
 }
 else
 {
  Object ele = q[front];
  front = (front+1)%CAPACITY;
  q[front] = null;
  count--;
  return ele;
 }
}

c)

public Object dequeue()
{
 if(count == 0)
 {
  System.out.println("Queue underflow");
  return 0;
 }
 else
 {
  front = (front+1)%CAPACITY;
  Object ele = q[front];
  q[front] = null;
  count--;
  return ele;
 }
}

d)

public Object dequeue()
{
 if(count == 0)
 {
  System.out.println("Queue underflow");
  return 0;
 }
 else
 {
  Object ele = q[front];
  q[front] = null;
  front = (front+1)%CAPACITY;
  return ele;
  count--;
 }
}

Answer: a

Explanation: Dequeue removes the first element from the queue, and ‘front’ points to the front end of the queue. Note that even though option d is performing the dequeue operation, it is returning from the function before decrementing the count value.

 
 
8. Which of the following best describes the growth of a linear queue at runtime? (Q is the original queue, size() returns the number of elements in the queue)

a)

private void expand()
{
 int length = size();
 int[] newQ = new int[length<<1];
 for(int i=front; i<=rear; i++)
 {
  newQ[i-front] = Q[i%CAPACITY];
 }
 Q = newQ;
 front = 0;
 rear = size()-1;
}

b)

private void expand()
{
 int length = size();
 int[] newQ = new int[length<<1];
 for(int i=front; i<=rear; i++)
 {
  newQ[i-front] = Q[i%CAPACITY];
 }
 Q = newQ;
}

c)

private void expand()
{
 int length = size();
 int[] newQ = new int[length<<1];
 for(int i=front; i<=rear; i++)
 {
  newQ[i-front] = Q[i];
 }
 Q = newQ;
 front = 0;
 rear = size()-1;
}

d)

private void expand()
{
 int length = size();
 int[] newQ = new int[length*2];
 for(int i=front; i<=rear; i++)
 {
  newQ[i-front] = Q[i%CAPACITY];
 }
 Q = newQ;
}

Answer: a

Explanation: A common technique to expand the size of array at run time is simply to double the size. Create a new array of double the previous size and copy all the elements, after copying do not forget to assign front = 0 and rear = size()-1, as these are necessary to maintain the decorum of the queue operations.

 
 

9. What is the space complexity of a linear queue having n elements?

a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)

Answer: a

Explanation: Because there are n elements.

10. What is the output of the following piece of code?

public class CircularQueue
{
 protected static final int CAPACITY = 100;
 protected int size,front,rear;
 protected Object q[];
 int count = 0;
 
 public CircularQueue()
 {
  this(CAPACITY);
 }
 public CircularQueue (int n)
 {
  size = n;
  front = 0;
  rear = 0;
  q = new Object[size];
 }
 
 
 public void enqueue(Object item)
 {
  if(count == size)
  {
   System.out.println("Queue overflow");
    return;
  }
  else
  {
   q[rear] = item;
   rear = (rear+1)%size;
   count++;
  }
 }
 public Object dequeue()
 {
  if(count == 0)
  {
   System.out.println("Queue underflow");
   return 0;
  }
  else
  {
   Object ele = q[front];
   q[front] = null;
   front = (front+1)%size;
   count--;
   return ele;
  }
 }
 public Object frontElement()
 {
  if(count == 0)
  return -999;
  else
  {
   Object high;
   high = q[front];
   return high;
  }
 }
 public Object rearElement()
 {
  if(count == 0)
  return -999;
  else
  {
   Object low;
   rear = (rear-1)%size;
   low = q[rear];
   rear = (rear+1)%size;
   return low;
  }
 }
}
public class CircularQueueDemo
{
 public static void main(String args[])
 {
  Object var;
  CircularQueue myQ = new CircularQueue();
  myQ.enqueue(10);
  myQ.enqueue(3);
  var = myQ.rearElement();
  myQ.dequeue();
  myQ.enqueue(6);
  var = mQ.frontElement();
  System.out.println(var+" "+var);
 }
}

a) 3 3
b) 3 6
c) 6 6
d) 10 6

Answer: a

Explanation: First enqueue 10 and 3 into the queue, followed by a dequeue(removes 10), followed by an enqueue(6), At this point, 3 is at the front end of the queue and 6 at the rear end, hence a call to frontElement() will return 3 which is displayed twice.