16.4. The Stack ADTA stack is a special type of list that allows insertions and removals to be performed only to the front of the list. Therefore, it enforces last-in/first-out (LIFO) behavior on the list. Think of a stack of dishes at the salad bar. When you put a dish on the stack, it goes onto the top of the stack. When you remove a dish from the stack, it comes from the top of the stack (Fig. 16.20). Figure 16.20. A stack is a list that permits insertions and removals only at its top. |
public class Stack extends List { public Stack() { super(); // Initialize the list } public void push( Object obj ) { insertAtFront( obj ); } public Object pop() { return removeFirst(); } } // Stack class |
Because the isEmpty() method is defined in List, there is no need to override it in Stack. In effect, the push() and pop() methods merely rename the insertAtFront() and removeFirst() methods. Note that the Stack() constructor calls the superclass constructor. This is necessary so that the list can be initialized.
Do we have to make any changes to the List class in order to use it this way? Yes. We want to change the declaration of head from private to protected, so that it can be accessed in the Stack class. And we want to declare List's public access methods, such as insertAtFront() and removeFirst(), as protected. That will allow them to be used in Stack, and in any classes that extend List, but not in other classes. This is essential. Unless we do this we haven't really restricted the stack operations to push and pop, and therefore we haven't really defined a stack ADT. Remember, an ADT defines the data and operations on the data. A stack ADT must restrict access to the data to just the push and pop operations.
Java Language Rule: Protected Elements
An object's protected elements are hidden from all other objects except instances of the same class or its subclasses. |
Effective Design: Information Hiding
Use the private and protected qualifiers to hide an ADT's implementation details from other objects. Use public to define the ADT's interface. |
Exercise 16.9 | Define the peek() method for the Stack class. It should take no parameters and return an Object. It should return the Object on the top of the stack. |
Now let's test our stack class by using a stack to reverse the letters in a String. The algorithm is this: Starting at the front of the String, push each letter onto the stack until you reach the end of the String. Then pop letters off the stack and concatenate them, left to right, into another String, until the stack is empty (Fig. 16.23).
Reversing a string
public static void main( String argv[] ) { 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 o = null; String reversed = ""; while (!stack.isEmpty()) { o = stack.pop(); reversed = reversed + o.toString(); } System.out.println("Reversed String: " + reversed); } // main() |
Because our Nodes store Objects, we must convert each char into a Character, using the wrapper class. We can use the toString() method to convert from Object to String as we are popping the stack.