Transcript DSinJ

Data Structures in Java
Elementary Data Structures

Stack


Queue


container of elements that are inserted
and removed first-in first-out (FIFO)
Linked List



2/26/02
container of elements that are inserted
and removed last-in first-out (LIFO)
chain of elements
can grow dynamically
often used to implement other data
structures
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 2
Stack


Last-in, First-out (LIFO) structure
Operations




push: add element into the stack
pop: remove & return topmost element
empty: check if the stack has no elements
Sample uses

2/26/02
“Back” button of a browser, “Undo”
operation, function/method calls
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 3
Array Implementation
for a Stack of ints
public class ArrayStack
{
int store[];
int top;
static final int MAX = 100;
public ArrayStack()
{
store = new int[MAX];
top = 0;
}
// ...
top
4
top = index of the
first FREE
slot
}
12 24
2/26/02
37 17
...
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 4
ArrayStack class, continued
public class ArrayStack
{ // ...
public boolean empty()
{
return (top == 0);
}
public void push(int entry)
{
if (top < MAX)
store[top++] = entry;
}
// ...
}
12 24
2/26/02
37 17
// in the code that uses
// the stack …
stack.push( 95 );
Remember:
top = index of the
first FREE
slot
top
45
95
...
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 5
ArrayStack class, continued
public class ArrayStack
{
// ...
public int pop()
throws Exception
{
if ( empty() )
throw new Exception();
else
return store[--top];
}
}
12 24
2/26/02
37 17
// in the code that uses
// the stack …
int x = stack.pop();
// x gets 95,
// slot 4 is now free
Remember:
top = index of the
first FREE slot
top
54
95
Store[4] still contains
95, but it’s now
considered “free”.
...
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 6
Using the Stack
try
{
ArrayStack st = new ArrayStack();
st.push( 1 ); st.push( 3 ); st.push( 2 );
System.out.println( st.pop() );
st.push( 5 );
System.out.println( st.pop() );
System.out.println( st.pop() );
}
catch ( Exception e )
{
System.out.println( “pop() on empty stack” );
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 7
Problems with Array
Implementation


MAX needs to be specified
Consequences



stack may fill up (when top == MAX)
memory is wasted if actual stack
consumption is way below maximum
Need a more “dynamic” implementation
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 8
Linked List Implementation

Stack as a sequence of nodes
top
5
2/26/02
1
3
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
2
null
Slide 9
Integer Node
public class IntNode
{
int data;
IntNode next;
// set
public
public
public
public
& get methods for data and next
void setData( int data ) ...
int getData() ...
void setNext( IntNode next ) ...
IntNode getNext() ...
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 10
Linked List as a Data Structure

Operations on a linked list





insert a node somewhere in the list
get next node
delete a node from the list
The IntNode class supports the Linked
List structure
Linked List Implementation of a Stack:

2/26/02
an example of a data structure implemented
through another data structure
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 11
LinkedStack Class
public class LinkedStack
{
IntNode top;
public LinkedStack()
{
top = null;
}
public boolean empty()
{
return (top == null);
}
// ...
}
top
5
2/26/02
1
3
2
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
null
Slide 12
Push Operation using a List
// in the code
// that uses the
// stack
stack.push( 7 );
temp
top
public class LinkedStack
{
// ...
public void push( int entry )
{
IntNode temp = new IntNode();
temp.setData( entry );
temp.setNext( top );
top = temp;
}
// ...
}
X
7
2/26/02
5
1
3
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
2
null
Slide 13
Pop Operation using a List
// in the code
// that uses the
// stack
int x = stack.pop();
temp
top
7
Garbage
Collected
7
2/26/02
X
5
public class LinkedStack
{
// ...
public int pop() throws Exception
{
if ( empty() )
{ throw new Exception();
}
else
{
int temp = top.getData();
top = top.getNext();
return temp;
}
}
}
1
3
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
2
null
Slide 14
Separating Interface from
Implementation

Better if there is a Stack interface that
both ArrayStack and LinkedStack
implements
public interface Stack
{
public void push( int entry );
public int pop() throws Exception;
public boolean empty();
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 15
Stack Implementations
public class ArrayStack implements Stack
{
...
}
public class LinkedStack implements Stack
{
...
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 16
A StackFactory Class

Use a separate class that produces Stack objects
public class StackFactory
{
public static Stack createStack()
{
return new ArrayStack();
// or return new LinkedStack();
}
}

Advantage:


2/26/02
if you want to change your implementation, you just need to
change StackFactory
you don’t need to change all calls to new ArrayStack in all your
code!
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 17
Sample Code
(application that uses a stack)
Stack st;
st = StackFactory.createStack();
// above statement does not know or care
// how the stack is implemented
st.push(1); st.push(3); st.push(2);
System.out.println( st.pop() );
// ...
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 18
A Generic Stack

Make the stack data an instance of
Object



Array implementation:


can work with any kind of object, not just int
you can use Integer class for int data (same
for other primitive types)
store is an Object[], instead of int[]
Linked List implementation:


2/26/02
use ObjectNode (not just IntNode)
more code later
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 19
Linked Stack of Objects
top
null
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 20
Java’s Stack Class


Good news: the java.util package already
has a Stack (of objects) class
Methods available


2/26/02
javap java.util.Stack
others besides push, pop, and empty
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 21
Queue


First-in, First-out (FIFO) structure
Operations




enqueue: insert element at rear
dequeue: remove & return front element
empty: check if the queue has no elements
Sample use

2/26/02
handling requests and reservations
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 22
The Queue Interface
public interface Queue
{
public void enqueue( Object entry );
public Object dequeue() throws Exception;
public boolean empty();
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 23
Array Implementation of Queues

An Object array and two integers


front: index of first element in queue
rear: index of first FREE element in queue
front
0
rear
4
...
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 24
ArrayQueue
public class ArrayQueue implements Queue
{
Object store[];
int front, rear;
static final int MAX = 100;
public ArrayQueue()
{
store = new Object[MAX];
front = rear = 0;
}
// ...
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 25
Check for Empty and Enqueue
public class ArrayQueue implements Queue
{ // ...
public boolean empty()
{ // queue is empty if first element
// is the same as the first free element
return ( front == rear );
}
public void enqueue( Object o )
{ // put data in first free slot
// move rear index to next slot
if ( rear < MAX )
store[rear++] = o;
}
// ...
rear
front
}
4
0
...
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 26
Dequeue Operation
public class ArrayQueue implements Queue
{
// ...
public Object dequeue() throws Exception
{
if ( empty() )
{ throw new Exception();
}
else
{ return store[front++];
}
rear
}
front
}
4
0
...
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 27
Dequeue that allows GC
public class ArrayQueue implements Queue
{ // …
public Object dequeue() throws Exception
{
if ( empty() )
{ throw new Exception();
}
else
{ Object data = store[front]; // get front data
// set pointer to null, so it can be garbage-collected
// later (when caller code doesn’t let’s go of pointer
store[front] = null;
front++;
return data;
}
}
rear
front
}
0
4
...
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 28
Circular Array



Suppose many enqueue operations
followed by many dequeue operations
Result: rear approaches MAX but the
queue is not really full
Solution: Circular Array

2/26/02
allow rear (and front) to “wrap around” the
array (if rear = MAX-1, incrementing rear
means resetting it to 0)
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 29
Circular Array, continued

When is the array full?



Solution: Reserve a slot



Simple answer: when (rear == front)
Problem: this is the same condition as empty
full:
empty:
when ( (rear+1) % MAX == front) (one free slot left)
when ( rear == front )
Note: “wastes” a slot



alternative: have a boolean field called hasElements
full: when ( hasElements && (rear == front))
But not really better


2/26/02
hasElements takes up extra space too
Also, need to take care of hasElements in enqueue and dequeue
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 30
Revised Enqueue
public class ArrayQueue implements Queue
{
// ...
public void enqueue( Object o )
{
if ( (rear + 1) % MAX != front )
{
store[rear] = o;
rear = (rear + 1) % MAX;
}
}
// ...
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 31
Revised Dequeue
public class ArrayQueue implements Queue
{
// ...
public Object dequeue() throws Exception
{
if ( empty() )
{ throw new Exception();
}
else
{ Object data = store[front];
store[front] = null;
front = (front + 1) % MAX;
return data;
}
}
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
}
2/26/02
Ateneo de Manila University
Slide 32
Using the Queue
Queue q = new ArrayQueue();
int result;
// the following should be enclosed in a try-catch
stmt
q.enqueue( new Integer(5) );
q.enqueue( new Integer(2) );
result = ((Integer)q.dequeue()).intValue();
System.out.println(result);
q.enqueue( new Integer(3) );
result = ((Integer)q.dequeue()).intValue();
System.out.println( result );
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 33
Linked List Implementation
front
rear
null
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 34
The ObjectNode Class
public class ObjectNode
{
Object data;
ObjectNode next;
public
public
public
public
void setData( Object o ) { data = o; }
Object getData() { return data; }
void setNext( ObjectNode p ) { next = p; }
ObjectNode getNext() { return next; }
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 35
Enqueue
front
rear
null
null
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 36
Dequeue
front
rear
null
return this object
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 37
The LinkedQueue Class
public class LinkedQueue implements Queue
{
ObjectNode front;
ObjectNode rear;
public LinkedQueue()
{
front = rear = null;
}
// other Queue methods
}
2/26/02
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 38
Exercise: Snake game

Run the game



Note that it uses an instance of the Queue interface
currently, it uses ArrayQueue, as defined in lecture
Complete the LinkedQueue class

need to worry about





the “empty-queue” case
and the case where the queue has only 1 element
Modify QueueFactory class to create a
LinkedQueue instead of ArrayQueue
Test your LinkedQueue by running Snake
Enhance/Fix Snake

2/26/02
e.g., add a border, add special points, etc.
© 2002 Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Slide 39