Queue
Q1.
Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q). The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional storage isQ2.
Consider a sequence a of elements a_0 = 1, a_1 = 5, a_2 = 7, a_3 = 8, a_4 = 9, \; and \; a_5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty. I: push the elements of a from a_0 to a_5 in that order into S. II: enqueue the elements of a from a_0 to a_5 in that order into Q. III: pop an element from S. IV: dequeue an element from Q. V: pop an element from S. VI: dequeue an element from Q. VII: dequeue an element from Q and push the same element into S. VIII: Repeat operation VII three times. IX: pop an element from S. X: pop an element from S. The top element of S after executing the above operations is ___.Q3.
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?Q4.
Consider a standard Circular Queue implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are q[0],q[1],... q[10].The front and rear pointers are initialized to point at q[2]. In which position will the ninth element be added?Q5.
A circular queue has been implemented using a single linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operation can be performed in O (1) time ? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.Q6.
Which of the following data structure is useful in traversing a given graph by breadth first search?Q7.
The queue data structure is to be realized by using stack. The number of stacks needed would beQ8.
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below. The maximum possible number of iterations of the while loop in the algorithm is_________.Q9.
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)?Q10.
An implementation of a queue Q, using two stacks S1 and S2, is given below: void insert(Q,x){ push (S1,x); } void delete(Q, x){ 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); } Let n insert and m(\leqn) delete operations be performed in an arbitrary on an empty queue Q, Let x and y be the number of push and pop operations performed respectively in the processes. Which one of the following is true for all m and n ?