Collections
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

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.

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.

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

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