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

Introduction to Computers, the Internet and the World Wide Web

Introduction to Java Applications

Introduction to Classes and Objects

Control Statements: Part I

Control Statements: Part 2

Methods: A Deeper Look

Arrays

Classes and Objects: A Deeper Look

Object-Oriented Programming: Inheritance

Object-Oriented Programming: Polymorphism

GUI Components: Part 1

Graphics and Java 2D™

Exception Handling

Files and Streams

Recursion

Searching and Sorting

Data Structures

Generics

Collections

Introduction to Java Applets

Multimedia: Applets and Applications

GUI Components: Part 2

Multithreading

Networking

Accessing Databases with JDBC

Servlets

JavaServer Pages (JSP)

Formatted Output

Strings, Characters and Regular Expressions

Appendix A. Operator Precedence Chart

Appendix B. ASCII Character Set

Appendix C. Keywords and Reserved Words

Appendix D. Primitive Types

Appendix E. (On CD) Number Systems

Appendix F. (On CD) Unicode®

Appendix G. Using the Java API Documentation

Appendix H. (On CD) Creating Documentation with javadoc

Appendix I. (On CD) Bit Manipulation

Appendix J. (On CD) ATM Case Study Code

Appendix K. (On CD) Labeled break and continue Statements

Appendix L. (On CD) UML 2: Additional Diagram Types

Appendix M. (On CD) Design Patterns

Appendix N. Using the Debugger

Inside Back Cover



Java(c) How to Program
Java How to Program (6th Edition) (How to Program (Deitel))
ISBN: 0131483986
EAN: 2147483647
Year: 2003
Pages: 615

Similar book on Amazon

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