Frames | No Frames |
1: /* Stack.java - Class that provides a Last In First Out (LIFO) 2: datatype, known more commonly as a Stack 3: Copyright (C) 1998, 1999, 2001, 2005 Free Software Foundation, Inc. 4: 5: This file is part of GNU Classpath. 6: 7: GNU Classpath is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU Classpath is distributed in the hope that it will be useful, but 13: WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15: General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU Classpath; see the file COPYING. If not, write to the 19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20: 02110-1301 USA. 21: 22: Linking this library statically or dynamically with other modules is 23: making a combined work based on this library. Thus, the terms and 24: conditions of the GNU General Public License cover the whole 25: combination. 26: 27: As a special exception, the copyright holders of this library give you 28: permission to link this library with independent modules to produce an 29: executable, regardless of the license terms of these independent 30: modules, and to copy and distribute the resulting executable under 31: terms of your choice, provided that you also meet, for each linked 32: independent module, the terms and conditions of the license of that 33: module. An independent module is a module which is not derived from 34: or based on this library. If you modify this library, you may extend 35: this exception to your version of the library, but you are not 36: obligated to do so. If you do not wish to do so, delete this 37: exception statement from your version. */ 38: 39: 40: package java.util; 41: 42: /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 43: * "The Java Language Specification", ISBN 0-201-63451-1 44: * plus online API docs for JDK 1.2 beta from http://www.javasoft.com. 45: * Status: Believed complete and correct 46: 47: /** 48: * Stack provides a Last In First Out (LIFO) data type, commonly known 49: * as a Stack. Stack itself extends Vector and provides the additional 50: * methods for stack manipulation (push, pop, peek). You can also seek for 51: * the 1-based position of an element on the stack. 52: * 53: * @author Warren Levy (warrenl@cygnus.com) 54: * @author Eric Blake (ebb9@email.byu.edu) 55: * @see List 56: * @see AbstractList 57: * @see LinkedList 58: * @since 1.0 59: * @status updated to 1.4 60: */ 61: public class Stack extends Vector 62: { 63: // We could use Vector methods internally for the following methods, 64: // but have used Vector fields directly for efficiency (i.e. this 65: // often reduces out duplicate bounds checking). 66: 67: /** 68: * Compatible with JDK 1.0+. 69: */ 70: private static final long serialVersionUID = 1224463164541339165L; 71: 72: /** 73: * This constructor creates a new Stack, initially empty 74: */ 75: public Stack() 76: { 77: } 78: 79: /** 80: * Pushes an Object onto the top of the stack. This method is effectively 81: * the same as addElement(item). 82: * 83: * @param item the Object to push onto the stack 84: * @return the Object pushed onto the stack 85: * @see Vector#addElement(Object) 86: */ 87: public Object push(Object item) 88: { 89: // When growing the Stack, use the Vector routines in case more 90: // memory is needed. 91: // Note: spec indicates that this method *always* returns obj passed in! 92: 93: addElement(item); 94: return item; 95: } 96: 97: /** 98: * Pops an item from the stack and returns it. The item popped is 99: * removed from the Stack. 100: * 101: * @return the Object popped from the stack 102: * @throws EmptyStackException if the stack is empty 103: */ 104: public synchronized Object pop() 105: { 106: if (elementCount == 0) 107: throw new EmptyStackException(); 108: 109: modCount++; 110: Object obj = elementData[--elementCount]; 111: 112: // Set topmost element to null to assist the gc in cleanup. 113: elementData[elementCount] = null; 114: return obj; 115: } 116: 117: /** 118: * Returns the top Object on the stack without removing it. 119: * 120: * @return the top Object on the stack 121: * @throws EmptyStackException if the stack is empty 122: */ 123: public synchronized Object peek() 124: { 125: if (elementCount == 0) 126: throw new EmptyStackException(); 127: 128: return elementData[elementCount - 1]; 129: } 130: 131: /** 132: * Tests if the stack is empty. 133: * 134: * @return true if the stack contains no items, false otherwise 135: */ 136: public synchronized boolean empty() 137: { 138: return elementCount == 0; 139: } 140: 141: /** 142: * Returns the position of an Object on the stack, with the top 143: * most Object being at position 1, and each Object deeper in the 144: * stack at depth + 1. 145: * 146: * @param o The object to search for 147: * @return The 1 based depth of the Object, or -1 if the Object 148: * is not on the stack 149: */ 150: public synchronized int search(Object o) 151: { 152: int i = elementCount; 153: while (--i >= 0) 154: if (equals(o, elementData[i])) 155: return elementCount - i; 156: return -1; 157: } 158: }