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 Bags in Java
Build and populate Bags 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. Queues¶
10.2.2.1. [8:50] Queue Intro Video¶
Video Slides 10.2.2.1-QueueIntro.pdf
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
10.2.3. Checkpoint 1¶
10.2.4. Programming Practice: Queues 1¶
10.2.5. Linked Queues Intro and Enqueue¶
10.2.6. Checkpoint 2¶
10.2.7. Linked Queues Removing and More (Dequeue and Other Methods)¶
10.2.8. Checkpoint 3¶
10.2.9. Deques¶
10.2.10. Checkpoint 4¶
10.2.10.1. Deque Interface¶
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.11. Deque Removing and Wrap Up¶
10.2.11.1. [9:02] Deque Removing and Wrap Up Video Demonstration¶
Video Slides 10.2.7.1-DequeRemoveAndWrapUp.pdf
10.2.12. Checkpoint 5¶
10.2.13. Array Implementation of Queues¶
10.2.14. Checkpoint 6¶
10.2.15. ArrayQueue One Unused Location¶
10.2.16. Checkpoint 7¶
10.2.17. ArrayQueue Ensure Capacity¶
10.2.17.1. [14:06] ArrayQueue Ensure Capacity Video¶
Video Slides 10.2.10.2-ArrayQueueEnsureCapacity.pdf
10.2.18. Checkpoint 8¶
10.2.19. ArrayQueue WrapUp¶
10.2.19.1. [6:59] ArrayQueue WrapUp Video¶
Video Slides 10.2.11.1-ArrayQueueWrapUp.pdf
10.2.19.1.1. 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
