Transcript Abstract Data Types (ADT)

Abstract Data Types (ADT)
• Collection
– An object that can hold a list of other objects
• Homogeneous Collection
– Contains elements all of the same type
– Example: Array of integers
• Heterogeneous Collection
– Contains elements of differing types
– Example: The Java Stack
• Abstract Data Type
– A data structure with a well-defined interface
– Examples: stack, queue, list, tree, graph
Stacks/Queues/Dynamic lists
Key: a well defined interface to abstract the data structure
Key: We can change the data structure without effecting users
• Stack Operations
– push, pop, isEmpty(), isFull(), look(), reset()
– look() is sometimes called peek()
• Queue Operations
– add(), remove(), isFull(), isEmpty(), reset()
• Tree Operations
– insert(), remove(), find(), traverse(), bfs(), dfs()
Implementation Possibilities
• Use generic built-in methods
– Advantage: standard data type supported by Java
– Disadvantage: lose flexibility
• Using Arrays
– Advantages: fast, native Java data structure
– Disadvantage: The size must be known in advance
• Dynamic storage
– Advantage: The structure can grow and shrink
– Disadvantage: Executes more slowly
A Stack Example
Reverse a String
public static void main( String args[] )
{ Stack stack = new Stack();
String string = "Hello this is a test string";
System.out.println("String: " + string);
for (int k = 0; k < string.length(); k++)
stack.push(new Character( string.charAt(k)));
Object obj = null;
String reversed = "";
while (!stack.isEmpty())
{ obj = stack.pop();
reversed = reversed + o.toString();
}
System.out.println("Reversed: " + reversed);
}
Java Generic Classes
• Vector
Vector<String> vec = new Vector<String>();
vec.addElement("alpha"); rec.addElement("beta");
System.out.println(vec.elementAt(0));
• Stack
Stack<String> stk = new Stack<String>();
stk.push("alpha"); stk.push("beta");
System.out.println(stk.pop());
• LinkedList
List<PhoneRecord> link = new LinkedList<PhoneRecord>();
link.add(new PhoneRecord("Roger", "(541) 997-2918"));
for (PhoneRecord pr : theList) System.out.println(pr);
• Java has many other generic interfaces and classes
– Examples: Set, Map, Hashtable
Stack of doubles with Arrays
public class Stack
{ int top;
double[] data;
public Stack(int size)
{ data = new double[size]; top = -1; }
public void push(double x) throws Exception
{ if (!isFull() { data[++top] = value; }
else throw new Exception(); }
public double pop()
{ if (!isEmpty()) return data[top--];
else throw new StackException(); }
public boolean isEmpty() {return (top==-1); }
public boolean isFull()
{return (top==data.length-1);}
public double peek() throws Exception()
{ if (!isEmpty()) {return data[top];}
else throw new StackException(); } }
Algorithm: Evaluating InfixExpressions
Instantiate two stacks: operator, operand
Remove white space from the string expression
Break string expression into tokens (delimeters = "+-/*()")
WHILE more tokens exist, get nextToken
SWITCH nextToken
Left paren: push '(' on operator stack
): WHILE top of operator stack !='(' THEN CALL Eval()
Pop the matching (
+ or –: WHILE top of operator stack is '+', '-', '*', or '/'
THEN CALL eval()
push nextToken to operator stack
* or /: WHILE top of operator() stack is '*' or '/'
THEN CALL eval()
push nextToken to operator stack
DEFAULT: Convert to double & push nextToken to operand stack
WHILE operator stack is not empty THEN CALL eval()
Result is on top of operand stack
Note: eval() method
pop two operands and one operator, calculate, and push result to operand stack
Example Expression Algorithm
Evaluate: "1+2*16/4"
push 1 to operand
push '+' to operator
push 2 to operand
push '*' to operator
push 16 to operand
Call Eval: pop 16, pop 2, pop '*', 2*16->32, push 32 to operand
push '/' to operator
push 4 to operand
Call Eval: pop 4, pop 32, pop '/,' 32/4->8, push 8 to operand
Call Eval: pop 8, pop 1, pop '+,' 1+8->9, push 9 to operand
Result is at top of operand stack (9)
Example Expression Algorithm
Evaluate: "3+(5+6/2)*3/2-4"
push 3 to operand, push '+' to operator, push '(' to operator
push 5 to operand, push '+' to operator, push 6 to operand
push '/' to operator, push 2 to operand
Call Eval: pop 2, pop 6, pop '/', 6/2->3, push 3 to operand
Call Eval: pop 3, pop 5, pop '+', 5+3->8, push 8 to operand
pop '('
push '*' to operator, push 3 to operand
Call Eval: pop 3 pop 8, 8*3->24, push 24 to operand
push '/' to operator, push 2 to operand
Call Eval: pop 2, pop 24, 24/2->12, push 12 to operand
push '-' to operator, push 4 to operand
Call Eval: pop 4, pop 12, 12-4->8, push 8 to operand
Call Eval: pop 8, pop 3, 3+8->11, push 11to operand
Result is at top of operand stack (11)
Queue Concepts using Arrays
• A circular array
– We store data in
consecutive locations
– When we reach the
bottom, we then wrap
around to the top
• Example
– Goal: Store x at next
location in an array, data
– Assume: we stored the
last element at offset j
– Java Code: j =
(j+1)%data.length; data[j]
= x;
j
0
4.2
1
9.2
2
7.5
3
1.9
4
0.4
data
Question: if x=3.5, where is it stored? What if j=2?
Queues with an array implementation
• Instance variables
– int head, int tail, double data[]
– We add to the tail and remove from the head
– We update the tail on insertion, and update the head on
removal.
• How do we check if the queue is full?
– Answer: Check if the next tail location equals the head
• How do we remove an item
– Answer: Extract from the head and increment the
pointer. If the head and tail pointers become equal, we
set both to minus one.
Using dynamic storage
Class Node
{
Object info;
Node next;
public Node(Object data)
{ info=data; next=null; }
}
node1 = new Node("alpha");
node1.next = new Node("beta");
node1.next.next
= new Node("gamma");
"alpha"
"beta"
"gamma"
X
Doubly linked
• Doubly linked node
class Node
{ String info;
Node next;
Node previous;
}
• Tree nodes
class Node
{int info; Node[] next; }
Doubly Linked
Class Node
{ Object info;
Node next;
public Node(Object data)
{ info=data; next = prev =null; }
}
Node node1 = new Node("alpha");
Node node2 = new Node("gamma");
Node node3 = "new Node("gamma");
node1.next = node2;
node2.next = node3;
node3.prev = node2;
node2.prev = node1;
X
"alpha"
X
"beta"
"gamma"
X