Queue
Q11.
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 ?Q12.
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 ?Q13.
Consider the following statements: (i). First-in-first out types of computations are efficiently supported by STACKS. (ii). Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations. (iii). Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices. (iv). Last-in-first-out type of computations are efficiently supported by QUEUES.Q14.
Suppose a circular queue of capacity (n-1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty areQ15.
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT (Q,C,K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN (Q). For a sequence of operations, the keys chosen are inQ16.
What is the minimum number of stacks of size n required to implement a queue to size n ?