Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-04-18

posted Apr 18, 2018, 10:15 AM by Konstantinovich Samuel   [ updated Apr 18, 2018, 12:24 PM ]
Deadlines:
09StackCalc (should be done/mostly done)

10Deque (by Monday)

UPDATE 1. You can create an Object array and typecast it to E[] by suppressing the warning. I forgot that you need to place this suppression outside of the method!

public class Foo<E>{
  private E[] data;

  @SuppressWarnings("unchecked")
  public Foo(){
     data =(E[])new Object[10];
  }
}
Update2. The Deque does not allow you to store null values. So your add methods will throw exceptions.


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 interface 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. 







10Deque/MyDeque.java
  - Due Monday, April 23rd. This is not too bad if you followed the Deque in class. 

You will be writing an array-based implementation of a Deque of <E>. Use this reference for more specific info about the methods.  https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html
We are not implementing the entire Deque interface, because it is too long, and we just need a subset.


-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: 


Required methods + their exceptions
Constructors:
MyDeque() - Create an initial capacity of 10.
MyDeque(int initialCapacity) - This creates a capacity that matches the parameter. 
Throws: 
     IllegalArgumentException when the initialCapacity is negative. 

The easy method:
int size() 

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(E)
void addLast(E)
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.
removeFirst()
removeLast()
Throws:
NoSuchElementException - if this deque is empty

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




Comments