10. Queue

 

Queue

• A queue is a non-primitive linear data structure. It ia an ordered list in which deletion take place only at one end (called as front), and insertion can take place only at the other end (called as rear).
• The element which is added in first will be first to be removed and the element which is inserted last will be removed in last.
• That is why it is called First In First Out (FIFO) or Last In Last Out (LILO) type of data structure.

Representation of Queue

• Mostly each of our queues will be maintained by a linear array queue and pointer variables: FRONT containing the location of the front element of the queue and REAR, containing the location of the rear element of the queue.
• Whenever an element is added to the queue, the REAR is increased by 1 i.e., REAR = REAR + 1.
• The condition FRONT = null, will indicate that the queue is empty. Whenever an element is deleted from the queue, the value of FRONT is increased by 1 i.e., FRONT = FRONT + 1.

1. Which of the following principle does Queue use?
1. LIFO principle
2. FIFO principle
3. Linear Tree
4. Ordered Array

ii. FIFO principle

2. Queue serve major role in
1. Simulation of recursion
2. Simulation of arbitary linked list
3. Simulation of limited resource allocation
4. Simulation of heap sort

iii. Simulation of limited resource allocation

3. Consider the following sequence of operations on an empty stack:
   push(54); push(52); pop(); push(55); push(62); s = pop();
   Consider the following sequence of operations on an empty queue:
   enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
   The value of s + q is
1. 86
2. 68
3. 24
4. 94

i. 86

4. In a queue, the initial values of FRONT pointer and RARE pointer should be __ and __ respectively.
1. -1, -1
2. 0, -1
3. 0, 0
4. -1, 0

i. -1, -1

5. Consider the following code and find the operation performed.
int fun()
{
    if (isEmpty())
    {
        return -10;
    }
    else
    {
        int n;
        n = q[front];
        front++;
        return n;
    }
}
1. Enqueue
2. Dequeue
3. Return the front element
4. Both ii. and iii.

iv. Both ii. and iii.

6. 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.
1. 1
2. 2
3. 3
4. 4

ii. 2

7. Which of the following is true about linked list implementation of queue
1. In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
2. In 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.

iii. Both of the above.

8. Consider the following pseudo code. Assume that IntQueue is an integer queue. What does the function fun do?
1. Print numbers from 0 to n-1.
2. Print numbers from n-1 to 0.
3. Print first n Fibonacci numbers.
4. Print first n Fibonacci numbers in reverse order.

iii. Print first n Fibonacci numbers.

9. 6, 8, 4, 3 and 1 are inserted into a data structure in the same order. An item is deleted using only a basic data structure operation. If the deleted item is a 1, the data structure cannot be?
1. Queue
2. Tree
3. Stack
4. Hash Table

iii. Print first n fibonacci numbers.

10. The initial configuration of the queue is a, b, c, d (a is the front end). To get the configuration d, c, b, a one needs a minimum of?
1. 3 deletions and 4 additions
2. 3 deletions and 3 additions
3. 3 additions and 2 deletions
4. 2 deletions and 3 additions

ii. 3 deletions and 3 additons

11. Time taken for addition of element in queue is
1. O(1)
2. O(n)
3. O(log n)
4. None of these

i. O(1)

12. In the linked list implementation of queue, where will the new element be inserted?
1. At the middle position of the linked list.
2. At the head position of the linked list.
3. At the tail position of the linked list.
4. None of these

ii. At the head position of the linked list.
iii. At the tail position of the linked list.

13. Which of the following that determines the need for the circular queue?
1. Avoid wastage of memory.
2. Access the queue using priority.
3. Follows the FIFO principle.
4. None of these

i. Avoid wastage of memory.