Class PriorityQueue and Interface Queue

In Section 17.8, we introduced the queue data structure and created our own implementation of it. In this section we investigate interface Queue and class PriorityQueue in the Java utilities package (java.util). Queue, a new collection interface introduced in J2SE 5.0, extends interface Collection and provides additional operations for inserting, removing and inspecting elements in a queue. PriorityQueue, one of the classes that implements the Queue interface, orders elements by their natural ordering as specified by Comparable elements' compareTo method or by a Comparator object that is supplied through the constructor.

Class PriorityQueue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure. When adding elements to a PriorityQueue, the elements are inserted in priority order such that the highest-priority element (i.e., the largest value) will be the first element removed from the PriorityQueue.

The common PriorityQueue operations are offer to insert an element at the appropriate location based on priority order, poll to remove the highest-priority element of the priority queue (i.e., the head of the queue), peek to get a reference to the highest-priority element of the priority queue (without removing that element), clear to remove all elements in the priority queue and size to get the number of elements in the priority queue. Figure 19.17 demonstrates the PriorityQueue class.

Figure 19.17. PriorityQueue test program.

(This item is displayed on page 939 in the print version)

 1 // Fig. 19.17:
 2 // Standard library class PriorityQueue test program.
 3 import java.util.PriorityQueue;
 5 public class PriorityQueueTest
 6 {
 7 public static void main( String args[] )
 8 {
 9 // queue of capacity 11 
10 PriorityQueue< Double > queue = new PriorityQueue< Double >();
12 // insert elements to queue
13 queue.offer( 3.2 ); 
14 queue.offer( 9.8 ); 
15 queue.offer( 5.4 ); 
17 System.out.print( "Polling from queue: " );
19 // display elements in queue
20 while ( queue.size() > 0 )
21 {
22 System.out.printf( "%.1f ", queue.peek() ); // view top element
23 queue.poll(); // remove top element
24 } // end while
25 } // end main
26 } // end class PriorityQueueTest
Polling from queue: 3.2 5.4 9.8

Line 10 creates a PriorityQueue that stores Doubles with an initial capacity of 11 elements and orders the elements according to the object's natural ordering (the defaults for a PriorityQueue). Note that PriorityQueue is a generic class and that line 10 instantiates a PriorityQueue with a type argument Double. Class PriorityQueue provides five additional constructors. One of these takes an int and a Comparator object to create a PriorityQueue with the initial capacity specified by the int and the ordering by the Comparator. Lines 1315 use method offer to add elements to the priority queue. Method offer throws a NullPointException if the program attempts to add a null object to the queue. The loop in lines 2024 use method size to determine whether the priority queue is empty (line 20). While there are more elements, line 22 uses PriorityQueue method peek to retrieve the highest-priority element in the queue for output (without actually removing the element from the queue). Line 23 removes the highest-priority element in the queue with method poll.

Introduction to Computers, the Internet and the World Wide Web

Introduction to Java Applications

Introduction to Classes and Objects

Control Statements: Part I

Control Statements: Part 2

Methods: A Deeper Look


Classes and Objects: A Deeper Look

Object-Oriented Programming: Inheritance

Object-Oriented Programming: Polymorphism

GUI Components: Part 1

Graphics and Java 2D™

Exception Handling

Files and Streams


Searching and Sorting

Data Structures



Introduction to Java Applets

Multimedia: Applets and Applications

GUI Components: Part 2



Accessing Databases with JDBC


JavaServer Pages (JSP)

Formatted Output

Strings, Characters and Regular Expressions

Appendix A. Operator Precedence Chart

Appendix B. ASCII Character Set

Appendix C. Keywords and Reserved Words

Appendix D. Primitive Types

Appendix E. (On CD) Number Systems

Appendix F. (On CD) Unicode®

Appendix G. Using the Java API Documentation

Appendix H. (On CD) Creating Documentation with javadoc

Appendix I. (On CD) Bit Manipulation

Appendix J. (On CD) ATM Case Study Code

Appendix K. (On CD) Labeled break and continue Statements

Appendix L. (On CD) UML 2: Additional Diagram Types

Appendix M. (On CD) Design Patterns

Appendix N. Using the Debugger

Inside Back Cover

Java(c) How to Program
Java How to Program (6th Edition) (How to Program (Deitel))
ISBN: 0131483986
EAN: 2147483647
Year: 2003
Pages: 615 © 2008-2020.
If you may any questions please contact us: