Transcription
Data Structures04 - Java Collections FrameworkDavid DrohanJAVA: An Introduction to Problem Solving & Programming, 6th Ed. By Walter SavitchISBN 0132162709 2012 Pearson Education, Inc., Upper Saddle River, NJ. All Rights Reserved
Objectivesq Describe and use class Arrays for arraymanipulations.q Define and use an instance of ArrayListq Introduction to the Java Collections Frameworkq Describe, create, use Iteratorsq Define, use classes with generic types04 - Java Collections Algorithms2
Class Arraysq Class Arraysn n Provides static methods for manipulatingarraysProvides the following “high-level” methodsw Method binarySearch for searching sorted arraysw Method equals for comparing arraysw Method fill for placing values into arraysw Method sort for sorting arrays04 - Java Collections Algorithms3
12// Fig. 19.2: UsingArrays.java// Using Java arrays.3456import java.util.Arrays;public class UsingArrays{78910private int intArray[] { 1, 2, 3, 4, 5, 6 };private double doubleArray[] { 8.4, 9.3, 0.2, 7.9, 3.4 };private int filledIntArray[], intArrayCopy[];11121314// constructor initializes arrayspublic UsingArrays(){filledIntArray new int[ 10 ]; // create int array with 10 elements151617intArrayCopy new int[ intArray.length ];18Arrays.sort( doubleArray ); // sort doubleArray ascending19202122// copy array intArray into array intArrayCopySystem.arraycopy( intArray, 0, intArrayCopy, 0, intArray.length );2324Use static method fill of class Arrays to populatearray with 7sArrays.fill( filledIntArray, 7 ); // fill with 7s} // end UsingArrays constructorUse static method sort of class Arrays tosort array’s elements in ascending orderUse static method arraycopy of class System to copyarray intArray into array intArrayCopy04 - Java Collections Algorithms4
25// output values in each array26public void printArrays()27{2829System.out.print( "doubleArray: " );for ( double doubleValue : doubleArray )303132System.out.print( "\nintArray: " );3334for ( int intValue : intArray )System.out.printf( "%d ", intValue );System.out.printf( "%.1f ", doubleValue );3536System.out.print( "\nfilledIntArray: " );37383940for ( int intValue : filledIntArray )System.out.printf( "%d ", intValue );System.out.print( "\nintArrayCopy: " );41for ( int intValue : intArrayCopy )424344System.out.printf( "%d ", intValue );System.out.println( "\n" );45} // end method printArrays464748// find value in array intArraypublic int searchForInt( int value )49{5051Use static method binarySearch of class Arrays to perform binarysearch on arrayreturn Arrays.binarySearch( intArray, value );} // end method searchForInt5204 - Java Collections Algorithms5
53// compare array contents54public void printEquality()55{56boolean b Arrays.equals( intArray, intArrayCopy );57System.out.printf( "intArray %s intArrayCopy\n",58( b ? " " : "! " ) );Use static method equals of class Arraysto determine whether values of the two arrays areequivalent5960b Arrays.equals( intArray, filledIntArray );61System.out.printf( "intArray %s filledIntArray\n",6263( b ? " " : "! " ) );} // end method printEquality6465public static void main( String args[] )66{67UsingArrays usingArrays new gArrays.printEquality();7104 - Java Collections Algorithms6
7273int location usingArrays.searchForInt( 5 );if ( location 0 )747576777879System.out.printf("Found 5 at element %d in intArray\n", location );elseSystem.out.println( "5 not found in intArray" );location usingArrays.searchForInt( 8763 );80818283if ( location 0 )System.out.printf("Found 8763 at element %d in intArray\n", location );else84System.out.println( "8763 not found in intArray" );85} // end main86 } // end class UsingArraysdoubleArray: 0.2 3.4 7.9 8.4 9.3intArray: 1 2 3 4 5 6filledIntArray: 7 7 7 7 7 7 7 7 7 7intArrayCopy: 1 2 3 4 5 6intArray intArrayCopyintArray ! filledIntArrayFound 5 at element 4 in intArray8763 not found in intArray04 - Java Collections Algorithms7
ArrayLists04 - Java Collections Algorithms8
Array-Based Data Structures: Outlineq The Class ArrayListq Creating an Instance of ArrayListq Using Methods of ArrayListq Programming Example: A To-Do Listq Parameterized Classes and Generic Data Types04 - Java Collections Algorithms9
Class ArrayListq Consider limitations of Java arraysn n Array length is not dynamically changeablePossible to create a new, larger array and copyelements – but this is awkward, contrivedq More elegant solution is use instance ofArrayListn Length is changeable at run time04 - Java Collections Algorithms10
Class ArrayListq Drawbacks of using ArrayListn n n Less efficient than using an arrayCan only store objectsCannot store primitive typesq Implementationn n Actually does use arraysExpands capacity in manner previously suggested04 - Java Collections Algorithms11
Class ArrayListq Class ArrayList is an implementation of anAbstract Data Type (ADT) called a listq Elements can be addedn n n At endAt beginningIn between itemsq Possible to edit, delete, access, and countentries in the list04 - Java Collections Algorithms12
Creating Instance of ArrayListq Necessary toimport java.util.ArrayList;q Create and name instanceArrayList String list new ArrayList String (20);q This list willn n Hold String objectsInitially hold up to 20 elements04 - Java Collections Algorithms13
Using Methods of ArrayListq Object of an ArrayList used like an arrayn But methods must be used, not square bracket []notationq GivenArrayList String aList new ArrayList String (20);n Assign a value withaList.add("Hello Everybody");aList.add(index, "Hi Mam");aList.set(index, "Well Dad");04 - Java Collections Algorithms14
Programming Exampleq A To-Do Listn n n Maintains a list of everyday tasksUser enters as many as desiredProgram displays the listq View source code class ArrayListDemo04 - Java Collections Algorithms15
class ArrayListDemo04 - Java Collections Algorithms16
Programming Example : OutputSamplescreenoutput04 - Java Collections Algorithms17
Notes on Using ArrayListq When accessing all elements of an ArrayListobjectn Use a For-Each loopq Use the trimToSize method to save memoryq To copy an ArrayListn Do not use just an assignment statement (why not?)n Use theclone method, e.g.ArrayList Integer a new ArrayList Integer ();a.add(5);ArrayList Integer b (ArrayList Integer )a.clone();a.add(6);04 - Java Collections Algorithms18
Parameterized Classes, Generic Data Typesq Class ArrayList is a parameterized classn It has a parameter which is a typeq Possible to declare our own classes which usetypes as parametersArrayList Device d new ArrayList Device ();q Note : earlier versions of Java had a type ofArrayList that was not parameterized04 - Java Collections Algorithms19
Collections & Primitive Data Typesq Note that Collections can only hold Objectsn One cannot put a fundamental/primitive data type into a Collectionq Java has defined "wrapper" classes which hold fundamental data typevalues within an Objectn n These classes are defined in java.langEach fundamental data type is represented by a wrapper classq The wrapper classes g04 - Java Collections Algorithms20
Collections & Primitive Data Typesq The wrapper classes are usually used so that fundamental datavalues can be placed within a Collectionq The wrapper classes have useful class constant variablesn n Integer.MAX VALUE, Integer.MIN VALUEDouble.MAX VALUE, Double.MIN VALUE, Double.NaN,Double.NEGATIVE INFINITY, Double.POSITIVE INFINITYq They also have useful class methodsn n Double.parseDouble(String) - converts a String to a doubleInteger.parseInt(String) - converts a String to an integer04 - Java Collections Algorithms21
The Java Collections Framework04 - Java Collections Algorithms22
The Java Collections Frameworkq A collection of interfaces and classes thatimplement useful data structures andalgorithmsq The Collection interface specifies howobjects can be added, removed, or accessedfrom a Collectionq Brief introduction to a number ofimplementationsn See next slide04 - Java Collections Algorithms23
The Java Collections Frameworkq The java classes that implement the collection interfaces,generally have names in combination of the type ofimplementation prefixed to the type of interface, forexample,n n n n ArrayList, LinkedList, also (Vector and Stack) classesimplement the List interface.PriorityQueue implement the Queue interface.HashSet, TreeSet, LinkedHashSet typical general purpose classesthat implement the Set interface.HashMap,TreeMap and LinkedHashMap implement the Map interfaceq The public interface Collection is the root interface inthe collection hierarchy and is part ofjava.util.Collection API.q All java developers should know about the CollectionsFramework!04 - Java Collections Algorithms24
Collections Overview Distinctionq A Collection classn Data structure (object) that can hold references to otherobjectsq The Collections Frameworkn n n n Interfaces declare operations for various collection typesProvide high-performance, high-quality implementations ofcommon data structuresEnable software reuseEnhanced with generics capabilities in J2SE 5.0w Compile-time type checking04 - Java Collections Algorithms25
Interface Collection &Class Collectionsq Interface Collectionn n Root interface in the collection hierarchyInterfaces Set, Queue, List extend interfaceCollectionw Set – collection does not contain duplicatesw Queue – collection represents a waiting linew List – ordered collection can contain duplicate elementsn Contains bulk operationsw Adding, clearing and comparing objectsn Provides a method to return an Iterator objectw Walk through collection and remove elements fromcollection04 - Java Collections Algorithms26
The Collection Interfaceq The Collection interface provides the basis for List-likecollections in Java. The interface includes:boolean add(Object)boolean addAll(Collection)void clear()boolean contains(Object)boolean containsAll(Collection)boolean equals(Object)boolean isEmpty()Iterator iterator()boolean remove(Object)boolean removeAll(Collection)boolean retainAll(Collection)int size()Object[] toArray()Object[] toArray(Object[])04 - Java Collections Algorithms27
Interface Collection &Class Collectionsq Class Collectionsn Provides static methods that manipulateCollection objectsw Implement algorithms for searching, sorting and so on(later section in notes)n Collections can be manipulated polymorphically (ata generic level)q Synchronized collectionq Unmodifiable collection04 - Java Collections Algorithms28
The List Interfaceq Lists allow duplicate entries within the collectionq Lists are an ordered collection much like an arrayn n Lists grow automatically when neededThe list interface provides accessor methods based onindexq The List interface extends the Collections interfaceand add the following method definitions:void add(int index, Object)boolean addAll(int index,Collection)Object get(int index)int indexOf(Object)int lastIndexOf(Object)""ListIterator listIterator()ListIterator listIterator(int index)Object remove(int index)Object set(int index, Object)List subList(int fromIndex, int toIndex)"04 - Java Collections Algorithms29
List Implementationsq Java provides 3 concrete classes which implement the listinterfacen n n ArrayListLinkedListVectorq Vectors try to optimize storage requirements by growingand shrinking as requiredn n Contains a capacity (defaults to size 10)Methods are synchronized (used for Multi-threading)q ArrayList is roughly equivalent to Vectorn Methods are not synchronizedq LinkedList implements a doubly linked list of elementsn Methods are not synchronized04 - Java Collections Algorithms30
The List Interfaceq NOTE :LinkedLists can be used to createStacks, Queues, Trees and Deques (doubleended queues, pronounced “decks”).q The collections framework providesimplementations of some of these datastructures.04 - Java Collections Algorithms31
Iteratorsq A variable that allows you to step through acollection of nodes in a linked listn For arrays, we use an integerq Common to place elements of a linked listinto an arrayn For display purposes, array is easily traversedString[] array myList.toArray();for (String element : array)System.out.println(element);04 - Java Collections Algorithms32
The Iterator Interfaceq Java formally considers an iterator to be anobjectq Note interface named Iterator with methodsn n n hasNext – returns boolean valuenext – returns next element in iterationremove – removes element most recentlyreturned by next method04 - Java Collections Algorithms33
ArrayList and Iterator Exampleq Demonstrate Collection interface capabilitiesq Place two String arrays in ArrayListsq Use Iterator to remove elements fromArrayList04 - Java Collections Algorithms34
12// Fig. 19.3: CollectionTest.java// Using the Collection interface.3import java.util.List;4import java.util.ArrayList;56import java.util.Collection;import java.util.Iterator;78public class CollectionTest9 {1011private static final String[] colors { "MAGENTA", "RED", "WHITE", "BLUE", "CYAN" };12private static final String[] removeColors 13{ "RED", "WHITE", "BLUE" };141516// create ArrayList, add Colors to it and manipulate itpublic CollectionTest()17{181920List String list new ArrayList String ();List String removeList new ArrayList String ();Create ArrayList objects and assign their references tovariable list and removeList, respectively04 - Java Collections Algorithms35
21// add elements in colors array to list22for ( String color : colors )2324252627282930list.add( color );Use List method add to add objects to list and removeList,respectively// add elements in removeColors to removeListfor ( String color : removeColors )removeList.add( color );System.out.println( "ArrayList: " );Use List method size to get the number of ArrayListelements31323334// output list contentsfor ( int count 0; count list.size(); count )System.out.printf( "%s ", list.get( count ) );35// remove colors contained in removeList363738removeColors( list, removeList );394041424344Use List method get to retrieve individual elementvaluesSystem.out.println( "\n\nArrayList after calling removeColors: " );// output list contentsfor ( String color : list )System.out.printf( "%s ", color );Method removeColors takes two Collections asarguments; Line 36 passes two Lists, which extendsCollection, to this method} // end CollectionTest constructor04 - Java Collections Algorithms36
45// remove colors specified in collection2 from collection14647private void removeColors(Collection String collection1, Collection String collection2 )484950{// get iteratorIterator String iterator collection1.iterator();5152// loop while collection has items53while ( iterator.hasNext() )5455Method removeColors allows any Collectionscontaining strings to be passed as arguments to this methodObtain Collection iteratorIterator method hasNext determines whether theIterator contains more elementsif ( collection2.contains( iterator.next() ) )56575859iterator.remove(); // remove current Color} // end method removeColors606162{public static void main( String args[] )Iterator method next returns a reference to the nextelementnew CollectionTest();} // end main63 } // end class CollectionTestCollection method contains determines whethercollection2 contains the element returned by nextArrayList:MAGENTA RED WHITE BLUE CYANArrayList after calling removeColors:MAGENTA CYANUse Iterator method remove to remove Stringfrom Iterator04 - Java Collections Algorithms37
LinkedList and ListIterator Exampleq Add elements of one List to the otherq Convert Strings to uppercaseq Delete a range of elements04 - Java Collections Algorithms38
123// Fig. 19.4: ListTest.java// Using LinkLists.import java.util.List;45678import java.util.LinkedList;import java.util.ListIterator;public class ListTest{9private static final String colors[] { "black", "yellow",10111213"green", "blue", "violet", "silver" };private static final String colors2[] { "gold", "white","brown", "blue", "gray", "silver" };1415// set up and manipulate LinkedList objectspublic ListTest()16{17List String list1 new LinkedList String ();181920List String list2 new LinkedList String ();212223for ( String color : colors )list1.add( color );Create two LinkedList objects// add elements to list linkUse List method add to append elements from array colors to the end oflist104 - Java Collections Algorithms39
24// add elements to list link22526for ( String color : colors2 )list2.add( color );Use List method add to append elements from array colors2 to the end oflist2272829list1.addAll( list2 ); // concatenate listslist2 null; // release resources30313233printList( list1 ); // print list1 elementsUse List method addAll to append all elements of list2 to theend of list1convertToUppercaseStrings( list1 ); // convert to upper case stringprintList( list1 ); // print list1 elements3435System.out.print( "\nDeleting elements 4 to 6." );363738394041removeItems( list1, 4, 7 ); // remove items 4-7 from listprintList( list1 ); // print list1 elementsprintReversedList( list1 ); // print list in reverse order} // end ListTest constructor4243public void printList( List String list ){// output List contents4445System.out.println( "\nlist: " );46for ( String color : list )4748495051Method printList allows any Lists containingstrings to be passed as arguments to this methodSystem.out.printf( "%s ", color );System.out.println();} // end method printList04 - Java Collections Algorithms40
5253// locate String objects and convert to uppercaseprivate void convertToUppercaseStrings( List String list )5455{ListIterator String iterator list.listIterator();565758Method convertToUppercaseStrings allows anyLists containing strings to be passed as arguments to thismethodInvoke List method listIterator to get a bidirectional iterator for the Listwhile ( iterator.hasNext() ){Invoke ListIterator method hasNext to determine whether the List contains another element596061626364656667String color iterator.next(); // get itemiterator.set( color.toUpperCase() ); // convert to upper case} // end while} // end method convertToUppercaseStringsInvoke ListIterator method next to obtain the nextString in the ListInvoke ListIterator method set to replace thecurrent String to which iterator refers with theString returned by method toUpperCase// obtain sublist and use clear method to delete sublist itemsprivate void removeItems( List String list, int start, int end ){list.subList( start, end ).clear();// remove itemsMethod removeItems allows any Lists containing stringsto be passed as arguments to this method68} // end method removeItems69707172Invoke List method subList to obtain a portion of the List// print reversed listprivate void printReversedList( List String list ){7374ListIterator String iterator list.listIterator( list.size() );Method printReversedListallows any Lists containing stringsto be passed as arguments to thismethodInvoke List method listIterator with one argument thatspecifies the starting position to get a bidirectional iterator for thelist04 - Java Collections Algorithms41
75System.out.println( "\nReversed List:" );7677// print list in reverse order78while ( iterator.hasPrevious() )7980The while condition calls method hasPrevious to determine whether thereare more elements while traversing the list backwardSystem.out.printf( "%s ", iterator.previous() );} // end method printReversedList8182public static void main( String args[] )83{8485Invoke ListIterator method previous to get theprevious element from the listnew ListTest();} // end main86 } // end class ListTestlist:black yellow green blue violet silver gold white brown blue gray silverlist:BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY SILVERDeleting elements 4 to 6.list:BLACK YELLOW GREEN BLUE WHITE BROWN BLUE GRAY SILVERReversed List:SILVER GRAY BLUE BROWN WHITE BLUE GREEN YELLOW BLACK04 - Java Collections Algorithms42
LinkedList (Cont.)q static method asList of class Arraysn View an array as a List collectionn n n Allow programmer to manipulate the array as if itwere a listAny modification made through thechange the arrayList viewAny modification made to the array change theList viewn Only operation permitted on the view returned byasListisset04 - Java Collections Algorithms43
1// Fig. 19.5: UsingToArray.java234// Using method toArray.import java.util.LinkedList;import java.util.Arrays;56 public class UsingToArray7 {8// constructor creates LinkedList, adds elements and converts to array9public UsingToArray()Call method asList to create a List view of array colors,10{11121314151617181920which is then used for creating a LinkedListString colors[] { "black", "blue", "yellow" };LinkedList String links new LinkedList String ( Arrays.asList( colors ) );links.addLast( "red" );// add as last itemCall LinkedList method addLast to add “red” to the endof linkslinks.add( "pink" );// add to the endlinks.add( 3, "green" ); // add at 3rd indexlinks.addFirst( "cyan" ); // add as first itemCall LinkedList method add to add “pink” as the lastelement and “green” as the element at index 3Call LinkedList method addFirst to add “cyan” as the new first item inthe LinkedList04 - Java Collections Algorithms44
21// get LinkedList elements as an array2223colors links.toArray( new String[ links.size() ] );2425System.out.println( "colors: " );262728for ( String color : colors )System.out.println( color );} // end UsingToArray constructor2930public static void main( String args[] )31{3233Use List method toArray to obtain array representation ofLinkedListnew UsingToArray();} // end main34 } // end class 04 - Java Collections Algorithms45
Vector Example12// Fig. 19.6: VectorTest.java// Using the Vector class.345import java.util.Vector;import java.util.NoSuchElementException;678public class VectorTest{private static final String colors[] { "red", "white", "blue" };9101112public VectorTest(){Vector String vector new Vector String ();131415printVector( vector ); // print vector1617181920for ( String color : colors )vector.add( color );Create Vector of type String with initial capacity of10 element and capacity increment of zero// add elements to the vectorCall Vector method add to add objects (Strings inthis example) to the end of the VectorprintVector( vector ); // print vector04 - Java Collections Algorithms46
21// output the first and last elements22try232425{26} // end try2728// catch exception if vector is emptycatch ( NoSuchElementException exception )2930{31323334} // end catch35363738System.out.printf( "First element: %s\n", vector.firstElement());System.out.printf( "Last element: %s\n", vector.lastElement() );exception.printStackTrace();Call Vector method firstElement to return a reference to the firstelement in the VectorCall Vector method lastElement to return a reference to the last elementin the Vector// does vector contain "red"?if ( vector.contains( "red" ) )Vector method contains returns boolean thatindicates whether Vector contains a specific ObjectSystem.out.printf( "\n\"red\" found at index %d\n\n",vector.indexOf( "red" ) );elseSystem.out.println( "\n\"red\" not found\n" );39Vector method remove removes the first occurrence of its argument Object fromVector4041vector.remove( "red" ); // remove the string "red"System.out.println( "\"red\" has been removed" );4243printVector( vector ); // print vectorVector method indexOf returns index of firstlocation in Vector containing the argument04 - Java Collections Algorithms47
4445// does vector contain "red" after remove operation?if ( vector.contains( "red" ) )46System.out.printf(47"\"red\" found at index %d\n", vector.indexOf( "red" ) );48else49System.out.println( "\"red\" not found" );505152// print the size and capacity of vectorSystem.out.printf( "\nSize: %d\nCapacity: %d\n", vector.size(),53vector.capacity() );545556} // end Vector constructor57585960{6162636465666768Vector methods size and capacity returnnumber of elements in Vector and Vectorcapacity, respectivelyprivate void printVector( Vector String vectorToOutput )if ( vectorToOutput.isEmpty() )System.out.print( "vector is empty" ); // vectorToOutput is emptyelse // iterate through the elementsMethod printVector allows any Vectors containing strings to bepassed as arguments to this method{System.out.print( "vector contains: " );// output elementsfor ( String element : vectorToOutput )System.out.printf( "%s ", element );} // end elseVector method isEmpty returns true if thereare no elements in the Vector04 - Java Collections Algorithms48
697071System.out.println( "\n" );} // end method printVector727374public static void main( String args[] ){new VectorTest(); // create object and call its constructor75} // end main76 } // end class VectorTestvector is emptyvector contains: red white blueFirst element: redLast element: blue"red" found at index 0"red" has been removedvector contains: white blue"red" not foundSize: 2Capacity: 1004 - Java Collections Algorithms49
Class Stackq Implements a stack data structureq Extends class Vectorq Stores references to objectsq Elements removed from ADT in reverse orderof initial insertionn LIFO Implementation04 - Java Collections Algorithms50
123// Fig. 19.16: StackTest.java// Program to test java.util.Stack.import java.util.Stack;456789import java.util.EmptyStackException;public class StackTest{public StackTest(){10Stack Number stack new Stack Number ();1112// create numbers to store in the stack131415Long longNumber 12L;Integer intNumber 34567;Float floatNumber 1.0F;161718Double doubleNumber 1234.5678;192021stack.push( longNumber ); // push a longprintStack( stack );stack.push( intNumber ); // push an int2223printStack( stack );stack.push( floatNumber ); // push a float24printStack( stack );252627stack.push( doubleNumber ); // push a doubleprintStack( stack );Create an empty Stack of typeNumber// use push methodStack method push adds object to top ofStack04 - Java Collections Algorithms51
28// remove items from stack2930try{31Number removedObject null;3233// pop elements from stack3435while ( true ){Stack method pop removes element from topof Stack3637removedObject stack.pop(); // use pop methodSystem.out.printf( "%s popped\n", removedObject );38printStack( stack );394041} // end while} // end trycatch ( EmptyStackException emptyStackException intStackTrace();} // end catch} // end StackTest constructorprivate void printStack( Stack Number stack ){Stack method isEmpty returns true if Stack isemptyif ( stack.isEmpty() )System.out.print( "stack is empty\n\n" ); // the stack is emptyelse // stack is not empty{System.out.print( "stack contains: " );04 - Java Collections Algorithms52
55// iterate through the elements56for ( Number number : stack )57System.out.printf( "%s ", number );5859System.out.print( "(top) \n\n" ); // indicates top of the stack6061} // end else} // end method printStack6263public static void main( String args[] )64{6566new StackTest();} // end main67 } // end class StackTest04 - Java Collections Algorithms53
stack contains: 12 (top)stack contains: 12 34567 (top)stack contains: 12 34567 1.0 (top)stack contains: 12 34567 1.0 1234.5678 (top)1234.5678 poppedstack contains: 12 34567 1.0 (top)1.0 poppedstack contains: 12 34567 (top)34567 poppedstack contains: 12 (top)12 poppedstack is emptyjava.util.EmptyStackExceptionat java.util.Stack.peek(Unknown Source)at java.util.Stack.pop(Unknown Source)at StackTest. init (StackTest.java:36)at StackTest.main(StackTest.java:65)04 - Java Collections Algorithms54
Interface Queue & Class PriorityQueueq Interface Queuen n n New collection interface introduced in J2SE 5.0Extends interface CollectionProvides additional operations for inserting, removing andinspecting elements in a queue fashionq Class PriorityQueuen n Implements the Queue interfaceOrders elements by their natural orderingw Specified by Comparable elements’ compareTo method ORw Comparator object supplied through constructor (discussed later)q For an Unordered Queue, implement asLinkedList04 - Java Collections Algorithms55
1// Fig. 19.17: PriorityQueueTest.java2// Standard library class PriorityQueue test program.345import java.util.PriorityQueue;public class PriorityQueueTest6789{public static void main( String args[] ){// queue of capacity 111011PriorityQueue Double queue new PriorityQueue Double ();12// insert elements to queue1314queue.offer( 3.2 );queue.offer( 9.8 );15queue.offer( 5.4 );1617System.out.print( "Polling from queue: " );1819202122232425Create a PriorityQueue that stores Doubles with an initial capacity of 11elements and orders the elements according to the object’s natural orderingUse method offer to add elements to the priorityqueue// display elements in queueUse method size to determine whether the priority queueis emptywhile ( queue.size() 0 ){System.out.printf( "%.1f ", queue.peek() ); // view top elementqueue.poll(); // remove top element} // end whileUse method pool to remove the highest-priority element from} // end mainthe queueUse method peek toretrieve the highest-priorityelement in the queue26 } // end class PriorityQueueTestPolling from queue: 3.2 5.4 9.804 - Java Collections Algorithms56
The Set Interfaceq The Set interface also extends the Collectioninterface but does not add any methods to it.q Collection classes which implement the Set interface havethe added stipulation that Sets CANNOT contain duplicateelementsq Elements are compared using the equals methodNOTE: exercise
Array-Based Data Structures: Outline ! The Class ArrayList ! Creating an Instance of ArrayList ! Using Methods of ArrayList ! Programming Example: A To-Do List ! Parameterized Classes and Generic Data Types 04 -
