GATE Archives – Previous Years Questions on Queue

Double Ended Queue:

Q1. Following is C like pseudo-code of a function that takes a Queue as an argument, and uses a stack S to do processing.

C

void fun(Queue *Q) 
{ 
    Stack S;  // Say it creates an empty stack S 
   
    // Run while Q is not empty 
    while (!isEmpty(Q)) 
    { 
        // deQueue an item from Q and push the dequeued item to S 
        push(&S, deQueue(Q)); 
    } 
   
    // Run while Stack S is not empty 
    while (!isEmpty(&S)) 
    { 
      // Pop an item from S and enqueue the popped item to Q 
      enQueue(Q, pop(&S)); 
    } 
}

What does the above function do in general?

(A) Removes the last from Q

(B) Keeps the Q same as it was before the call

(D) Reverses the Q

Answer: (D)
Explanation: The function takes a queue Q as an argument. It dequeues all items of Q and pushes them to a stack S. Then pops all items of S and enqueues the items back to Q. Since the stack is LIFO order, all items of the queue are reversed.
Hence option (D) is the correct answer.

Q2. Which one of the following is an application of Queue Data Structure?

(A) When a resource is shared among multiple consumers.

(B) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes

(D) All of the above

Answer: (D)
Explanation:
(A) When a resource is shared among multiple consumers: In scenarios where a resource (such as a printer, CPU time, or database connection) needs to be shared among multiple consumers or processes, a queue data structure can be used. Each consumer can enqueue their requests for the resource, and the resource can be allocated to them in the order of their requests by dequeuing from the queue. This ensures fair access to the shared resource and prevents conflicts or resource contention.

(B) When data is transferred asynchronously between two processes: When data is transferred asynchronously between two processes or systems, a queue can be used as a buffer or intermediary storage. One process enqueues the data to be sent, while the other process dequeues and processes the received data. The queue allows for decoupling the rate of data production from data consumption, ensuring smooth and efficient communication between the processes.

(C) Load Balancing: Load balancing is the practice of distributing workloads across multiple resources to optimize performance and utilization. A queue data structure can be used in load-balancing algorithms to manage incoming requests or tasks. The requests are enqueued in the queue, and the load balancer can dequeue and assign them to available resources based on various criteria (e.g., round-robin, least connections). This helps distribute the workload evenly across the resources, preventing overload and maximizing throughput.

Q3. How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.

(A) 1

(B) 2

(D) 4

Answer: (B)
Explanation: A queue can be implemented using two stacks. Refer this for more reference: https://www.w3wiki.org/queue-using-stacks/
Hence Option(B) is the correct answer.

Q4. How many queues are needed to implement a stack. Consider the situation where no other data structure like arrays, linked list is available to you.

(A) 1

(B) 2

(D) 4

Answer: (B)
Explanation: A stack can be implemented using two queues. Refer this for more reference: https://www.w3wiki.org/implement-stack-using-queue/
Hence Option(B) is the correct answer.

Q5. Which of the following is true about linked list implementation of queue?

(A) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.

(B) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.

(D) None of the above

Answer: (C)
Explanation: To keep the First In First Out order, a queue can be implemented using a linked list in any of the given two ways.
Hence option (C) is the correct answer.

Q6. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Answer: (A)
Explanation: Suppose we start filling the queue.
Let the maxQueueSize ( Capacity of the Queue) is 4.So the size of the array which is used to implement this circular queue is 5, which is n. In the beginning when the queue is empty, FRONT and REAR point to 0 index in the array. REAR represents insertion at the REAR index. FRONT represents deletion from the FRONT index.
enqueue(“a”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 1)
enqueue(“b”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 2)
enqueue(“c”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 3)
enqueue(“d”); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 4)
Now the queue size is 4 which is equal to the maxQueueSize. Hence overflow condition is reached.
Now, we can check for the conditions.
When Queue Full :
( REAR+1)%n = (4+1)%5 = 0
FRONT is also 0. Hence ( REAR + 1 ) %n is equal to FRONT.
When Queue Empty :
REAR was equal to FRONT when empty ( because in the starting before filling the queue FRONT = REAR = 0 )
Hence Option A is correct.

Q7. Consider the following pseudo code. Assume that IntQueue is an integer queue. What does the function fun do?

C

void fun(int n) 
{ 
    IntQueue q = new IntQueue(); 
    q.enqueue(0); 
    q.enqueue(1); 
    for (int i = 0; i < n; i++) { 
        int a = q.dequeue(); 
        int b = q.dequeue(); 
        q.enqueue(b); 
        q.enqueue(a + b); 
        print(a); 
    } 
}

(A) Prints numbers from 0 to n-1

(B) Prints numbers from n-1 to 0

(D) Prints first n Fibonacci numbers in reverse order.

Answer: (C)
Explanation: The function prints first n Fibonacci Numbers. Note that 0 and 1 are initially there in q. In every iteration of the loop sum of the two queue items is enqueued and the front item is dequeued.
Hence option (C) is the correct answer.

Q8. Which of the following is NOT a common operation in a queue data structure?

(A) Enqueue

(B) Dequeue

(D) Shuffle

Answer: (D)
Explanation: Shuffle is NOT a common operation in a queue data structure.
Hence Option (D) is the correct answer.

Q9. Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

(A) A queue cannot be implemented using this stack.

(B) A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

(C) A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

(D) A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Answer: (C)
Explanation: To DEQUEUE an item, simply POP. To ENQUEUE an item, we can do following 3 operations 1) REVERSE 2) PUSH 3) REVERSE
Hence Option (C) is the correct answer.

Q10. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

(A) Both operations can be performed in O(1) time

(B) At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)

(D) Worst case time complexity for both operations will be Ω(log n)

Answer: (A)
Explanation: We can use circular array to implement both in O(1) time. See below article for details
Queue Introduction and Array Implementation
Hence Option (D) is the correct answer.

Queue Notes for GATE Exam [2024]

A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order. Queue is a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element, which is first pushed into the order, the operation is first performed on that.

FIFO Property in Queue

Table of Content

Implementing Queues using Arrays:
Implementing Queues using Linked List:
Implementation of Queue using Stack:
Circular Queue:
Priority Queue:
Double Ended Queue:
GATE Archives – Previous Years Questions on Queue:

GATE Archives – Previous Years Questions on Queue

C

C

Queue Notes for GATE Exam [2024]

Similar Reads