Queue
Q11.
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m - 1 } } What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?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.
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 areQ14.
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.Q15.
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 ?