QUEUE
1.
How many stacks are required to implement a queue?
(a) 1
(b) 2
(c) 3
(d) 4
Answer
Two stacks are required to implement a queue. Queue follows FIFO ( First-In-First –Out) property. But Stack is based on LIFO(Last-in-first-out) property. So stack always at the top has the most recent element. But for queue, we first remove the element which was inserted first. Thus all the elements above it must be placed in another stack. Thus we need two stacks to implement a queue.
Algorithm:
1) For Enqueue(insertion) operation
a) Push element to stack 1.
2) For Dequeue(deletion) operation
a) If stack 2 is empty, put everything of stack 1 into stack 2.
b) Pop an element from stack 2. .
2.
How many queues are needed to implement a stack?
(a) 1
(b) 2
(c) 3
(d) 4
Answer
Algorithm:
1) For Push operation
a) Enqueue element to queue 1.
2) For Pop operation
a) Dequeue all the elements from queue 1 to queue 2 except last element. This last element is the one that needs to be popped. Pop it.
b) Swap the names of queue1 and queue 2. (or swap the contents from queue 1 to queue 2) .
Suppose implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. 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 takes a single instruction and DEQUEUE takes a sequence of two instructions.
(c) A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
(d) A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.
Answer
For ENQUEUE operation
a) REVERSE
b) PUSH
c) REVERSE
For DEQUEUE operation
a) POP.
4.
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (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)
Answer
It is possible in case of circular array. .
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. 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 Answer
In this recursion, queue is being deleted by one element every time and getting saved in i. And again the function calls itself. When queue becomes empty, the last element will be inserted first in the queue. This will be for all the elements present. Thus, it reverses the order of elements in the queue. .
6.
A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a
(a) queue.
(b) stack.
(c) linked list
(d) tree
Answer
This is the condition that must be fulfilled by a queue. .
7.
Let the following circular queue can accommodate maximum five elements with the following data:
Front=1,Rear=3
Queue: A,B,C,_,_
What will happen when we add “D” to it?
a) Front=1,Rear=4
Queue: A,B,C,D
b) Front=2,Rear=5
Queue: A,B,C,D
c) Front=2,Rear=4
Queue: A,B,C,D
d) Front=1,Rear=3
Queue: A, B, C, D
Adding an element in queue will increase the rear by 1, as insertion in queue takes from back.
Rear=rear+1.
8.
A queue is a,
(a) FIFO (First In First Out) list.
(b) LIFO (Last In First Out) list.
(c) Ordered array.
(d) Linear tree.
Answer
Queue follows first-in-first-out condition. .
9.
The data structure required for Breadth First Traversal on a graph is?
(a) Stack
(b) Array
(c) Queue
(d) Tree
Answer
Breadth first traversal is an algorithm to traverse nodes of a graph.It says, first traverse a node, then traverse all the nodes that are adjacent to it, then traverse all the adjacent nodes to the nodes visited in the last step. So, we need a data structure to maintain the order in FIFO manner which can be done using Queue. .
10.
If the MAX_SIZE is the size of the array used in the implementation of circular queue. How is rear calculated while inserting an element in the queue?
(a) rear=(rear%1)+MAX_SIZE
(b) rear=rear%(MAX_SIZE+1)
(c) rear=(rear+1)%MAX_SIZE
(d) rear=rear+(1%MAX_SIZE)
Rear needs to be increased by one when an element is inserted.,but in case of circular queue, if it goes beyond range of the array, it should be looped back. This is what done by this condition.