Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-04-07 HW10

posted Apr 6, 2017, 7:48 PM by Samuel Konstantinovich   [ updated Apr 12, 2017, 5:55 AM ]
(I changed my mind to make you do fewer but more meaningful assignments)

The Deque will be the next assignment to save time and because making a stack and queue first would be too easy, especially if you can use the built-in LinkedList. 
We will skip them to save time. Instead, you will work on a Deque of Strings.

  - Due Monday, April 24th. This is not too bad if you followed the Deque in class. 

You need to know the idea of a stack and a queue but can use one class to act as either of them.
The Deque class is basically a replacement for the Queue and can be used as a Stack as well. 

-This interface extends the Queue interface. When a deque is used as a queue, FIFO (First-In-First-Out) behavior results.
Elements are added at the end of the deque and removed from the beginning.

-Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.
When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. 

-You are making a resizeable deque. There is no maximum capacity. This removes the need for several exceptions.

-You are writing a circular array based representation of this class:
    Keep track of a front and back indices.
    Add to the back, remove from the front.
    When you reach the end of the array, wrap around. The modulus operator is helpful for helping keep your indices in bounds.
    When you fill the entire circular array, double the capacity, and copy the old values over. Don't forget to update the front and back indices.

    Here are some examples of a partially full circular array deque: 

You will be writing an array-based implementation of a Deque of Strings. Use this reference for more specific info about the methods.

Required methods + their exceptions

The add methods:
These will add the element to the specified side. The deque will double capacity if there is no space left.
void addFirst(String)
void addLast(String)
Throws: (this is a subset of the real deque)
NullPointerException - if the specified element is null and this deque does not permit null elements

The remove methods:
These will retrieve and remove the element from the specified side.
String removeFirst()
String removeLast()
NoSuchElementException - if this deque is empty

The get methods:
These will retrieve but not remove the element from the specified side.
String getFirst()
String getLast()
NoSuchElementException - if this deque is empty