Question

Collections (a) What are generic types and what is their importance in ADTs for collections? (b) How are the ADTS of stacks and queues similar? How does their behaviour differ? (c) What is the difference between a static and a dynamic data structure? Why are static structures such as arrays often used in the background for dynamic data structures (e.g., in Java's ArrayList)? What issues does this raise and how are they generally resolved? (d) Suppose the following fragment occurs in a Java program (and assume that ev erything behaves as you would expect). Write the corresponding output in the answer book Stack<Integer> s = new Stack<>(); s.push (5) while s.isEmpty ()) { int n s.pop () ; System.out.print (n + "-"); if (n 1) s.push (n/3) s.push (n/2) System.out.println (); Queue<Integer> q = new Queue<>(); q.enqueue (5); while q.isEmpty )) { int n q.dequeue () ; System.out.print (n + "^"); if (n 1) { q.enqueue (n/3) ; q.enqueue (n/2); System.out.println ();

Answer 1

1.

a. A generic type is used to allow data type in the parameter declaration.

b. It allows a programmer to compile-time safety. Invalid type caught at compile time itself

ex ArrayList<String> list =new String<String>(); //this list can only be used to add string type in this list

//if any other you try to add it will throw compile time error.

Importance of Generic Type :

a. Type check happens at compile time. Avoid type mismatched exception at run time.

b. No need for typecasting.

c. Programmer can also implement a Generic type Algorithm

2. Stack and Queue similarity :

a. Both internally implement Array or LinkedList.

b. Both have the same super class.

Difference :

a. A stack is LIFO but Queue is FIFO.

b. Stack supports pop() to remove and push() to insert element. Queue supports add() to insert and remove() to remove element.

3. Static and dynamic data structure:

Static data structure:

a. Size is fixed.

b. Memory allocation happens at class loading time.

c. Access time is less

Dynamic data structure

a. Size is not fixed.

b. Size can be modified at run time

c. Difficult access to element with respect to the static data structure.

ArrayList used to make easier accessibility of element. update. add like operation happen in O(1) time in an ArrayList, which is possible because internally in implement array. Having known that array provides add like operation happen in O(1) time.

Element added is ArrayList, internally gets add in an array

But ArrayList is Dynamic data type and its size can be changed.

So when Array size gets full, another array of bigger size gets created and all previous element will get inserted in new array

4.

Stack<Integer> s=new Stack ();
   s.push(5); //add 5 to stack
   while(!s.isEmpty()){
       int n=s.pop(); //pop top element
       System.out.print(n+" _ "); //print n
       if(n>=1){ //
           s.push(n/3); //if n is greater than or equal to 1 divide it by 3 push it
           s.push(n/2); //divide it by 2 push it
       }
   }
   System.out.println();
   Queue<Integer> q =new queue();
   q.add(5);
   while(!q.isEmpty()){
       int n=q.remove();
       System.out.print(n+" _ ");
       if(n>=1){
           q.add(n/3);
           q.add(n/2);
       }
   }
      
      
   }

output

5 _ 2 _ 1 _ 0 _ 0 _ 0 _ 1 _ 0 _ 0 _
5 _ 1 _ 2 _ 0 _ 0 _ 0 _ 1 _ 0 _ 0 _