1. Queues¶
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
1.1.1. Suggested Reading¶
Chapter 10: Queues, Deques, and Priority Queues & Chapter 11: Queue, Deque, and Priority Queue Implementations from <https://www.amazon.com/Data-Structures-Abstractions-Java-4th/dp/0133744051/ref=sr_1_1?ie=UTF8&qid=1433699101&sr=8-1&keywords=Data+Structures+and+Abstractions+with+Java>`_ by Frank M. Carrano and Timothy Henry
1.2. Queues¶
1.2.1. [8:50] Queue Intro Video¶
TODO: fix URLS.
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
1.2.2. Checkpoint 1¶
1.2.4. Checkpoint 2¶
1.2.6. Checkpoint 3¶
1.3. Deques¶
1.3.1. [13:51] Deque Intro Video¶
TODO: fix URLS.
asdf
1.3.1.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
1.3.3. Checkpoint 5¶
1.4. Array Implementation of Queues¶
1.4.2. Checkpoint 6¶
1.4.4. Checkpoint 7¶
1.4.6. Checkpoint 7¶
1.4.7. [6:59] ArrayQueue WrapUp Video¶
TODO: fix URLS.
1.4.7.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
