New Tutorials: # Queue Data Structure Questions

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?
 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. C. Load Balancing. D. All of the above
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.
 A. 1 B. 2 C. 3 D. 4
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.
 A. 1 B. 2 C. 3 D. 4

Q. A Priority Queue can be efficiently implemented using which of the following data structures?
 A. Array B. Linked List C. Heap Data Structures like Binary Heap, Fibonacci Heap D. None of the above
Q. 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. C. Both of the above D. None of the above
Q. 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 is full and queue is empty will be:
 A. Full: `(REAR+1) mod n == FRONT`, Empty: `REAR == FRONT` B. Full: `(REAR+1) mod n == FRONT`, Empty: `(FRONT+1) mod n == REAR` C. Full: `REAR == FRONT`, Empty: `(REAR+1) mod n == FRONT` D. Full: `(FRONT+1) mod n == REAR`, Empty: `REAR == FRONT`
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:
 A. 10, 8, 7, 5, 3, 2, 1 B. 10, 8, 7, 2, 3, 1, 5 C. 10, 8, 7, 1, 2, 3, 5 D. 10, 8, 7, 3, 2, 1, 5
Q. Consider the following operation along with `Enqueue` and `Dequeue` operations on a Queue, where `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;
}
}``````
 A. O(n) B. O(n + k) C. O(nk) D. O(n2)

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?
 A. A queue cannot be implemented using this stack. B. A queue can be implemented where `ENQUEUE` will be implemented using a single operation and `DEQUEUE` will require two stack operations. C. A queue can be implemented where `ENQUEUE` will be a combination of 3 stack operations and `DEQUEUE` will require a single operation. D. A queue can be implemented where both `ENQUEUE` and `DEQUEUE` will require a single stack operation.
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)?
 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) C. The worst case time complexity for both operations will be Ω(n) D. Worst case time complexity for both operations will be Ω(log n)
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);
}
}``````
 A. Prints numbers from 0 to `n-1` B. Prints numbers from `n-1` to 0 C. Prints first `n` Fibonacci numbers D. Prints first `n` Fibonacci numbers in reverse order.
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?
 A. θ(1), θ(1) B. θ(1), θ(n) C. θ(n), θ(1) D. θ(n), θ(n)

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.
Consider the following function:
``````void f(queue Q)
{
int i ;
if (!isEmpty(Q))
{
i = delete(Q);
f(Q);
insert(Q, i);
}
}``````
What operation is performed by the above function `f`?

 A. Leaves the queue `Q` unchanged B. Reverses the order of the elements in the queue `Q` C. Deletes the element at the front of the queue `Q` and inserts it at the rear keeping the other elements in the same order. D. Empties the queue `Q`
Q. An implementation of a queue `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 push and pop operations performed respectively in the process. Which one of the following is true for all values 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);
}
}
}``````
 A. `n+m <= x < 2n` and `2m <= y <= n+m` B. `n+m <= x < 2n` and `2m<= y <= 2n` C. `2m <= x < 2n` and `2m <= y <= n+m` D. `2m <= x < 2n` and `2m <= y <= 2n`
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));
}
}``````
 A. Removes the last element from `Q` B. Keeps the `Q` same as it was before the call C. Makes `Q` empty D. Reverses the `Q`