Table of contents
1.
Introduction
2.
Questions
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024
Easy

Queue Gate Questions

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

The Queue is a vague Data Structure, similar to Stacks. Unlike stacks, the Queue is open at both ends. One area is always used to enter data (enqueue), and the other is used to delete data (dequeue). The Queue follows the exit method first, i.e., the object of the first stored data will be accessed first(FIFO).

 

Questions

1. Application of Queue Data Structure is:-

  1. The resource is shared among multiple consumers.
  2. Data is transferred asynchronously between two processes.
  3. Load Balancing
  4. All of the above

Solution: d. All of the above

All a,b, and c options are the application of Queue.
 

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

void fun(Queue *Q)
{
    Stack S;
 
    while (!isEmpty(Q))
    {
        push(&S, deQueue(Q));
}
    while (!isEmpty(&S))
    {     
      enQueue(Q, pop(&S));
    }
}
You can also try this code with Online C++ Compiler
Run Code


Run-on IDE

What will do above function?

  1. Removes the last from Q
  2. It keeps the Q the same as it was before the call.
  3. Makes Q empty
  4. Reverses the Q

Solution: d.It will reverse the Q.

The function takes the Queue Q as an argument. It removes the line from all Q objects and pushes them into Stack S. Then removes all S objects and lines the objects in en queue to Q. Since the Stack is a LIFO system, all queue items are undone.
 

3. How many stacks are required to implement a queue? Where no other data structure like arrays or linked lists is available.

  1. 1
  2. 2
  3. 3
  4. 4

Solution: b. 2.

A. Queue follows the FIFO principle, whereas Stack follows the LIFO principle. Think of using the 1st Queue as an auxiliary space; push and pop an element from the primary Queue till the last one remains. There are two ways to do this: I. pushing operation is costly II. Popping operations is costly. Read more here.
 

4. How many queues are required to implement a stack? Where no other data structure like arrays and the linked list is available to you.

  1. 1
  2. 2
  3. 3
  4. 4

Solution: b. 2.

A. Similar to the question above, we will use one Queue as an auxiliary space. There are two ways to do this: I. pushing operation is costly II. Popping operations is costly. Read more here.
 

5. A priority queue can be efficiently implemented using which of the following data structures? Consider that the number of inserts and peek and extraction operations are almost the same below.

  1. Binary Heap and Fibonacci Heap
  2. Linked List
  3. Array
  4. None of the above

Solution: a. Binary Heap and Fibonacci Heap

A. Binary heap is implemented using an array, I.e., contiguous memory location. Thus, the cache can operate more efficiently. Click here to see a detailed explanation.
 

6. Is the statement true about linked list implementation of the Queue?

  1. In a push operation, if new nodes are inserted at the beginning of the linked list, then in pop operation and nodes must be removed from the end.
  2. In a push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
  3. Both of the above
  4. None of the above

Solution: c. Both of the above

As First In First Out order, a queue can be implemented using a linked list in any of the given two ways.
 

7. The circular Queue of capacity (n - 1) is used in an array of n elements. Assume that insert and deletion functions are performed using REAR and FRONT as the variable index of Array, respectively. Initially, REAR = FORWARD = 0. The conditions for finding the Queue are full and empty.

  1. (REAR+1) mod n == FRONT, empty: REAR == FRONT.
  2. empty: (FRONT+1) mod n == REAR,(REAR+1) mod n == FRONT
  3. empty: (REAR+1) mod n == FRONT, REAR == FRONT
  4. (FRONT+1) mod n == REAR, empty: REAR == FRONT.

Solution: a. (REAR+1) mod n == FRONT, empty: REAR == FRONT.

(REAR+1) mod n == FRONT for full, as we mod, i.e., % gives the remainder. To understand its significance, consider this example: 6%5=1; if the size of the circular Queue is 5, after filling the last element index would be 6; taking a mod will reduce it to the actual index. Click here to see more explanations.
 

8. A Priority-Queue is implemented as a Max-Heap. The level-order traversal is 10, 8, 5, 3, and 2. Elements 1 and 7 are inserted in a heap in, respectively. The level-order traversal of the heap will be:-

  1. 10, 8, 7, 5, 3, 2, 1
  2. 10, 8, 7, 2, 3, 1, 5
  3. 10, 8, 7, 1, 2, 3, 5
  4. 10, 8, 7, 3, 2, 1, 5

Solution: d. 10, 8, 7, 3, 2, 1, 5

Design a binary search tree with the provided values in a rough notebook, then traverse level order. More explanation of the question is here.
 

9. An implementation of a queue Q, using stacks, S1 and S2, is:-

void insert(Q, x) {
  push (S1, x);
}
  
void delete(Q){
  if(stack-empty(S2)) then 
      if(stack-empty(S1)) then {
          print("Q is empty");
          return;
      }
      else while (!(stack-empty(S1))){
          x=pop(S1);
          push(S2,x);
      }
  x=pop(S2);
}
You can also try this code with Online C++ Compiler
Run Code


Run-on IDE

Let n insert and m (<=n) delete operations to be performed in arbitrary order on an empty queue Q. Let l and m be the number of push and pop operations performed, respectively. Which of the following is valid for all m and n?

  1. 2m <= y <= n+m and n+m <= x < 2n 
  2. 2m<= y <= 2n and n+m <= x < 2n 
  3. 2m <= y <= n+m and 2m <= x < 2n 
  4. m <= x <2n and 2m <= y <= 2n

Solution:a. 2m <= y <= n+m and n+m <= x < 2n 

The way in which installation and removal operations are performed is important here. Best case: Add and delete tasks performed separately. For every wipe operation, two pops and one push function are performed. Therefore, the number of m + n push (n push for insert () and m push for delete ()) and 2m pop operations are performed. Worst case: First n elements are added, and m elements are removed. In the initial removal operation, n + 1 pop operations and n push operations are performed. Without startup, for all deletion tasks, one pop operation is performed. Therefore, the number of m + n pop operations and 2n push operations are performed (n push for insert () and n push for delete ()).
 

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

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);
    }
}
You can also try this code with Online C++ Compiler
Run Code


Run-on IDE

  1. Prints numbers from 0 to n-1
  2. Prints numbers from n-1 to 0
  3. Prints first n Fibonacci numbers
  4. Prints first n reverse Fibonacci numbers.

Solution: c. It will print first n Fibonacci numbers.

The fun function can print first n Fibonacci number. Note that 0 and 1 are present at the beginning of q. A loop sum of two queue objects is inserted into the line in every repetition, and the previous object is dequeue. So, each time basically, the last and the second last elements are being added together and pushed.
 

11. A standard circular Queue 'q' implemented whose size is 11 from 0 to 10. The front & rear pointers start to point at q[2]. The ninth element be added at which position?

  1. q[0]
  2. q[1]
  3. q[9]
  4. q[10]

 Solution: a. q[0]

A circular queue whose total size is 11, front and rear pointers are initialized from point q[2].

There is only a number of the stack is required to implement a queue.
 

12. Choose the incorrect statement?

  1. If Queue is implemented through the linked list, keeping track of a front pointer will change only rear pointer "s" during insertion into non-empty Queue.
  2. The Queue can be used to implement the least recently used page fault algorithm and Quicksort algorithm.
  3. The Queue can be used to implement the Quicksort algorithm but not least recently used (LRU) page fault algorithm.
  4. Both (A) and (C)

Solution: c. The Queue can be used to implement the Quicksort algorithm but not least recently used (LRU) page fault algorithm.

If the Queue is used with a linked list to keep track of the forward cursor, only the backward indicators will change during the installation of the blank Queue. The Queue can be used to use the recently used page algorithm (LRU) and the Short Quick algorithm. Only option (C) is incorrect.

Read about Application of Queue in Data Structure here.

FAQs

1. Name some public interfaces provided by queues?
Some of the public interfaces provided by queues are

  • isEmpty() -  if the queue is empty returns true.
     
  • peek() -  without removing it returns the item from the front of the queue.
     
  • insert() - At the end of the queue, inserts a new data item.
     
  • remove() - From the end of the queue, it removes the item.
     
  • isFull() - if the queue is full returns true .

 

2. Where are queues used?
Queues are used for:

  • Traverse the nodes of a binary tree.
     
  • Search the vertices of a graph.
     
  • Check if delimiters are balanced in a computer program
     
  • Reverse strings

 

3. What is the best time to push and use pop Queue?
Push () and pop () methods used in stacks take longer to implement. i.e., the release time is speedy and does not depend on the number of items in the stack. In the Big O notation, this is expressed as O (1).

Key takeaways

In this article, we have gone through critical previous years' GATE exam questions. Most of the data structures make use of Queue to implement their algorithms. The Queue is a type of invisible data or a linear data structure that keeps things in order. It uses the FIFO (First In First Out) method to access objects. Rows are often used to manage a string in multithreading and to use critical line systems.

Recommended Reading -

You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

Ninja, have a great time learning.

Live masterclass