Brought to you by EarthWeb
ITKnowledge Logo Login Graphic Click Here!
Click Here!
ITKnowledge
Find:
 
EXPERT SEARCH ----- nav

EarthWeb Direct

EarthWeb sites: other sites

Previous Table of Contents Next


Stack

The Stack class implements a classic stack data structure, that is a last-in-first-out (LIFO) set of objects. There are three fundamental operations you can perform with a stack:

1.  Put an object on the top of the stack. This is called pushing.
2.  Take an object off the top of the stack. This is called popping.
3.  Look at the object on the top of the stack, but leave it there. This is called peeking.

Notice that all three of these operations operate only on the top of the stack. To see what’s further down in the stack, you must first remove everything that’s on top of it.


Note:  Some people claim that there are only two fundamental stack operations: pushing and popping. Peeking can be considered to be a pop followed by a push of the object back onto the stack.

Java provides methods to perform all three fundamental operations: pushing, popping, and peeking. They are

     public Object peek()
     public Object pop()
     public Object push(Object  item)

When an object is placed in a stack, it loses its type information. Therefore, when you retrieve it from the stack, you have to cast it back. For example,

     String s = (String) theStack.pop();

Java has two more utility methods that, while useful, are not part of the minimal requirements for a stack. They are

     public boolean empty()
     public int search(Object  o)

The empty() method returns true if the Stack contains no elements or false if it does not.

The search method returns an int that tells you how deep in the stack the object o is. The object on the top of the stack is at position 0; the second to the top object is at position 1, and so on. If the object is not found in the stack search() returns -1.

Objects are tested for their presence in the stack with the equals() method, not with ==. Thus, in some sense, search() is looking for an object equivalent to the requested object, not necessarily the same object. For example, consider the following code:

     Stack theStack = new Stack();
     URL u1 = new URL("http://sunsite.unc.edu/
      javafaq/javafaq.html#xtocid1902961");
     URL u2 = new URL("http://sunsite.unc.edu/
      javafaq/javafaq.html");
     theStack.push(u1);
     theStack.push("Here's a string");
     theStack.push("Here's another string");
     theStack.push(u2);

When this code has finished, the stack looks like this:

     0 (URL u2) http://sunsite.unc.edu/javafaq/javafaq.html
     1 (String) "Here's another string"
     2 (String) "Here's a string"
     3 (URL u1) http://sunsite.unc.edu/javafaq/javafaq.html#xtocid1902961

Now suppose you search for u1 like this:

     int result = theStack.search(u1);

If you print out the result, you will see that it’s 0, not 3, even though u1 is at position 3 in the stack, not position 0. The stack is searched from top to bottom for the first object for which o.equals(u1) is true. In this example that’s u2, http://sunsite.unc.edu/javafaq/javafaq.html, because the URL class’s equals() method does not consider the ref to be part of a URL.

In Java, the Stack class extends the Vector class. Therefore, you can do anything with a stack that you can do with a Vector. Most significantly this means that you can use the at methods: elementAt(), insertElementAt(), removeElementAt(), and setElementAt(). This is unfortunate because it allows the integrity of a stack to be violated. The whole point of a stack is that operations always take place only on the top of the stack. Many algorithms depend on this assertion. It is extremely bad style to violate this directive.

It is certainly true that there are situations in which it is useful and convenient to operate on elements in the middle of a list. However, if this is what you need to do, you should use a raw Vector, not a stack.

The Stack class was written by Jonathan Payne. My best guess is that he decided to implement Stack as a subclass of Vector in order to save time through code reuse. However, what he probably should have done was to have used the Vector class via encapsulation rather than inheritance. Listing 3.2 demonstrates how the Stack class could have been quickly written without allowing too much access to the nether regions of the stack.

Listing 3-2 An alternative vision for the Stack class

     /*
      * @(#)Stack.java 1.12 96/12/09
      *
      * Copyright 1996 Elliotte Rusty Harold.
      *
      * Permission to use, copy, modify, and distribute this software
      * and its documentation for all purposes and without
      * fee is hereby granted provided that this copyright notice
      * appears in all copies.
      */

     package com.macfaq.util;

     import java.util.*;

     /**
      * A stack that guarantees its own integrity.
      *
      * @version   1.0, 12/09/96
      * @author  Elliotte Rusty Harold
      */
     public class Stack {

      Vector theStack = new Vector();

      public Object push(Object o) {

       theStack.addElement(item);
       return o;

      }

      public Object pop() {

       Object  o;

       int len = theStack.size();
       o = peek();
       theStack.removeElementAt(len - 1);
       return o;

      }

      public Object peek() {

       Object  o;

       int len = theStack.size();
       if (len == 0) throw new EmptyStackException();
        return theStack.elementAt(len - 1);

      }

      public boolean empty() {

       if (theStack.size() == 0) return true;
       else return false;

      }

      public int search(Object o) {

       int i = theStack.lastIndexOf(o);

       if (i >= 0) return theStack.size() - i;
    return -1;

       }

     }

This Stack class performs all the necessary stack operations; it’s still based on the Vector class, so it can take advantage of any optimizations made there, but it does not allow other classes to violate the stack structure.


Previous Table of Contents Next
HomeAbout UsSearchSubscribeAdvertising InfoContact UsFAQs
Use of this site is subject to certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.