![]() |
|||
![]() ![]() |
![]() |
|
![]() |
StackThe 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:
Notice that all three of these operations operate only on the top of the stack. To see whats further down in the stack, you must first remove everything thats on top of it.
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 its 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 thats u2, http://sunsite.unc.edu/javafaq/javafaq.html, because the URL classs 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; its 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.
|
![]() |
|