10.2. Queues¶
10.2.1. Objectives¶
Upon completion of this module, students will be able to:
Name the function and purpose of basic Java data structures
State key characteristics of Queues in Java
Build and populate Queues in Java
10.2.1.1. Suggested Reading¶
Chapter 10: Queues, Deques, and Priority Queues and Chapter 11: Queue, Deque, and Priority Queue Implementations from Data Structures and Abstractions with Java by Frank M. Carrano and Timothy Henry
10.2.2. Interactive: Introduction to Queues [8:50]¶
Follow Along, Practice, and Explore
Download to run and explore the java files (see below) from the video on your own in eclipse. You may download the standalone *.java file for this example.
QueueInterface.java
package queue; /** An interface for the ADT queue. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public interface QueueInterface { /** Adds a new entry to the back of this queue. @param newEntry An object to be added. */ public void enqueue(T newEntry); /** Removes and returns the entry at the front of this queue. @return The object at the front of the queue. @throws EmptyQueueException if the queue is empty before the operation. */ public T dequeue(); /** Retrieves the entry at the front of this queue. @return The object at the front of the queue. @throws EmptyQueueException if the queue is empty. */ public T getFront(); /** Detects whether this queue is empty. @return True if the queue is empty, or false otherwise. */ public boolean isEmpty(); /** Removes all entries from this queue. */ public void clear(); } // end QueueInterface
Video Slides 10.2.2.1-QueueIntro.pdf
10.2.3. Checkpoint 1¶
10.2.4. Programming Practice: Queues 1¶
10.2.5. Interactive: Linked Queues Intro and Enqueue [11:29]¶
Follow Along, Practice and Explore
Video Slides 10.2.4.1-LinkedQueuesEnqueue.pdf
10.2.6. Checkpoint 2¶
10.2.7. Interactive: Linked Queues Removing and More (Dequeue and Other Methods) [8:41]¶
Follow Along, Practice and Explore
Video Slides 10.2.5.1-LinkedQueueRemove.pdf
10.2.8. Checkpoint 3¶
10.2.9. Interactive: Introduction to Deque [13:51]¶
Follow Along, Practice and Explore
Download to run and explore the java files (see below) from the video on your own in eclipse. You may download the standalone *.java file for this example.
DequeInterface.java
Video Slides 10.2.6.1-DequeIntro.pdf
package deque;
/**
* An interface for the ADT deque.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
* @param generic type for the deque
*/
public interface DequeInterface
{
/**
* Adds a new entry to the front of this dequeue.
*
* @param newEntry
* An object to be added.
*/
public void addToFront(T newEntry);
/**
* Adds a new entry to the back of this dequeue.
*
* @param newEntry
* An object to be added.
*/
public void addToBack(T newEntry);
/**
* Removes and returns the front entry of this dequeue.
*
* @return The object at the front of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T removeFront();
/**
* Removes and returns the back entry of this dequeue.
*
* @return The object at the back of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T removeBack();
/**
* Retrieves the front entry of this dequeue.
*
* @return The object at the front of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T getFront();
/**
* Retrieves the back entry of this dequeue.
*
* @return The object at the back of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T getBack();
/**
* Detects whether this dequeue is empty.
*
* @return True if the queue is empty, or false otherwise.
*/
public boolean isEmpty();
/**
* Removes all entries from this dequeue.
*/
public void clear();
} // end DequeInterface
10.2.10. Checkpoint 4¶
10.2.11. Interactive: Deque Removing and Wrap Up [9:02]¶
Follow Along, Practice and Explore
Video Slides 10.2.7.1-DequeRemoveAndWrapUp.pdf
10.2.12. Checkpoint 5¶
10.2.13. Interactive: ArrayQueue: Array Implementation of Queues [11:08]¶
Follow Along and Engage
Download the slides corresponding to the videos. Take notes on them as you watch the video, practice drawing diagrams yourself!
Video Slides 10.2.8.1-ArrayQueueIntro.pdf
10.2.14. Checkpoint 6¶
10.2.15. Interactive: ArrayQueue: One Unused Location [7:11]¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
Video Slides 10.2.9.1-ArrayQueueRemove.pdf
10.2.16. Checkpoint 7¶
10.2.17. Interactive: ArrayQueue: Ensure Capacity [14:06]¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
Video Slides 10.2.10.2-ArrayQueueEnsureCapacity.pdf
10.2.18. Checkpoint 8¶
10.2.19. Interactive: ArrayQueue WrapUp [6:59]¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
Video Slides 10.2.11.1-ArrayQueueWrapUp.pdf
Empty Queue Exception
package queue;
/**
* A class of runtime exceptions thrown by methods to indicate that a queue is
* empty.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public class EmptyQueueException extends RuntimeException {
/**
* serial Version UID
*/
private static final long serialVersionUID = 960025440830878197L;
public EmptyQueueException() {
this(null);
} // end default constructor
public EmptyQueueException(String message) {
super(message);
} // end constructor
} // end EmptyQueueException
