DATA STRUCTURES & ALGORITHMS

This Test will cover basic concepts of Queue data Structure and related algorithm.

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

Q. 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.

Q. 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.

Q. A **Priority Queue** can be efficiently implemented using which of the following data structures?

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

Q. Suppose a **Circular queue** of capacity **insertion** and **deletion** operation are carried out using

`(n - 1)`

elements is implemented with an array of `n`

elements. Assume that the `REAR`

and `FRONT`

as array index variables, respectively. Initially, `REAR = FRONT = 0`

. The conditions to detect, queue is full and queue is empty will be:
Q. A **Priority Queue** is implemented as a **Max-Heap**. Initially, it has

`5`

elements. The level-order traversal of the heap is given below: `10, 8, 5, 3, 2`

. Two new elements `1`

and `7`

are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements will be:Q. Consider the following operation along with **Queue**, where

`Enqueue`

and `Dequeue`

operations on a `k`

is a global parameter. What will be the worst case time complexity of a sequence of `n`

`MultiDequeue()`

operations if the queue is empty initially?
```
MultiDequeue(Q)
{
m = k;
while (Q is not empty and m > 0)
{
Dequeue(Q)
m = m - 1;
}
}
```

Q. Suppose a stack implementation supports an operation

`REVERSE`

, which reverses the order of elements on the stack, in addition to the `PUSH`

and `POP`

operations. Which one of the following statements is TRUE with respect to this modified stack? Q. A queue is implemented using an array such that

`ENQUEUE`

and `DEQUEUE`

operations are performed efficiently. Which one of the following statements is CORRECT if the array is circular. (`n`

refers to the number of items in the queue)?Q. Consider the following pseudocode. 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);
}
}
```

Q. A queue is implemented using a non-circular singly linked list. The queue has a

`head`

pointer and a `tail`

pointer, as shown in the figure. Let `n`

denote the number of nodes in the queue. Let `enqueue`

be implemented by inserting a new node at the `head`

, and `dequeue`

be implemented by deletion of a node from the `tail`

.
Which one of the following is the time complexity of the most time-efficient implementation of `enqueue`

and `dequeue`

, respectively, for this data structure?

Q. Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:

`isEmpty(Q)` : returns true if the queue is empty, false otherwise. |

`delete(Q)` : deletes the element at the front of the queue and returns its value. |

`insert(Q, i)` : inserts the integer i at the rear of the queue. |

```
void f(queue Q)
{
int i ;
if (!isEmpty(Q))
{
i = delete(Q);
f(Q);
insert(Q, i);
}
}
```

`f`

?Q. An implementation of a queue **push** and **pop** operations performed respectively in the process. Which one of the following is true for all values of

`Q`

, using two stacks `S1`

and `S2`

, is given below. If `n`

insert and `m`

(<= n) delete operations were performed in an arbitrary order on an empty queue `Q`

, `x`

and `y`

be the number of `m`

and `n`

?```
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);
}
}
}
```

Q. Following is a C like pseudocode for a function that takes a Queue as an argument, and uses a stack

`S`

to do the processing. What does the function do in general?```
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 poppped item to Q
enQueue(Q, pop(&S));
}
}
```