.. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :author: Molly Domino Queues ====== 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 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 .. _QueueIntro: Interactive: Introduction to Queues ----------------------------------- .. admonition:: 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 1) create a new Eclipse project, then 2) 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 3) download and import the standalone \*.java file(s) to the created package. .. raw:: html

QueueInterface.java .. code-block:: 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 .. raw:: html

Video Slides: QueueIntro.pdf .. raw:: html Checkpoint 1 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint1Summ.html ka :long_name: Checkpoint 1 Programming Practice: Queues 1 ------------------------------ .. extrtoolembed:: 'Programming Practice: Queues 1' :workout_id: 1920 .. _QueueLinked: Interactive: Linked Queues Intro and Enqueue ---------------------------------------------------- .. admonition:: Follow Along, Practice and Explore .. raw:: html

LinkedQueuesEnqueue.pdf .. raw:: html Checkpoint 2 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint2Summ.html ka :long_name: Checkpoint 2 Interactive: Linked Queues Removing and More (Dequeue and Other Methods) ------------------------------------------------------------------------------- .. admonition:: Follow Along, Practice and Explore .. raw:: html

LinkedQueueRemove.pdf .. raw:: html Checkpoint 3 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint3Summ.html ka :long_name: Checkpoint 3 .. _QueueIntroDeque: Interactive: Introduction to Deque ---------------------------------- .. admonition:: 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 1) create a new Eclipse project, then 2) 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 3) download and import the standalone \*.java file(s) to the created package. .. raw:: html

DequeInterface.java

DequeIntro.pdf .. code-block:: java package deque; /** * An interface for the ADT dequeue. * * @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 .. raw:: html Checkpoint 4 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint4Summ.html ka :long_name: Checkpoint 4 Interactive: Deque Removing and Wrap Up ------------------------------------------------------------------------------- .. admonition:: Follow Along, Practice and Explore .. raw:: html

Video Slides DequeRemoveAndWrapUp.pdf .. raw:: html Checkpoint 5 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint5Summ.html ka :long_name: Checkpoint 5 .. _QueueArray: Interactive: ArrayQueue: Array Implementation of Queues --------------------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the videos. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

ArrayQueueIntro.pdf .. raw:: html

Checkpoint 6 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint6Summ.html ka :long_name: Checkpoint 6 Interactive: ArrayQueue: One Unused Location --------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

ArrayQueueRemove.pdf .. raw:: html Checkpoint 7 ------------- .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint7Summ.html ka :long_name: Checkpoint 7 Interactive: ArrayQueue: Ensure Capacity ------------------------------------------------ .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

ArrayQueueEnsureCapacity.pdf .. raw:: html Checkpoint 8 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/QueueCheckpoint8Summ.html ka :long_name: Checkpoint 8 Interactive: ArrayQueue WrapUp ------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

ArrayQueueWrapUp.pdf .. raw:: html .. admonition:: Empty Queue Exception .. code-block:: java 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 Programming Practice: Queues 2 ------------------------------ .. extrtoolembed:: 'Programming Practice: Queues 2' :workout_id: 1921