Section 16.4. The Stack ADT


[Page 785 (continued)]

16.4. The Stack ADT

A 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.
(This item is displayed on page 786 in the print version)


The stack operations are conventionally called push, for insert, and pop, for remove. Thus, the stack ADT stores a list of data and supports the following operations:

  • Push: Inserts an object onto the top of the stack.

  • Pop: Removes the top object from the stack.

  • Empty: Returns TRue if the stack is empty.

  • Peek: Retrieves the top object without removing it.


[Page 786]

Stacks are useful for a number of important computing tasks. For example, during program execution, method call and return happens in a LIFO fashion. The last method called is the first method exited. Therefore, a stack structure known as the runtime stack is used to manage method calls during program execution. When a method is called, an activation block is created, which includes the method's parameters, local variables, and return address. The activation block is pushed onto the stack. When the method call returns, the return address is retrieved from the activation block and the whole block is popped off the stack. The Exception.printStackTrace() method uses the runtime stack to print a trace of the method calls that led to an exception.

Stack applications


16.4.1. The Stack Class

Given our general definition of List and Node, it is quite easy to define the stack ADT as a subclass of List (Fig. 16.21). As a subclass of List, a Stack will inherit all of the public and protected methods defined in List. Therefore, we can simply use the insertAtFront() and removeFirst() methods for the push and pop operations, respectively (Fig. 16.22).

Figure 16.21. As a subclass of List, a Stack inherits all of its public (+) and protected (#) elements. Therefore, push() can be defined in terms of insertAtFront(), and pop() can be defined in terms of removeFirst().



[Page 787]

Figure 16.22. The Stack ADT.

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.


Self-Study Exercise

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.

16.4.2. Testing the Stack Class

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


Figure 16.23. A method to test the Stack ADT, which is used here to reverse a String of letters.
(This item is displayed on page 788 in the print version)

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.




Java, Java, Java(c) Object-Orienting Problem Solving
Java, Java, Java, Object-Oriented Problem Solving (3rd Edition)
ISBN: 0131474340
EAN: 2147483647
Year: 2005
Pages: 275

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net