JAVA JAVA JAVA INCLUDE COMMENTS Objective: Yes, the data structures you may have
ID: 3668922 • Letter: J
Question
JAVA JAVA JAVA
INCLUDE COMMENTS
Objective:
Yes, the data structures you may have agonized over is actually already implemented in java, but now you know the details behind each of them. Write a program that does the following:
Create and populate an ArrayList of integers with 10 to 20 numbers where each number could be between 0-99. Then print that out.
Sort the ArrayList in ascending order either by writing QuickSort or MergeSort. You may NOT use the collections sort. Write it yourself. Then print that out.
Populate a Queue with the ArrayList, and then dequeue each element and print it out until the queue is empty.
Populate a Stack with the ArrayList, and then pop each element and print it out until the stack is empty.
Do this process 3 times.
Notes:
Make sure to use import.util.*;
Queues have a different kind of constructor from the rest
Queue<Integer> q = new LinkedList<Integer>();
Here is the documentation links for reference
ArrayList
https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
Queue
https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
Stack
https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
Example:
Populating the Array List of Size 12
This list contains
86
15
7
36
50
32
60
88
0
63
92
59
Sorting
Printing Sorted Numbers
0
7
15
32
36
50
59
60
63
86
88
92
Adding elements in the list to a queue
Removing and Printing each element from the Queue
0
7
15
32
36
50
59
60
63
86
88
92
Adding elements in the list to a stack
Removing and printing each element from the Stack
92
88
86
63
60
59
50
36
32
15
7
0
Populating the Array List of Size 11
This list contains
36
6
36
66
98
12
15
48
53
33
14
Sorting
Printing Sorted Numbers
6
12
14
15
33
36
36
48
53
66
98
Adding elements in the list to a queue
Removing and Printing each element from the Queue
6
12
14
15
33
36
36
48
53
66
98
Adding elements in the list to a stack
Removing and printing each element from the Stack
98
66
53
48
36
36
33
15
14
12
6
Populating the Array List of Size 18
This list contains
27
5
70
48
35
39
14
16
59
94
21
73
83
78
32
97
60
4
Sorting
Printing Sorted Numbers
4
5
14
16
21
27
32
35
39
48
59
60
70
73
78
83
94
97
Adding elements in the list to a queue
Removing and Printing each element from the Queue
4
5
14
16
21
27
32
35
39
48
59
60
70
73
78
83
94
97
Adding elements in the list to a stack
Removing and printing each element from the Stack
97
94
83
78
73
70
60
59
48
39
35
32
27
21
16
14
5
4
Explanation / Answer
//Program:
package datastructures;
import java.util.*;
public class DataStructures {
public static void main(String[] args) {
int n;
for(int i=0;i<3;i++)
{
System.out.println("Populating the Array List of Size ");
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
ArrayList <Integer> Arr=new <Integer> ArrayList(n) ;
for(int j=0;j<n;j++)
{
Random rn = new Random();
int num=rn.nextInt() % 100;
if(num<0) num=num*-1;
Arr.add(num);
}
System.out.println("This list contains");
for(int j=0;j<Arr.size();j++)
{
System.out.println(Arr.get(j));
}
System.out.println("Sorting");
doMergeSort(0, Arr.size()-1,Arr);
System.out.println("Printing sorted numbers");
for(int j=0;j<Arr.size();j++)
{
System.out.println(Arr.get(j));
}
System.out.println("Adding elements in the list to a queue");
Queue<Integer> q = new LinkedList<>();
for(int j=0;j<Arr.size();j++)
{
q.add(Arr.get(j));
}
System.out.println("Removing and Printing each element from the Queue");
for(int j=0;!q.isEmpty();j++)
{
System.out.println(q.remove());
}
System.out.println("Adding elements in the list to a stack");
Stack <Integer> S=new <Integer> Stack();
for(int j=0;j<Arr.size();j++)
{
S.push(Arr.get(j));
}
System.out.println("Removing and printing each element from the Stack");
for(int j=0;!S.isEmpty();j++)
{
System.out.println(S.pop());
}
}
}
private static void doMergeSort(int lowerIndex, int higherIndex, ArrayList <Integer> Arr)
{
if (lowerIndex < higherIndex)
{
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
doMergeSort(lowerIndex, middle,Arr);
// Below step sorts the right side of the array
doMergeSort(middle + 1, higherIndex,Arr);
// Now merge both sides
mergeParts(lowerIndex, middle, higherIndex,Arr);
}
}
private static void mergeParts(int lowerIndex, int middle, int higherIndex, ArrayList <Integer> Arr )
{
int array[]=new int[Arr.size()];
int tempMergArr[]=new int[Arr.size()];
for(int i=0;i<Arr.size();i++)
{
array[i]=Arr.get(i);
}
for (int i = lowerIndex; i <= higherIndex; i++)
{
tempMergArr[i] = array[i];
} int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex)
{ if (tempMergArr[i] <= tempMergArr[j])
{ array[k] = tempMergArr[i]; i++; }
else { array[k] = tempMergArr[j]; j++; } k++; }
while (i <= middle)
{ array[k] = tempMergArr[i]; k++; i++; }
}
}
//Sample Run:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.