Abstract Data Types

Generic structures

Implementation separate from structure

Stacks

Push takes an element as a parameter:

push(E)

Pop returns an element

E pop()

LIFO – Last In First Out

Exercises

1. A letter means push and an asterisk means pop in the sequence

   E A S * Y * Q U E * * * S T * * * I O * N * * *.`
   

   Give the sequence of values returned by the pop operations.

2. Give a way to insert asterisks in the sequence E A S Y so that the sequence of values returned by the pop operations is

   a. E A S Y b. Y S A E c. A S Y E d. A Y E S

   or, in each instance, prove that no such sequence exists.

3. Given two sequences, give an algorithm for determining whether or not asterisks can be added to make the first produce the second.

Interface

interface intStack { 
	intStack(int)  //param optional: size of stack
	boolean isEmpty()
	void push(int)
	int pop() 
	int peek() //sometimes
} 

Implementation

• Arrays?
• Nodes? (next week )
• Java Stack Reference

Functions: Extensions

Queues

Put takes an element as a parameter

put(E)

get returns an element

get(E)

FIFO – First In First Out

Exercises

1. A letter means put and an asterisk means get in the sequence

   ```
   S I L* *L Y * R ** A B * * * B I T * * * .
   ```
   

   Give the sequence of values returned by the get operations when this sequence of operations is performed on an initially empty FIFO queue.

How would that problem work on a queue that did not allow duplicate letters?

Interface

interface intQueue 
{ 
	intQueue(int maxN) 
  	boolean empty() 
	void put(int item) 
	int get()
} 

Implementation

• an array:

class intQueue 
{ 
	private int[] q; 
	private int N, head, tail; 
	intQueue(int maxN) { 
		q = new int[maxN + 1]; 
		N = maxN + 1; 
		head = N; 
		tail = 0; } 
	boolean empty() { 
		return (head % N == tail); } 
	void put(int item) { 
		q[tail++] = item; 
		tail = tail % N; } 
	int get() { 
		head = head % N; 
		return q[head++]; } 
} 

• Nodes? (next week )
• Stacks?
  • Power question: How many stacks do you need to implement a queue? What is the net efficiency of such an implementation?
• Java Queue Reference

Functions: Queue Flavors (pick one)

• priority queue
• deque
• circular queue
• sorted queue

Lists

A list is like a dynamically sized array

we usually define add(E), E get(index), set(index, E) and remove(index)

Interface

interface List {
    E get(int index);
    E set(int index, E element);
    boolean add(E element); 
    void add(int index, E element);
    E remove(int index);
}

Implementation

• Array
• Nodes (next week )
• Java List Reference

Functions: Polymorphic

Set

a set is a group of items with no order

Interface

interface Set {
	add(E)
	remove(E)
	boolean contains(E)
}

Implementation

• 
• For now, assume only numbers 1 to 100
• Java Set Reference

Functions: Selection and Statistics

Collections Assignment

Complete a function for each datastructure: stack, queue, list, set.

H period I period C period

assessment:

5 pts for each correct function (individual) 1 pt for each completed datastructure (group) 1 pt to be determined 70 pts for free

due 10/28 extended to 10/30, resubmissions due 11/13.