## 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:-**

- The resource is shared among multiple consumers.
- Data is transferred asynchronously between two processes.
- Load Balancing
- 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));
}
}
```

**Run-on IDE**

**What will do above function?**

- Removes the last from Q
- It keeps the Q the same as it was before the call.
- Makes Q empty
- 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
- 2
- 3
- 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
- 2
- 3
- 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.**

- Binary Heap and Fibonacci Heap
- Linked List
- Array
- 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?**

- 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.
- In a push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
- Both of the above
- 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.**

- (REAR+1) mod n == FRONT, empty: REAR == FRONT.
- empty: (FRONT+1) mod n == REAR,(REAR+1) mod n == FRONT
- empty: (REAR+1) mod n == FRONT, REAR == FRONT
- (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:-**

- 10, 8, 7, 5, 3, 2, 1
- 10, 8, 7, 2, 3, 1, 5
- 10, 8, 7, 1, 2, 3, 5
- 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);
}
```

**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?**

- 2m <= y <= n+m and n+m <= x < 2n
- 2m<= y <= 2n and n+m <= x < 2n
- 2m <= y <= n+m and 2m <= x < 2n
- 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);
}
}
```

**Run-on IDE**

- Prints numbers from 0 to n-1
- Prints numbers from n-1 to 0
- Prints first n Fibonacci numbers
- 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?**

- q[0]
- q[1]
- q[9]
- 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?**

- 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.
- The Queue can be used to implement the least recently used page fault algorithm and Quicksort algorithm.
- The Queue can be used to implement the Quicksort algorithm but not least recently used (LRU) page fault algorithm.
- 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.