Stacks

A stack is a constrained version of a linked listnew nodes can be added to and removed from a stack only at the top. [Note: A stack does not have to be implemented using a linked list.] For this reason, a stack is referred to as a last-in, first-out (LIFO) data structure. The link member in the bottom (i.e., last) node of the stack is set to null to indicate the bottom of the stack.

The primary methods for manipulating a stack are push and pop. Method push adds a new node to the top of the stack. Method pop removes a node from the top of the stack and returns the data from the popped node.

Stacks have many interesting applications. For example, when a program calls a method, the called method must know how to return to its caller, so the return address of the calling method is pushed onto the program execution stack. If a series of method calls occurs, the successive return addresses are pushed onto the stack in last-in, first-out order so that each method can return to its caller. Stacks support recursive method calls in the same manner as they do conventional nonrecursive method calls.

The program execution stack also contains the memory for local variables on each invocation of a method during a program's execution. When the method returns to its caller, the memory for that method's local variables is popped off the stack, and those variables are no longer known to the program. If the local variable is a reference, the reference count for the object to which it referred is decremented by 1. If the reference count becomes zero, the object can be garbage collected.

Compilers use stacks to evaluate arithmetic expressions and generate machine-language code to process the expressions. The exercises in this chapter explore several applications of stacks, including using them to develop a complete working compiler. Also, package java.util contains class Stack (see Chapter 19) for implementing and manipulating stacks that can grow and shrink during program execution.

We take advantage of the close relationship between lists and stacks to implement a stack class by reusing a list class. We demonstrate two different forms of reusability. First, we implement the stack class by extending class List of Fig. 17.3. Then we implement an identically performing stack class through composition by including a reference to a List object as a private instance variable of a stack class. The list, stack and queue data structures in this chapter are implemented to store Object references to encourage further reusability. Thus, any object type can be stored in a list, stack or queue.

Stack Class That Inherits from List

The application of Fig. 17.10 and Fig. 17.11 creates a stack class by extending class List of Fig. 17.3. We want the stack to have methods push, pop, isEmpty and print. Essentially, these are the methods insertAtFront, removeFromFront, isEmpty and print of class List. Of course, class List contains other methods (such as insertAtBack and removeFromBack) that we would rather not make accessible through the public interface to the stack class. It is important to remember that all methods in the public interface of class List class also are public methods of the subclass StackInheritance (Fig. 17.10). When we implement the stack's methods, we have each StackInheritance method call the appropriate List methodmethod push calls insertAtFront and method pop calls removeFromFront. Clients of class StackInheritance can call methods isEmpty and print because they are inherited from List. Class StackInheritance is declared as part of package com.deitel.jhtp6.ch17 for reuse purposes. Note that StackInheritance does not import List, because both classes are in the same package.

Figure 17.10. StackInheritance extends class List.

 1 // Fig. 17.10: StackInheritance.java
 2 // Derived from class List.
 3 package com.deitel.jhtp6.ch17;
 4
 5 public class StackInheritance extends List
 6 {
 7 // no-argument constructor
 8 public StackInheritance()
 9 {
10 super ( "stack" );
11 } // end StackInheritance no-argument constructor
12
13 // add object to stack
14 public void push( Object object )
15 {
16 insertAtFront( object );
17 } // end method push
18
19 // remove object from stack
20 public Object pop() throws EmptyListException
21 {
22 return removeFromFront();
23 } // end method pop
24 } // end class StackInheritance

Figure 17.11. Stack manipulation program.

(This item is displayed on pages 833 - 834 in the print version)

 1 // Fig. 17.11: StackInheritanceTest.java
 2 // Class StackInheritanceTest.
 3 import com.deitel.jhtp6.ch17.StackInheritance;
 4 import com.deitel.jhtp6.ch17.EmptyListException;
 5
 6 public class StackInheritanceTest
 7 {
 8 public static void main( String args[] )
 9 {
10 StackInheritance stack = new StackInheritance();
11
12 // use push method
13 stack.push( -1 ); 
14 stack.print(); 
15 stack.push( 0 ); 
16 stack.print(); 
17 stack.push( 1 ); 
18 stack.print(); 
19 stack.push( 5 ); 
20 stack.print(); 
21
22 // remove items from stack
23 try
24 {
25 Object removedObject = null;
26
27 while ( true )
28 {
29 removedObject = stack.pop(); // use pop method
30 System.out.printf( "%s popped
", removedObject );
31 stack.print();
32 } // end while
33 } // end try
34 catch ( EmptyListException emptyListException )
35 {
36 emptyListException.printStackTrace();
37 } // end catch
38 } // end main
39 } // end class StackInheritanceTest

 

The stack is: -1

The stack is: 0 -1

The stack is: 1 0 -1

The stack is: 5 1 0 -1

5 popped
The stack is: 1 0 -1

1 popped
The stack is: 0 -1

0 popped
The stack is: -1

-1 popped
Empty stack
com.deitel.jhtp6.ch17.EmptyListException: stack is empty
 at com.deitel.jhtp6.ch17.List.removeFromFront(List.java:81)
 at com.deitel.jhtp6.ch17.StackInheritance.pop(StackInheritance.java:22)
 at StackInheritanceTest.main(StackInheritanceTest.java:29)

 

Class StackInheritanceTest's method main (Fig. 17.11) creates an object of class StackInheritance called stack (line 10). The program pushes integers onto the stack (lines 13, 15, 17 and 19). Once again, note that autoboxing is used here to insert Integer objects into the data structure. Lines 2732 pop the objects from the stack in an infinite while loop. If method pop is invoked on an empty stack, the method throws an EmptyListException. In this case, the program displays the exception's stack trace, which shows the methods on the program execution stack at the time the exception occurred. Note that the program uses method print (inherited from List) to output the contents of the stack.

Stack Class That Contains a Reference to a List

You can also implement a class by reusing a list class through composition. Figure 17.12 uses a private List (line 7) in class StackComposition's declaration. Composition enables us to hide the List methods that should not be in our stack's public interface. We provide public interface methods that use only the required List methods. Implementing each stack method as a call to a List method is called delegationthe stack method invoked delegates the call to the appropriate List method. In particular, StackComposition delegates calls to List methods insertAtFront, removeFromFront, isEmpty and print. In this example, we do not show class StackCompositionTest, because the only difference is that we change the type of the stack from StackInheritance to StackComposition (lines 3 and 10 of Fig. 17.11). The output is identical using either version of the stack.

Figure 17.12. StackComposition uses a composed List object.

 1 // Fig. 17.12: StackComposition.java
 2 // Class StackComposition definition with composed List object.
 3 package com.deitel.jhtp6.ch17;
 4
 5 public class StackComposition
 6 {
 7 private List stackList;
 8
 9 // no-argument constructor
10 public StackComposition()
11 {
12 stackList = new List( "stack" );
13 } // end StackComposition no-argument constructor
14
15 // add object to stack
16 public void push( Object object )
17 {
18 stackList.insertAtFront( object );
19 } // end method push
20
21 // remove object from stack
22 public Object pop() throws EmptyListException
23 {
24 return stackList.removeFromFront();
25 } // end method pop
26
27 // determine if stack is empty
28 public boolean isEmpty()
29 {
30 return stackList.isEmpty();
31 } // end method isEmpty
32
33 // output stack contents
34 public void print()
35 {
36 stackList.print();
37 } // end method print
38 } // end class StackComposition