001 /* Stack.java - Class that provides a Last In First Out (LIFO) 002 datatype, known more commonly as a Stack 003 Copyright (C) 1998, 1999, 2001, 2004, 2005 004 Free Software Foundation, Inc. 005 006 This file is part of GNU Classpath. 007 008 GNU Classpath is free software; you can redistribute it and/or modify 009 it under the terms of the GNU General Public License as published by 010 the Free Software Foundation; either version 2, or (at your option) 011 any later version. 012 013 GNU Classpath is distributed in the hope that it will be useful, but 014 WITHOUT ANY WARRANTY; without even the implied warranty of 015 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 016 General Public License for more details. 017 018 You should have received a copy of the GNU General Public License 019 along with GNU Classpath; see the file COPYING. If not, write to the 020 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021 02110-1301 USA. 022 023 Linking this library statically or dynamically with other modules is 024 making a combined work based on this library. Thus, the terms and 025 conditions of the GNU General Public License cover the whole 026 combination. 027 028 As a special exception, the copyright holders of this library give you 029 permission to link this library with independent modules to produce an 030 executable, regardless of the license terms of these independent 031 modules, and to copy and distribute the resulting executable under 032 terms of your choice, provided that you also meet, for each linked 033 independent module, the terms and conditions of the license of that 034 module. An independent module is a module which is not derived from 035 or based on this library. If you modify this library, you may extend 036 this exception to your version of the library, but you are not 037 obligated to do so. If you do not wish to do so, delete this 038 exception statement from your version. */ 039 040 041 package java.util; 042 043 /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 044 * "The Java Language Specification", ISBN 0-201-63451-1 045 * plus online API docs for JDK 1.2 beta from http://www.javasoft.com. 046 * Status: Believed complete and correct 047 048 /** 049 * Stack provides a Last In First Out (LIFO) data type, commonly known 050 * as a Stack. Stack itself extends Vector and provides the additional 051 * methods for stack manipulation (push, pop, peek). You can also seek for 052 * the 1-based position of an element on the stack. 053 * 054 * @author Warren Levy (warrenl@cygnus.com) 055 * @author Eric Blake (ebb9@email.byu.edu) 056 * @see List 057 * @see AbstractList 058 * @see LinkedList 059 * @since 1.0 060 * @status updated to 1.4 061 */ 062 public class Stack<T> extends Vector<T> 063 { 064 // We could use Vector methods internally for the following methods, 065 // but have used Vector fields directly for efficiency (i.e. this 066 // often reduces out duplicate bounds checking). 067 068 /** 069 * Compatible with JDK 1.0+. 070 */ 071 private static final long serialVersionUID = 1224463164541339165L; 072 073 /** 074 * This constructor creates a new Stack, initially empty 075 */ 076 public Stack() 077 { 078 } 079 080 /** 081 * Pushes an Object onto the top of the stack. This method is effectively 082 * the same as addElement(item). 083 * 084 * @param item the Object to push onto the stack 085 * @return the Object pushed onto the stack 086 * @see Vector#addElement(Object) 087 */ 088 public T push(T item) 089 { 090 // When growing the Stack, use the Vector routines in case more 091 // memory is needed. 092 // Note: spec indicates that this method *always* returns obj passed in! 093 094 addElement(item); 095 return item; 096 } 097 098 /** 099 * Pops an item from the stack and returns it. The item popped is 100 * removed from the Stack. 101 * 102 * @return the Object popped from the stack 103 * @throws EmptyStackException if the stack is empty 104 */ 105 public synchronized T pop() 106 { 107 if (elementCount == 0) 108 throw new EmptyStackException(); 109 110 modCount++; 111 T obj = elementData[--elementCount]; 112 113 // Set topmost element to null to assist the gc in cleanup. 114 elementData[elementCount] = null; 115 return obj; 116 } 117 118 /** 119 * Returns the top Object on the stack without removing it. 120 * 121 * @return the top Object on the stack 122 * @throws EmptyStackException if the stack is empty 123 */ 124 public synchronized T peek() 125 { 126 if (elementCount == 0) 127 throw new EmptyStackException(); 128 129 return elementData[elementCount - 1]; 130 } 131 132 /** 133 * Tests if the stack is empty. 134 * 135 * @return true if the stack contains no items, false otherwise 136 */ 137 public synchronized boolean empty() 138 { 139 return elementCount == 0; 140 } 141 142 /** 143 * Returns the position of an Object on the stack, with the top 144 * most Object being at position 1, and each Object deeper in the 145 * stack at depth + 1. 146 * 147 * @param o The object to search for 148 * @return The 1 based depth of the Object, or -1 if the Object 149 * is not on the stack 150 */ 151 public synchronized int search(Object o) 152 { 153 int i = elementCount; 154 while (--i >= 0) 155 if (equals(o, elementData[i])) 156 return elementCount - i; 157 return -1; 158 } 159 }