The Data Structures test

has been delayed until Thursday.

HW #4.1: Write a Priority Queue of ints. A collection. size, isempty, enqueue, dequeue.

Here is a link to the sample midterm.

HW: modify your Stack to make it Iterable.

class MyStack<T> implements Iterable
{
Iterator<T> iterator()
{
return new MyIterator<T>(this);
}

}

class MyIterator<T> implements Iterator
{
// a copy of my Stack array
T arr;
int curEl = -1;
MyIterator(MyStack<T> ms)
{
arr = new T[ms.top]
for loop to copy ms.arr into this.arr
}
T next()
{
return arr[++curEl];
}
boolean hasNext()
{
return curEl == arr.length;
}

}

This code is probably buggy

LLast part of this data structure.

Moving on: Implement Huffman tree encoding
we will need MANY interacting data structures
binary trees, priority queues, interfaces like comparator and comparable, etc.

The slides implement a Stack based on a Singly Linked list by *reimplementing* the necessary subset of methods of the Singly linked list class.

What *I* would suggest:
*Assume* you have a Singly Linked List class already. Make it a private data member. Adapt the Singly Linked to be a SLLStack by wrapping the methods.

class NodeStack<E>
{
protected SLL<E> sll; //
public NodeStack<E>() { // constructs an empty stack
sll = new SLL(); }
public int size() { return sll.size(); }
public boolean isEmpty() {return sll.size()==0;}
public void push(E elem) {
sll.insertFront(elem);
}
public E top() throws EmptyStackException {
     if (sll.isEmpty()) throw new EmptyStackException("empty");
return sll.returnFront(); // find some way to get access to the first elem
}
   public E pop() throws EmptyStackException {   if (sll.isEmpty()) throw new EmptyStackException("empty");       return sll.removeFront();}
}
dequeue (pronounced dee-kyoo) means remove from a queue (kyoo)

deque (pronounced deck) is a certain data structure

What about "my" way of writing a Queue based on a SLL?
class MyQueue<E>
{
protected SLL<E> sll; // reference to the head node  
void enqueue(E elem)
{
sll.insertAtEnd(elem);
}

E dequeue()
{
if (sll.isEmpty())
crashAndBurn();
return sll.removeFront();
}
}

Link to the sample midterm
https://docs.google.com/View?id=ajbqhgmq9qdz_59khz242gh&pli=1

The midterm will be Tuesday, Nov 1, 2011

class DList
{
   DNode prev(DNode current)
   {
return current.prev;
   }
}

main()
{
DNode j;
DList dl;
//...
j.getPrev(); // no! Don't do that!
dl.prev(j);

dl.replace(j, 6);
}



class ArrayBasedStack<T> implements Iterable<T>
{
/// ...
Iterator<T> iterator() { return new ArrayBasedStackIterator<T>();  }
}

class ArrayBasedStackIterator<T> implement Iterator<T>
{
boolean hasNext() { return false; }
Iterator<T> next() { return null; }
}


for (Iterator<T> it = L.iterator(), it.next(); it.hasNext() == true;
it.next())




List<Integer> values;


// ... statements that create a new // values list and int sum = 0;

Iterator<Integer> it = values.iterator();
for (Integer i = it.next(); it.hasNext(); it.next())
{ sum += i; }




class ArrayBasedStack<E> implements java.util.Queue<E>
{
public void push(E o) { A[top++]=o; }
public boolean add(E o)
{
push(o);
}
}

HW: Modify your Stack code to make use of the Queue<T> interface.

Unfortunately, there does not seem to be a Stack<T> interface, just a Stack<T> class. They recommend using the Deque interface and calling the associated stack methods instead of this Stack class. However, I don't want you to have to implement every single method associated with a Deque interface. Instead, implement the superinterface to Deque, which is java.util.Queue<T>.

Certain inherited methods from the superinterface Collection it does not make sense to implement. For example, why get an iterator? The rules for a stack are such that we can only see the top element. The same for the contains method. Therefore, only focus on the ones that are directly mentioned in the documentation for Queue, except, mentally substitute stack for queue:

Method Summary
boolean	add(E e)           Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E	element()           Retrieves, but does not remove, the head of this queue.
boolean	offer(E e)           Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E	peek()           Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E	poll()           Retrieves and removes the head of this queue, or returns null if this queue is empty.
E	remove()           Retrieves and removes the head of this queue.

In addition, the following from the superinterface Collection makes sense to implement:

Methods inherited from interface java.util.Collection
addAll, clear, equals, isEmpty, size, toArray, toArray

function addToFront(value x): #DLinked List, no 'header'
n = new Node(x)
n.next = head
n.prev = null

head.prev = n
head = n
size++
#actually, have to test for 0 elements to set tail

function addToFront(value x): #DLinked List, with 'header'
n = new Node(x)
n.prev = header
n.next = header.next
header.next = n
n.next.prev = n
size++

HW:
templatize your stack class