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);
}
}