# 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
}
``````

# 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;
intQueue(int maxN) {
q = new int[maxN + 1];
N = maxN + 1;
tail = 0; }
boolean empty() {
return (head % N == tail); }
void put(int item) {
q[tail++] = item;
tail = tail % N; }
int get() {
}
``````
• 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);
E remove(int index);
}
``````

# Set

a set is a group of items with no order

### Interface

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

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