8.1. Queues¶
8.1.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 Bags in Java
Build and populate Bags in Java
8.1.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
8.1.2. Interactive: Introduction to Queues¶
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. To run the standalone *.java file you will need to
create a new Eclipse project, then
create a package within the project called “example” (the package named at the top of the class MUST match the package the file is placed in within the Eclipse project), and finally
download and import the standalone *.java file(s) to the created package.
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: QueueIntro.pdf
8.1.3. Checkpoint 1¶
8.1.4. Programming Practice: Queues 1¶
8.1.5. Interactive: Linked Queues Intro and Enqueue¶
Follow Along, Practice and Explore
LinkedQueuesEnqueue.pdf
8.1.6. Checkpoint 2¶
8.1.7. Interactive: Linked Queues Removing and More (Dequeue and Other Methods)¶
Follow Along, Practice and Explore
LinkedQueueRemove.pdf
8.1.8. Checkpoint 3¶
8.1.9. Interactive: Introduction to Deque¶
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. To run the standalone *.java file you will need to
create a new Eclipse project, then
create a package within the project called “example” (the package named at the top of the class MUST match the package the file is placed in within the Eclipse project), and finally
download and import the standalone *.java file(s) to the created package.
DequeInterface.java
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
8.1.10. Checkpoint 4¶
8.1.12. Checkpoint 5¶
8.1.13. Interactive: ArrayQueue: Array Implementation of Queues¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
ArrayQueueIntro.pdf
8.1.14. Checkpoint 6¶
8.1.15. Interactive: ArrayQueue: One Unused Location¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
ArrayQueueRemove.pdf
8.1.16. Checkpoint 7¶
8.1.17. Interactive: ArrayQueue: Ensure Capacity¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
ArrayQueueEnsureCapacity.pdf
8.1.18. Checkpoint 8¶
8.1.19. Interactive: ArrayQueue WrapUp¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
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
