Transcript 25-Basic Data Structures II

Abstract Data Types –II
Overview
 A stack Interface in Java
StackEmptyException
 Stack ADT(A Simple Array-Based Implementation
Queue Abstract Data Type
Problems with Array Implementation
 Dynamic Data Structures LinkedList Node Implementation
 Preview: Abstract Data Types III.
Lecture 25
1
A stack Interface in Java
Because of its importance, the stack data stucture is included
as a “built-in” class in the java.util package of Java. Class
java.util.Stack is a
structure that stores generic Java
object and includes, among others, the methods push(obj),
pop(),peek() equivalent to top()), size(), and empty()(equivalent
to isEmpty()).
Implementing an abstract data type in Java involves
two steps. The first step is definition of a Java Application
Programming Interface(API), or simply interface, which
describes the names of the methods that the ADT supports and
how they are to be declared and used. Note that this interface
is very general since it specifies that objects of arbitrary, and
possible heterogeneous classes can be inserted into the stack
Lecture 25
2
Interface Stack
/**
* Interface for a stack: a collection of objects
* that are inserted and removed according to the
* last-in first-out principle.
*/
public interface Stack {
/**
* @return number of elements in the stack.
*/
public int size();
/**
* @return true if the stack is empty, false otherwise.
*/
public Object top()
throws StackEmptyException;
/**
* Insert an element at the top of the stack.
* @param element element to be inserted.
*/
public void push (Object element);
/**
* Remove the top element from the stack.
* @return element removed.
* @exception StackEmptyException if the stack is
empty.
*/
public Object pop()
public boolean isEmpty();
/**
* @return top element in the stack.
* @exception StackEmptyException if the stack is empty.
*/
throws StackEmptyException;
}
Lecture 25
3
A Stack Interface
Lecture 25
4
StackEmptyException
Exception thrown by methods pop() and top() of the
Stack interface when called on an empty Stack
/**
* Runtime exception thrown when one tries to perform operation top or
* pop on an empty stack.
*/
public class StackEmptyException extends RuntimeException {
public StackEmptyException(String err) {
super(err);
}
}
Lecture 25
5
Stack ADT(A Simple Array-Based Implementation)
Since an array’s size needs to be determined when it is created, one of the important
details of our implementation is that we specify some maximum size N for our stack ,
say, n= 1000 elements. Our stack then consists of an N-element. A
StackFullException can be raised if we try to insert a new element and the array S is
full.
Lecture 25
6
An Array-Based Stack(algorithm)
Lecture 25
7
Array-based Java Implementation of the Stack interface
/**
* Implementation of the Stack interface using a fixed-length array.
* An exception is thrown if a push operation is attempted when the size of
* the stack is equal to the length of the array.
*/
public class ArrayStack implements Stack {
/**
* Default length of the array used to implement the stack.
*/
public static final int CAPACITY = 1000;
/**
* Lenght of the array used to implement the stack.
*/
private int capacity;
/**
* Array used to implement the stack.
*/
private Object S[];
/**
* Index of the top element of the stack in the array.
*/
private int top = -1;
/**
* Initialize the stack to use an array of default length CAPACITY.
*/
public ArrayStack() {
this(CAPACITY);
}
/**
* Initialize the stack to use an array of given length.
*
* @param cap length of the array.
*/
public ArrayStack(int cap) {
capacity = cap;
S = new Object[capacity];
}
/**
* O(1) time.
*/
public int size() {
return (top + 1);
}
Lecture 25
8
Array-based Java Implementation of the Stack interface
/**
* O(1) time.
*/
public boolean isEmpty() {
return (top < 0);
}
/**
* O(1) time.
* @exception StackFullException if the array is full.
*/
public Object top() throws StackEmptyException
{
if (isEmpty())
throw new StackEmptyException("Stack is
empty.");
return S[top];
}
/**
* O(1) time.
*/
public void push(Object obj) throws
StackFullException {
if (size() == capacity)
throw new StackFullException("Stack
overflow.");
S[++top] = obj;
}
/**
* O(1) time.
*/
public Object pop() throws StackEmptyException {
Object elem;
if (isEmpty())
throw new StackEmptyException("Stack is Empty.");
elem = S[top];
S[top--] = null; // dereference S[top] for garbage collection.
return elem;
}
}
Lecture 25
9
Casting with a Generic Stack. Example method that reverse elements
One of the strong points of our realization of the stack ADT by means of a Java class that
implements the Stack interface is that we can store generic objects in the stack, each
belonging to an arbitrary class. An ArrayStack in the previous slide can store Integer
objects, Student objects or any object . When we retrieve an object from the stack(with
either the top or pop method) we always get back a reference of type Object, no matter
what the specific class of the object is. Thus in order to use the retrieved element as an
instance of the specific class it really belongs to, we must perform a cast, which forces the
object to be viewed as a member of a specific class rather than a more general superclass
Object.
public static Integer[] reverse(Integer[] a) {
ArrayStack S = new ArrayStack(a.length);
Integer[] b = new Integer[a.length];
for (int i=0; i < a.length; i++)
S.push(a[i]);
for (int i=0; i < a.length; i++)
b[i] = (Integer) (S.pop());
return b;
}//Casting is performed to force the object returned by pop to viewed as an Integer object
Lecture 25
10
Queue Abstract Data Type
Normal configuration
Using array Q in a circular
fashion:”Wrapped around”
r (r+1)mod N
Lecture 25
11
A Queue Interface
public interface Queue {
/**
* @return number of elements in the queue.
*/
public int size();
/**
* @return true if the queue is empty, false otherwise.
*/
public boolean isEmpty();
/**
* Inspect the element at the front of the queue.
*
* @return element at the front of the queue.
* @exception QueueEmptyException if the queue is empty.
*/
public Object front() throws QueueEmptyException;
/**
* Insert an element at the rear of the queue.
*
* @param element new element to be inserted.
*/
public void enqueue (Object element);
/**
* Remove the element at the front of the queue.
*
* @return element removed.
* @exception QueueEmptyException if the queue is empty.
*/
public Object dequeue() throws QueueEmptyException;
}
Lecture 25
12
Problems with Array Implementation
 when implementing data structures using arrays, we need to be
careful with the size of array chosen:
too small: unsuitable for the application.
too big: wasteful of space.
performance: can be an issue for certain operations
because of need to move array elements around.
 An alternative is to use a dynamic list structure which is able to
grow and shrink as the application demands:
 no estimate of size is required upfront.
 Does not suffer from performance problems outlined earlier with an
array implementation.
 These structures are also known as linked lists
Lecture 25
13
Inserting/Deleting an Element(Problems
0
13
1
30
2
45
3
4
with Array)
n-1
15
Move elements from position 1 up one place
Insert 5 here
13
5
30
0
1
2
13
5
30
45
3
45
15
4
n-1
15
Move elements from position 3 down one place
Delete this
5
30
45
15
Lecture 25
14
Dynamic Data Structures
So far we have studied fixed-size data structures such as
single-subscripted arrays
Here we are introducing dynamic data structures that grow and
shrink during execution.
•A linked list is based on the concept of a selfreferential object -- an object that refers to an
object of the same class.
•Self-referential class objects can be linked
together to form useful data structures such as
lists, stacks, queues, and trees
Lecture 25
15
The Linked List Data Structure

A linked list is based on the concept of a self-referential
object -- an object that refers to an object of the same class.
A link to another
Node object.
public class Node {
private String name;
private Node next;
}
Node
Data
Nuri
Link
Reference
Omer
Null reference
Sami
Lecture 25
16
Dynamic Linked List Structures
element next
element next
element
next
header
List Nodes
 Each node consists of a data element and reference which points to
the next node in the list.
 The last node reference is initialised to a null value and this is used to
terminate the list.
Implementation Issues
 If a header reference is used to point to the 1st list node:
 insertion and deleting first element requires the header to be updated to
reflect the changes to the start of the list.
 deleting in general requires that we keep track of the node in front of
the one to be deleted so that the links can be updated.
Lecture 25
17
Solution - Using a Dummy Header Node
next
element next
element next
element
next
dummy header
List Nodes
 Using a dummy header node solves the problems outlined
earlier with a header reference.
 To solve deletion problems we need to provide a
findPrevious method which returns a reference to the
predecessor of the node we wish to delete.
 If we delete the first node then findPrevious will return the
header node whose next reference can be updated.
 Inserting a new first node only requires that the header
next reference be updated to point to the new first node.
Lecture 25
18
Singly-linked list
The singly-linked list is the most basic of all the linked data structures. A
singly-linked list is simply a sequence of dynamically allocated objects,
each of which refers to its successor in the list. Despite this obvious
simplicity, there are myriad implementation variations. The
figure below shows several of the most common singly-linked list
variants.
head
(a)
(b)
head
tail
head
(c)
sentinel
tail
(d)
Lecture 25
19
Linked List (Cont’d)
The basic singly-linked list is indicated in the above figure by (a). Each element of the
list refers to its successor and the last element contains the null reference. One variable,
labeled head, is used to keep track of the list. The basic singly-linked list is inefficient
in those cases when we wish to add elements to both ends of the list. While it is easy to
add elements at the head of the list, to add elements at the other end we need to locate
the last element. If the basic basic singly-linked list is used, the entire list needs to be
traversed in order to find its tail.
head
(a)
(b)
head
tail
The list labeled (b) shows a way in which to make adding elements to
the tail of a list more efficient. The solution uses a second variable, tail,
which refers to the last element of the list. Of course, this time efficiency
comes at the cost of the additional space used to store the variable tail.
Lecture 25
20
Linked List (Cont’d)
The singly-linked list labeled (c) illustrates two common programming tricks. There is
an extra element at the head of the list called a sentinel. This element is never used to
hold data and it is always present. The principal advantage of using a sentinel is that it
simplifies the programming of certain operations. For example, since there is always a
sentinel standing guard, we never need to modify the head variable. Of course, the
disadvantage of a sentinel such as shown is that extra space is required, and the sentinel
needs to be created when the list is initialized.
head
(c)
sentinel
The list (c) is also a circular list. Instead of using a null reference to
demarcate the end of the list, the last element of the list refers to the
sentinel. The advantage of this programming trick is that insertion at the
head of the list, insertion at the tail of the list, and insertion at an
arbitrary position of the list are all identical operations.
Lecture 25
21
Linked List (Cont’d)
Of course, it is also possible to make a circular, singly-linked list that
does not use a sentinel. The list labeled (d) shows a variation in which a
single variable is used to keep track of the list, but this time the variable,
tail, refers to the last element of the list. Since the list is circular in this
case, the first element follows the last element of the list. Therefore, it is
relatively simple to insert both at the head and at the tail of this list. This
variation minimizes the storage required, at the expense of a little extra
time for certain operations.
tail
(d)
(e) Doubly Linked List
Lecture 25
22
LinkedList Node Implementation
• click here on this link
Linked List
 If an abstract data type is to be truly abstract then the type of the
element that it is used to manage should be irrelevant.
 We will therefore store instances of the base Java Object type in our
node which is represented by a Java class as follows.
public class Node {
private Object element;
private Node next;
// Object type stored in this node
// reference to another node
// class methods go here
}
 The structure is self-referential in nature as the reference which is
part of the class is also capable of referring to a ListNode (i.e. itself).
 A node class should also provide an appropriate set of constructors
and node interface methods.
Lecture 25
23