Dynamic Queue

FAQ

1. How many elements can we insert in a dynamic queue?
Answer: We can insert as many elements we want to use because it is automated in such a way that it doubles the size of itself if size becomes full , so it never shows stack overflow.

2. Can't we use circular queue despite making our custom dynamic queue?
Answer: Ya we can but that will not work for the case if we want to add the elements more than the size of parent queue and also we dont want to remove it. Because if we will use the circular queue it will add elements after removing the elements from first, So it would not meet our requirement as we need the data .
      ex- Q1 contains 5 elements and we want to add 10 more elements and also we want to print it ,and also we need the data so that later on we can perform any other operation required so.
          so we have to use custom dynamic queue inspite of circular queue
          
3. What are the types of algorithms in which queues are used?
Answer: a) Hashing may use queues to organize its particular hashing mechanisms
        b) Storage algorithms may use queues to maintain lists of used and available memory blocks
        c) BFS Algo , DFS Algo 
 
4. What is the time complexity for custom dynamic queue?
Answer: The time complexity of the above procedure will be O(1) if we have to insert an element just at the end without increasing the size and O(n) if we have to increase the size as we will have to copy all the values of the queue to the array. 

5. What is the space complexity for custom dynamic queue?
Answer: The space complexity is also O(n) as we make an array of size=2n where n is the current size of the queue.

Hint

1. Can't we modify the add(value) function in such a manner that it will never show us stack overflow?

2. When size equals data.length, we will create new array of double the length of previous one.

3. Now we must copy our elements to the new arrayin such a way that the elements of the queue are placed linearly starting from index 0 in the array . For this we will do arr[i]=data[(front+i)%data.length] for n iterations, where n is the current size of the queue.

4. After this, we will copy the array back to the original queue and we will add the element at the end as we used to do for a normal queue.

MCQ

1. The time complexity for insertion of an element in a dynamic queue at the end without increasing the size will be

	a) O(n)

	b) O(1)
	
	c) O(log n)

	d) O(nlog n)

Answer : b

-------------------------------------------------------------------------------------------------------------

2. The time complexity for insertion of an element in a dynamic queue at the end by increasing the size will be

	a) O(n)

	b) O(1)
	
	c) O(log n)

	d) O(n2)

Answer : a

-------------------------------------------------------------------------------------------------------------

3. The space complexity for insertion of an element in a dynamic queue 

	a) O(n)

	b) O(1)
	
	c) O(log n)

	d) None of the above

Answer : a

-------------------------------------------------------------------------------------------------------------

4. Which of the following principle does Queue use?

	a) LIFO principle

	b) FIFO principle

	c) Linear tree

	d) Ordered array

Answer : b