Transcript Elementary Data Structures

Elementary Data Structures
CS 105
Elementary Data Structures

Stack


Queue


container of elements that are inserted and
removed last-in first-out (LIFO)
container of elements that are inserted and
removed first-in first-out (FIFO)
Deque (double-ended queue)

container of elements that allows insertion
and removal from either end
L8: Elem DS
Slide 2
Stack


Last-in, First-out (LIFO) structure
Operations






push: add element into the stack
pop: remove & return topmost element
top: return topmost element
isEmpty: check if the stack has no elements
size: return number of elements in the stack
Sample uses

“Back” button of a browser, “Undo” operation,
function/method calls
L8: Elem DS
Slide 3
Stack Interface
public interface Stack
{
public int size();
public boolean isEmpty();
public void push( Object o );
public Object top() throws EmptyStackException;
public Object pop() throws EmptyStackException;
}
public class EmptyStackException extends RuntimeException
{
}
L8: Elem DS
Slide 4
Array Implementation
top
3
S
public class ArrayStack implements Stack
{
private int top = -1;
private Object S[];
...
}
...
x
z
y
w
L8: Elem DS
Slide 5
Array Implementation Details


An array of objects stores the elements
An integer field points to the topmost
element



Value of top is –1 when the stack is empty
A constant indicates the size/capacity of
the array
Throw a StackFullException when a push
is attempted on a full array
L8: Elem DS
Slide 6
ArrayStack class
public class ArrayStack implements Stack
{
public static final int CAPACITY = 1000;
private Object S[];
private int top;
public ArrayStack()
{
S = new Object[CAPACITY];
top = -1;
}
public boolean isEmpty()
{
return (top < 0);
}…
}
L8: Elem DS
Slide 7
ArrayStack class continued
public class ArrayStack implements Stack
{…
public int size()
{
return (top + 1);
}
}
public void push(Object obj) throws FullStackException
{
if (size() == CAPACITY)
throw new FullStackException();
S[++top] = obj;
public class FullStackException
}
extends RuntimeException
…
{
}
L8: Elem DS
Slide 8
ArrayStack class continued
public class ArrayStack implements Stack
{…
public Object top() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
return S[top];
}
public Object pop() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
return S[top--];
}…
}
L8: Elem DS
Slide 9
Garbage collection

After a pop() operation, array still
contains reference to popped element


Succeeding push() operations will override
such references but it is not certain whether
pushes will occur after the pops
Better to set the reference to null so that
the object is garbage-collected when no
longer in use
L8: Elem DS
Slide 10
Improved pop() method
public class ArrayStack implements Stack
{…
public Object pop() throws EmptyStackException
{
Object elem;
if (isEmpty())
throw new EmptyStackException();
elem = S[top];
S[top--] = null; // dereference S[top] for garbage collection.
return elem;
}
…
}
L8: Elem DS
Slide 11
Using the Stack
Stack s1 = new ArrayStack();
String temp;
s1.push( "easy" );
s1.push( "this" );
temp = (String) s1.pop();
System.out.print( temp );
s1.push( "is" );
s1.push( "class" );
while ( !s1.isEmpty() )
{
temp = (String) s1.pop();
System.out.print( " "+ temp
}
System.out.println();
OK because
Strings are
Objects
Cast object
to String
);
L8: Elem DS
Slide 12
Stack of ints
Stack s2 = new ArrayStack();
s2.push( 5 );
s2.push( 2 );
s2.push( 3 );
int num = (Integer) s2.pop();
System.out.println( num );
Note: In previous Java versions,
s2.push( new Integer( 2 ) );
num = ( (Integer) s2.pop() ).intValue();
Allowed in Java 1.5
because primitive
type values are
“auto-boxed”
Cast object to
Integer type
(not int)
L8: Elem DS
Slide 13
Time Complexity Analysis





push() :
pop() :
isEmpty() :
size() :
top():
O(1)
O(1)
O(1)
O(1)
O(1)
L8: Elem DS
Slide 14
Array Implementation Alternative



Make top variable point to next available
array position instead of actual topmost
element
top = 0 when empty
top
4
top represents size
S
...
x
z
y
w
L8: Elem DS
Slide 15
Problems with ArrayStack


CAPACITY needs to be specified
Consequences



stack may fill up (when size() == MAX )
memory is wasted if actual stack
consumption is way below maximum
Need a more “dynamic” implementation
L8: Elem DS
Slide 16
Linked List Implementation
top
null
y
z
w
A stack as a sequence of nodes
L8: Elem DS
Slide 17
The Node class
public class Node
{
private Object element;
private Node next;
public Node( Object e, Node n )
{
element = e;
next = n;
}
public Object getElement() …
public Node getNext() …
public void setElement( Object newElem ) …
public void setNext( Node newNext ) …
}
y
L8: Elem DS
Slide 18
Linked List Implementation

Stack is represented by a Node reference
(called top)



This reference is null when stack is empty
Top refers to the top element only but
links in each node keep the elements
together
An integer field represents the number of
elements in the stack
L8: Elem DS
Slide 19
NodeStack class
public class NodeStack implements Stack
{
private Node top;
private int size;
public NodeStack()
{
top = null;
size = 0;
}
public boolean isEmpty()
{
return (top == null);
}…
}
L8: Elem DS
Slide 20
NodeStack class continued
public class NodeStack implements Stack
{…
public int size()
{
return size;
}
public void push( Object obj )
{
Node v = new Node( obj, top );
top = v;
size++;
}
…
}
L8: Elem DS
Slide 21
Push operation
top
size
3
null
y
z
w
L8: Elem DS
Slide 22
Push operation
top
size
3
null
x
y
z
w
Create node
L8: Elem DS
Slide 23
Push operation
top
size
4
null
x
y
z
w
Update top
and size
L8: Elem DS
Slide 24
NodeStack class continued
public class NodeStack implements Stack
{…
public Object top() throws EmptyStackException
{
if ( isEmpty() )
throw new EmptyStackException();
return top.getElement();
}
public Object pop() throws EmptyStackException
{
if ( isEmpty() )
throw new EmptyStackException();
Object temp = top.getElement();
top = top.getNext();
size--;
return temp;
}…
}
L8: Elem DS
Slide 25
Pop operation
top
size
4
null
x
y
z
w
L8: Elem DS
Slide 26
Pop operation
top
size
4
null
x
y
z
w
temp
Get top element
L8: Elem DS
Slide 27
Pop operation
top
size
3
null
x
y
z
w
temp
Update top
and size
L8: Elem DS
Slide 28
Pop operation
top
size
3
null
x
y
z
w
temp
Node automatically
disposed
L8: Elem DS
Slide 29
Pop operation
top
size
3
null
x
y
z
w
Return element
L8: Elem DS
Slide 30
Using the NodeStack
Stack s2 = new NodeStack();
s2.push( 5 );
s2.push( 2 );
s2.push( 3 );
int num = (Integer) s2.pop();
System.out.println( num );
Only this line changed
L8: Elem DS
Slide 31
Time Complexity Analysis





push() :
pop() :
isEmpty() :
size() :
top():
O(1)
O(1)
O(1)
O(1)
O(1)
L8: Elem DS
Slide 32
ArrayStack versus NodeStack




NodeStack uses only the memory that it
needs at any given time
NodeStack has no size limit
(just the system’s memory) –
FullStackException not thrown
ArrayStack’s implementation is simpler
Which implementation is more efficient?
L8: Elem DS
Slide 33
Managing Multiple Implementations

Note that we now have two
implementations of a Stack:
public class ArrayStack implements Stack
{…}
public class NodeStack implements Stack
{…}

Consider what code needs to be changed
if we shift between implementations

It would be preferable if the code that uses
the stack does not need to be updated
L8: Elem DS
Slide 34
A StackFactory Class

Use a separate class that produces Stack objects
public class StackFactory
{
public static Stack createStack()
{
return new ArrayStack();
// or return new NodeStack();
}
}

Advantage:


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!
L8: Elem DS
Slide 35
Using a StackFactory
Stack s2 = StackFactory.createStack();
s2.push( 5 );
s2.push( 2 );
this line need not be
s2.push( 3 );
changed even if the
int num = (Integer) s2.pop();
stack implementation
changes
System.out.println( num );
L8: Elem DS
Slide 36
Queue


First-in, First-out (FIFO) structure
Operations






enqueue: insert element at rear
dequeue: remove & return front element
front: return front element
isEmpty: check if the queue has no elements
size: return number of elements in the queue
Sample use

handling requests and reservations
L8: Elem DS
Slide 37
The Queue Interface
public interface Queue
{
public int size();
public boolean isEmpty();
public void enqueue( Object o );
public Object front() throws EmptyQueueException;
public Object dequeue() throws EmptyQueueException;
}
public class EmptyQueueException extends RuntimeException
{
}
L8: Elem DS
Slide 38
Array Implementation Possibilities

On enqueue, place element in the next
available slot; on dequeue, remove
element at position 0 and move all other
elements to the left


Dequeue takes O(n) time
Have integer pointers to front and rear,
increment rear on enqueue, increment
front on dequeue, so that both
operations are O(1)
L8: Elem DS
Slide 39
Array Implementation of a Queue

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
...
L8: Elem DS
Slide 40
ArrayQueue
public class ArrayQueue implements Queue
{
public static final int CAPACITY = 1000;
private Object s[];
private int front, rear;
public ArrayQueue()
{
s = new Object[CAPACITY];
front = rear = 0;
}
...
}
L8: Elem DS
Slide 41
isEmpty and Enqueue
public class ArrayQueue implements Queue
{ ...
public boolean isEmpty()
{
return ( front == rear );
}
public void enqueue( Object o ) throws FullQueueException
{
if ( rear == CAPACITY )
throw new FullQueueException();
s[rear++] = o;
}
...
public class FullQueueException
extends RuntimeException
}
{
}
L8: Elem DS
Slide 42
Enqueue operation
front
0
rear
3
...
L8: Elem DS
Slide 43
Enqueue operation
front
0
rear
4
...
Enqueued
object
L8: Elem DS
Slide 44
Dequeue
public class ArrayQueue implements Queue
{
...
public Object dequeue() throws EmptyQueueException
{
if ( isEmpty() )
throw new EmptyQueueException();
return s[front++];
}
…
}
L8: Elem DS
Slide 45
Dequeue operation
front
0
rear
4
...
L8: Elem DS
Slide 46
Dequeue operation
front
1
rear
4
...
Return this
object
L8: Elem DS
Slide 47
Dequeue operation
Remember
to set
reference
in array to
null
front
1
null
rear
4
...
L8: Elem DS
Slide 48
Dequeue with Garbage Collection
public class ArrayQueue implements Queue
{ ...
public Object dequeue() throws EmptyQueueException
{
if ( isEmpty() )
throw new EmptyQueueException();
Object data = s[front];
s[front] = null;
front++;
return data;
}
}
L8: Elem DS
Slide 49
Circular Array



Suppose many enqueue operations
followed by many dequeue operations
Result: rear approaches CAPACITY but
the queue is not really full
Solution: Circular Array

allow rear (and front) to “wrap around” the
array (if rear = CAPACITY-1, incrementing
rear means resetting it to 0)
L8: Elem DS
Slide 50
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:
when ( (rear+1) % CAPACITY == front)
(one free slot left)
empty: when ( rear == front )
Note: “wastes” a slot



alternative: have a boolean field called hasElements
full: when ( hasElements && (rear == front))
But not really better


hasElements takes up extra space too
Also, need to take care of hasElements in enqueue and dequeue
L8: Elem DS
Slide 51
Revised Enqueue
public class ArrayQueue implements Queue
{
...
public void enqueue( Object o ) throws FullQueueException
{
if ((rear+1) % CAPACITY == front)
throw new FullQueueException();
s[rear] = o;
rear = (rear + 1) % CAPACITY;
}
...
}
L8: Elem DS
Slide 52
Revised Dequeue
public class ArrayQueue implements Queue
{ ...
public Object dequeue() throws EmptyQueueException
{
if ( isEmpty() )
throw new EmptyQueueException();
Object data = s[front];
s[front] = null;
front = (front + 1) % CAPACITY;
return data;
}
…
}
L8: Elem DS
Slide 53
Completing the Dequeue class
public class ArrayQueue implements Queue
{ ...
public int size()
{
return (CAPACITY + rear – front) % CAPACITY;
}
…
public Object front() throws EmptyQueueException
{
if ( isEmpty() )
throw new EmptyQueueException();
return s[front];
}
…
}
L8: Elem DS
Slide 54
Time Complexity Analysis





enqueue() :
dequeue() :
isEmpty() :
size() :
front():
O(1)
O(1)
O(1)
O(1)
O(1)
L8: Elem DS
Slide 55
Dynamic Implementation



Queue is represented by a linked
sequence of nodes
Two node references refer to front and
rear element, respectively
Use a size field to monitor number of
elements
L8: Elem DS
Slide 56
Linked List Implementation
front
public class NodeQueue implements Queue
{
private Node front;
private Node rear;
rear
private int size;
…
}
null
L8: Elem DS
Slide 57
Enqueue
front
rear
null
null
L8: Elem DS
Slide 58
Dequeue
front
rear
null
return this object
L8: Elem DS
Slide 59
NodeQueue considerations



Exercise: complete the NodeQueue class
Note that the queue is empty when both
front and rear are null
Need to watch out for special cases


Enqueue from an empty queue
Dequeue from a single-element queue
L8: Elem DS
Slide 60
Deque


Data structure that allows insertion and
deletion from either end of structure
Operations






insertFirst, insertLast: add element
removeFirst, removeLast: remove element
first: return first element
last: return last element
isEmpty: check if the deque has no elements
size: return number of elements in the deque
L8: Elem DS
Slide 61
Deque Interface
public interface Deque
{
public int size();
public boolean isEmpty();
public void insertFirst( Object o );
public void insertLast( Object o );
public Object first() throws EmptyDequeException;
public Object last() throws EmptyDequeException;
public Object removeFirst() throws EmptyDequeException;
public Object removeLast() throws EmptyDequeException;
}
public class EmptyDequeException extends RuntimeException
{
}
L8: Elem DS
Slide 62
Array Implementation of a Deque



Circular array implementation
Integer pointers to first and last element
Insertion/removal operations





insertFirst: decrement first pointer
removeFirst: increment first pointer
insertLast: increment last pointer
removeFirst: decrement last pointer
Decide whether pointers should point to actual
element or next available space

Impacts on full/empty conditions
L8: Elem DS
Slide 63
Dynamic Implementation of a Deque

Linked List implementation
first
last
null
L8: Elem DS
Slide 64
Deque using a Singly Linked List


insertFirst, removeFirst, insertLast are
O(1) operations
removeLast is an O(n) operation



Why?
Need to update last pointer to point to
second-to-the-last element
How can we make all operations O(1)?

Have a link to next and previous nodes
L8: Elem DS
Slide 65
Doubly Linked List
first
null
last
null
L8: Elem DS
Slide 66
The DLNode class
public class DLNode
{
private Object element;
private DLNode next, prev;
public Node( Object e, DLNode n, DLNode p )
{
element = e; next = n; prev = p;
}
public Object getElement() …
public DLNode getNext() …
public DLNode getPrev() …
public void setElement( Object newElem ) …
public void setNext( DLNode newNext ) …
public void setPrev( DLNode newPrev ) …
}
L8: Elem DS
Slide 67
Deque using a Doubly Linked List

insertFirst, removeFirst, insertLast, removeLast
are O(1) operations


Empty and single-element cases



Need to update next and prev pointers in DLNode
Insertion from the empty case (both pointers are
null) and removal from a single-element case (both
point to the single element) need to be handled
Or, make pointers point to dummy nodes (also called
sentinels), so that insertion and removal need not
worry about the special cases
size field: as in singly-linked implementation,
storing size makes isEmpty() and size() easier
L8: Elem DS
Slide 68