Stack
Stack is a subclass of Vector that implements a standard last-in, first-out stack. Stack only defines the default constructor, which creates an empty stack. Stack includes all the methods defined by Vector, and adds several of its own.
To put an object on the top of the stack, call push( ). To remove and return the top element, call pop( ). An EmptyStackException is thrown if you call pop( ) when the invoking stack is empty. You can use peek( ) to return, but not remove, the top object. The empty( ) method returns true if nothing is on the stack. The search( ) method determines whether an object exists on the stack, and returns the number of pops that are required to bring it to the top of the stack. Here is an example that creates a stack, pushes several Integer objects onto it, and then pops them off again:
The Methods Defined by Stack
boolean empty( ): Returns true if the stack is empty, and returns false if the stack contains elements.
Object peek( ): Returns the element on the top of the stack, but does not remove it.
Object pop( ): Returns the element on the top of the stack, removing it in the process.
Object push(Object element): Pushes element onto the stack. element is also returned.
int search(Object element): Searches for element in the stack. If found, its offset from the top of the stack is returned. Otherwise, –1 is returned.
// Demonstrate the Stack class.
import java.util.*;
class StackDemo {
static void showpush(Stack st, int a) {
st.push(new Integer(a));
System.out.println("push(" + a + ")");
System.out.println("stack: " + st);
}
static void showpop(Stack st) {
System.out.print("pop -> ");
Integer a = (Integer) st.pop();
System.out.println(a);
System.out.println("stack: " + st);
}
public static void main(String args[]) {
Stack st = new Stack();
System.out.println("stack: " + st);
showpush(st, 42);
showpush(st, 66);
showpush(st, 99);
showpop(st);
showpop(st);
showpop(st);
try {
showpop(st);
} catch (EmptyStackException e) {
System.out.println("empty stack");
}
}
}
The following is the output produced by the program; notice how the exception handler for EmptyStackException is caught so that you can gracefully handle a stack underflow:
stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack
Dictionary
Dictionary is an abstract class that represents a key/value storage repository and operates much like Map. Given a key and value, you can store the value in a Dictionary object. Once the value is stored, you can retrieve it by using its key. Thus, like a map, a dictionary can be thought of as a list of key/value pairs. Although not actually deprecated by Java 2, Dictionary is classified as obsolete, because it is superceded by Map. However, Dictionary is still in use and thus is fully discussed here.
To add a key and a value, use the put( ) method. Use get( ) to retrieve the value of a given key. The keys and values can each be returned as an Enumeration by the keys( ) and elements( ) methods, respectively. The size( ) method returns the number of key/ value pairs stored in a dictionary, and isEmpty( ) returns true when the dictionary is empty. You can use the remove( ) method to delete a key/value pair.
The Abstract Methods Defined by Dictionary
Enumeration elements( ): Returns an enumeration of the values contained in the dictionary.
Object get(Object key): Returns the object that contains the value associated with key. If key is not in the dictionary, a null object is returned.
boolean isEmpty( ): Returns true if the dictionary is empty, and returns false if it contains at least one key.
Enumeration keys( ): Returns an enumeration of the keys contained in the dictionary.
Object put(Object key, Object value): Inserts a key and its value into the dictionary. Returns null if key is not already in the dictionary; returns the previous value associated with key if key is already in the dictionary.
Object remove(Object key): Removes key and its value. Returns the value associated with key. If key is not in the dictionary, a null is returned.
int size( ): Returns the number of entries in the dictionary.
The Dictionary class is obsolete. You should implement the Map interface to obtain key/value storage functionality.
Hashtable
Hashtable was part of the original java.util and is a concrete implementation of a Dictionary. However, Java 2 reengineered Hashtable so that it also implements the Map interface. Thus, Hashtable is now integrated into the collections framework. It is similar to HashMap, but is synchronized.
Like HashMap, Hashtable stores key/value pairs in a hash table. When using a Hashtable, you specify an object that is used as a key, and the value that you want linked to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.
A hash table can only store objects that override the hashCode( ) and equals( ) methods that are defined by Object. The hashCode( ) method must compute and return the hash code for the object. Of course, equals( ) compares two objects. Fortunately, many of Java’s built-in classes already implement the hashCode( ) method. For example, the most common type of Hashtable uses a String object as the key. String implements both hashCode( ) and equals( ).
The Hashtable constructors are shown here:
Hashtable( )
Hashtable(int size)
Hashtable(int size, float fillRatio)
Hashtable(Map m)
The first version is the default constructor. The second version creates a hash table that has an initial size specified by size. The third version creates a hash table that has an initial size specified by size and a fill ratio specified by fillRatio. This ratio must be between 0.0 and 1.0, and it determines how full the hash table can be before it is resized upward. Specifically, when the number of elements is greater than the capacity of the hash table multiplied by its fill ratio, the hash table is expanded. If you do not specify a fill ratio, then 0.75 is used. Finally, the fourth version creates a hash table that is initialized with the elements in m. The capacity of the hash table is set to twice the number of elements in m. The default load factor of 0.75 is used. The fourth constructor was added by Java 2.
The Legacy Methods Defined by Hashtable
void clear( ): Resets and empties the hash table.
Object clone( ): Returns a duplicate of the invoking object.
boolean contains(Object value): Returns true if some value equal to value exists within the hash table. Returns false if the value isn’t found.
boolean containsKey(Object key): Returns true if some key equal to key exists within the hash table. Returns false if the key isn’t found.
boolean containsValue(Object value): Returns true if some value equal to value exists within the hash table. Returns false if the value isn’t found. (A non-Map method added by Java 2, for consistency.)
Enumeration elements( ): Returns an enumeration of the values contained in the hash table.
Object get(Object key): Returns the object that contains the value associated with key. If key is not in the hash table, a null object is returned.
boolean isEmpty( ): Returns true if the hash table is empty; returns false if it contains at least one key.
Enumeration keys( ): Returns an enumeration of the keys contained in the hash table.
Object put(Object key, Object value): Inserts a key and a value into the hash table. Returns null if key isn’t already in the hash table; returns the previous value associated with key if key is already in the hash table.
void rehash( ): Increases the size of the hash table and rehashes all of its keys.
Object remove(Object key): Removes key and its value. Returns the value associated with key. If key is not in the hash table, a null object is returned.
int size( ): Returns the number of entries in the hash table.
String toString( ): Returns the string equivalent of a hash table.
The following example reworks the bank account program, shown earlier, so that it uses a Hashtable to store the names of bank depositors and their current balances:
// Demonstrate a Hashtable
import java.util.*;
class HTDemo {
public static void main(String args[]) {
Hashtable balance = new Hashtable();
Enumeration names;
String str;
double bal;
balance.put("John Doe", new Double(3434.34));
balance.put("Tom Smith", new Double(123.22));
balance.put("Jane Baker", new Double(1378.00));
balance.put("Todd Hall", new Double(99.22));
balance.put("Ralph Smith", new Double(-19.08));
// Show all balances in hash table.
names = balance.keys();
while(names.hasMoreElements()) {
str = (String) names.nextElement();
System.out.println(str + ": " +
balance.get(str));
}
System.out.println();
// Deposit 1,000 into John Doe's account
bal = ((Double)balance.get("John Doe")).doubleValue();
balance.put("John Doe", new Double(bal+1000));
System.out.println("John Doe's new balance: " +
balance.get("John Doe"));
}
}
The output from this program is shown here:
Todd Hall: 99.22
Ralph Smith: -19.08
John Doe: 3434.34
Jane Baker: 1378.0
Tom Smith: 123.22
John Doe’s new balance: 4434.34
One important point: like the map classes, Hashtable does not directly support iterators. Thus, the preceding program uses an enumeration to display the contents of balance. However, you can obtain set-views of the hash table, which permits the use of iterators. To do so, you simply use one of the collection-view methods defined by Map, such as entrySet( ) or keySet( ). For example, you can obtain a set-view of the keys and iterate through them. Here is a reworked version of the program that shows this technique:
// Use iterators with a Hashtable.
import java.util.*;
class HTDemo2 {
public static void main(String args[]) {
Hashtable balance = new Hashtable();
String str;
double bal;
balance.put("John Doe", new Double(3434.34));
balance.put("Tom Smith", new Double(123.22));
balance.put("Jane Baker", new Double(1378.00));
balance.put("Todd Hall", new Double(99.22));
balance.put("Ralph Smith", new Double(-19.08));
// show all balances in hashtable
Set set = balance.keySet(); // get set-view of keys
// get iterator
Iterator itr = set.iterator();
while(itr.hasNext()) {
str = (String) itr.next();
System.out.println(str + ": " +
balance.get(str));
}
System.out.println();
// Deposit 1,000 into John Doe's account
bal = ((Double)balance.get("John Doe")).doubleValue();
balance.put("John Doe", new Double(bal+1000));
System.out.println("John Doe's new balance: " +
balance.get("John Doe"));
}
}
No comments:
Post a Comment