Java Tutorial/Collections/Stack
Версия от 17:44, 31 мая 2010; (обсуждение)
Содержание
- 1 Adding Elements: To add an element to a stack, call the push() method
- 2 A faster, smaller stack implementation.
- 3 An implementation of the java.util.Stack based on an ArrayList instead of a Vector, so it is not synchronized to protect against multi-threaded access.
- 4 A simple integer based stack.
- 5 A stack of simple integers
- 6 A very simple unsynchronized stack. This one is faster than the java.util-Version.
- 7 Character Stack
- 8 Checking the Top: To get the element without removing: using the peek() method
- 9 Demonstrate the generic Stack class.
- 10 extends ArrayList to create Stack
- 11 Growable int stack with type specific access methods
- 12 Growable Object stack with type specific access methods
- 13 Growable String stack with type specific access methods.
- 14 If the size of the stack is zero, true is returned; otherwise, false is returned
- 15 Removing Elements: To remove an element from the stack, the pop() method
- 16 Stack Basics: last-in, first-out behavior
- 17 Stack for boolean values
- 18 To find out if an element is on the stack: the search() method
Adding Elements: To add an element to a stack, call the push() method
public Object push(Object element)
[A, B, C]
A faster, smaller stack implementation.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.EmptyStackException;
/**
* A faster, smaller stack implementation. ArrayListStack is final and unsynchronized (the JDK"s
* methods are synchronized). In addition you can set the initial capacity if you want via the
* ArrayListStack(int) constructor.
*
* @author Jonathan Locke
* @param <T>
*/
public final class ArrayListStack<T> extends ArrayList<T>
{
private static final long serialVersionUID = 1L;
/**
* Construct.
*
* @param initialCapacity
* Initial capacity of the stack
*/
public ArrayListStack(final int initialCapacity)
{
super(initialCapacity);
}
/**
* Construct.
*/
public ArrayListStack()
{
this(10);
}
/**
* Construct.
*
* @param collection
* The collection to add
*/
public ArrayListStack(final Collection<T> collection)
{
super(collection);
}
/**
* Pushes an item onto the top of this stack.
*
* @param item
* the item to be pushed onto this stack.
*/
public final void push(final T item)
{
add(item);
}
/**
* Removes the object at the top of this stack and returns that object.
*
* @return The object at the top of this stack
* @exception EmptyStackException
* If this stack is empty.
*/
public final T pop()
{
final T top = peek();
remove(size() - 1);
return top;
}
/**
* Looks at the object at the top of this stack without removing it.
*
* @return The object at the top of this stack
* @exception EmptyStackException
* If this stack is empty.
*/
public final T peek()
{
int size = size();
if (size == 0)
{
throw new EmptyStackException();
}
return get(size - 1);
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if and only if this stack contains no items; <code>false</code>
* otherwise.
*/
public final boolean empty()
{
return size() == 0;
}
/**
* Returns the 1-based position where an object is on this stack. If the object <tt>o</tt>
* occurs as an item in this stack, this method returns the distance from the top of the stack
* of the occurrence nearest the top of the stack; the topmost item on the stack is considered
* to be at distance <tt>1</tt>. The <tt>equals</tt> method is used to compare <tt>o</tt>
* to the items in this stack.
*
* @param o
* the desired object.
* @return the 1-based position from the top of the stack where the object is located; the
* return value <code>-1</code> indicates that the object is not on the stack.
*/
public final int search(final T o)
{
int i = lastIndexOf(o);
if (i >= 0)
{
return size() - i;
}
return -1;
}
}
An implementation of the java.util.Stack based on an ArrayList instead of a Vector, so it is not synchronized to protect against multi-threaded access.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.EmptyStackException;
import java.util.NoSuchElementException;
/**
* An implementation of the {@link java.util.Stack} API that is based on an
* <code>ArrayList</code> instead of a <code>Vector</code>, so it is not
* synchronized to protect against multi-threaded access. The implementation
* is therefore operates faster in environments where you do not need to
* worry about multiple thread contention.
*
* The removal order of an <code>ArrayStack</code> is based on insertion
* order: The most recently added element is removed first. The iteration
* order is <i>not</i> the same as the removal order. The iterator returns
* elements from the bottom up, whereas the {@link #remove()} method removes
* them from the top down.
*
* Unlike <code>Stack</code>, <code>ArrayStack</code> accepts null entries.
*
* <strong>Note:</strong> this class should be bytecode-identical to the
* version in commons collections. This is required to allow backwards
* compability with both previous versions of BeanUtils and also allow
* coexistance with both collections 2.1 and 3.0.
*
* @see java.util.Stack
* @since Commons Collections 1.0
* @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
*
* @author Craig R. McClanahan
* @author Paul Jack
* @author Stephen Colebourne
*/
public class ArrayStack extends ArrayList implements Buffer {
/** Ensure serialization compatibility */
private static final long serialVersionUID = 2130079159931574599L;
/**
* Constructs a new empty <code>ArrayStack</code>. The initial size
* is controlled by <code>ArrayList</code> and is currently 10.
*/
public ArrayStack() {
super();
}
/**
* Constructs a new empty <code>ArrayStack</code> with an initial size.
*
* @param initialSize the initial size to use
* @throws IllegalArgumentException if the specified initial size
* is negative
*/
public ArrayStack(int initialSize) {
super(initialSize);
}
/**
* Return <code>true</code> if this stack is currently empty.
*
* This method exists for compatibility with <code>java.util.Stack</code>.
* New users of this class should use <code>isEmpty</code> instead.
*
* @return true if the stack is currently empty
*/
public boolean empty() {
return isEmpty();
}
/**
* Returns the top item off of this stack without removing it.
*
* @return the top item on the stack
* @throws EmptyStackException if the stack is empty
*/
public Object peek() throws EmptyStackException {
int n = size();
if (n <= 0) {
throw new EmptyStackException();
} else {
return get(n - 1);
}
}
/**
* Returns the n"th item down (zero-relative) from the top of this
* stack without removing it.
*
* @param n the number of items down to go
* @return the n"th item on the stack, zero relative
* @throws EmptyStackException if there are not enough items on the
* stack to satisfy this request
*/
public Object peek(int n) throws EmptyStackException {
int m = (size() - n) - 1;
if (m < 0) {
throw new EmptyStackException();
} else {
return get(m);
}
}
/**
* Pops the top item off of this stack and return it.
*
* @return the top item on the stack
* @throws EmptyStackException if the stack is empty
*/
public Object pop() throws EmptyStackException {
int n = size();
if (n <= 0) {
throw new EmptyStackException();
} else {
return remove(n - 1);
}
}
/**
* Pushes a new item onto the top of this stack. The pushed item is also
* returned. This is equivalent to calling <code>add</code>.
*
* @param item the item to be added
* @return the item just pushed
*/
public Object push(Object item) {
add(item);
return item;
}
/**
* Returns the one-based position of the distance from the top that the
* specified object exists on this stack, where the top-most element is
* considered to be at distance <code>1</code>. If the object is not
* present on the stack, return <code>-1</code> instead. The
* <code>equals()</code> method is used to compare to the items
* in this stack.
*
* @param object the object to be searched for
* @return the 1-based depth into the stack of the object, or -1 if not found
*/
public int search(Object object) {
int i = size() - 1; // Current index
int n = 1; // Current distance
while (i >= 0) {
Object current = get(i);
if ((object == null && current == null) ||
(object != null && object.equals(current))) {
return n;
}
i--;
n++;
}
return -1;
}
/**
* Returns the element on the top of the stack.
*
* @return the element on the top of the stack
* @throws BufferUnderflowException if the stack is empty
*/
public Object get() {
int size = size();
if (size == 0) {
throw new BufferUnderflowException();
}
return get(size - 1);
}
/**
* Removes the element on the top of the stack.
*
* @return the removed element
* @throws BufferUnderflowException if the stack is empty
*/
public Object remove() {
int size = size();
if (size == 0) {
throw new BufferUnderflowException();
}
return remove(size - 1);
}
}
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* Defines a collection that allows objects to be removed in some well-defined order.
*
* The removal order can be based on insertion order (eg, a FIFO queue or a
* LIFO stack), on access order (eg, an LRU cache), on some arbitrary comparator
* (eg, a priority queue) or on any other well-defined ordering.
*
* Note that the removal order is not necessarily the same as the iteration
* order. A <code>Buffer</code> implementation may have equivalent removal
* and iteration orders, but this is not required.
*
* This interface does not specify any behavior for
* {@link Object#equals(Object)} and {@link Object#hashCode} methods. It
* is therefore possible for a <code>Buffer</code> implementation to also
* also implement {@link java.util.List}, {@link java.util.Set} or
* {@link Bag}.
*
* <strong>Note:</strong> this class should be bytecode-identical to the
* version in commons collections. This is required to allow backwards
* compability with both previous versions of BeanUtils and also allow
* coexistance with both collections 2.1 and 3.0.
*
* @since Commons Collections 2.1
* @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
*
* @author Avalon
* @author Berin Loritsch
* @author Paul Jack
* @author Stephen Colebourne
*/
interface Buffer extends Collection {
/**
* Gets and removes the next object from the buffer.
*
* @return the next object in the buffer, which is also removed
* @throws BufferUnderflowException if the buffer is already empty
*/
Object remove();
/**
* Gets the next object from the buffer without removing it.
*
* @return the next object in the buffer, which is not removed
* @throws BufferUnderflowException if the buffer is empty
*/
Object get();
}
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* The BufferUnderflowException is used when the buffer is already empty.
*
* NOTE: From version 3.0, this exception extends NoSuchElementException.
*
* @since Commons Collections 2.1
* @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
*
* @author Avalon
* @author Berin Loritsch
* @author Jeff Turner
* @author Paul Jack
* @author Stephen Colebourne
*/
class BufferUnderflowException extends NoSuchElementException {
/** The root cause throwable */
private final Throwable throwable;
/**
* Constructs a new <code>BufferUnderflowException</code>.
*/
public BufferUnderflowException() {
super();
throwable = null;
}
/**
* Construct a new <code>BufferUnderflowException</code>.
*
* @param message the detail message for this exception
*/
public BufferUnderflowException(String message) {
this(message, null);
}
/**
* Construct a new <code>BufferUnderflowException</code>.
*
* @param message the detail message for this exception
* @param exception the root cause of the exception
*/
public BufferUnderflowException(String message, Throwable exception) {
super(message);
throwable = exception;
}
/**
* Gets the root cause of the exception.
*
* @return the root cause
*/
public final Throwable getCause() {
return throwable;
}
}
A simple integer based stack.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* A simple integer based stack.
*
* moved to org.apache.xerces.util by neilg to support the
* XPathMatcher.
* @author Andy Clark, IBM
*
* @version $Id: IntStack.java 447241 2006-09-18 05:12:57Z mrglavas $
*/
public final class IntStack {
//
// Data
//
/** Stack depth. */
private int fDepth;
/** Stack data. */
private int[] fData;
//
// Public methods
//
/** Returns the size of the stack. */
public int size() {
return fDepth;
}
/** Pushes a value onto the stack. */
public void push(int value) {
ensureCapacity(fDepth + 1);
fData[fDepth++] = value;
}
/** Peeks at the top of the stack. */
public int peek() {
return fData[fDepth - 1];
}
/** Returns the element at the specified depth in the stack. */
public int elementAt(int depth) {
return fData[depth];
}
/** Pops a value off of the stack. */
public int pop() {
return fData[--fDepth];
}
/** Clears the stack. */
public void clear() {
fDepth = 0;
}
// debugging
/** Prints the stack. */
public void print() {
System.out.print("(");
System.out.print(fDepth);
System.out.print(") {");
for (int i = 0; i < fDepth; i++) {
if (i == 3) {
System.out.print(" ...");
break;
}
System.out.print(" ");
System.out.print(fData[i]);
if (i < fDepth - 1) {
System.out.print(",");
}
}
System.out.print(" }");
System.out.println();
}
//
// Private methods
//
/** Ensures capacity. */
private void ensureCapacity(int size) {
if (fData == null) {
fData = new int[32];
}
else if (fData.length <= size) {
int[] newdata = new int[fData.length * 2];
System.arraycopy(fData, 0, newdata, 0, fData.length);
fData = newdata;
}
}
} // class IntStack
A stack of simple integers
import java.util.EmptyStackException;
/*
* $Id: IntVector.java 468655 2006-10-28 07:12:06Z minchau $
*/
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* $Id: IntStack.java 468655 2006-10-28 07:12:06Z minchau $
*/
/**
* Implement a stack of simple integers.
*
* %OPT%
* This is currently based on IntVector, which permits fast acess but pays a
* heavy recopying penalty if/when its size is increased. If we expect deep
* stacks, we should consider a version based on ChunkedIntVector.
* @xsl.usage internal
*/
public class IntStack extends IntVector
{
/**
* Default constructor. Note that the default
* block size is very small, for small lists.
*/
public IntStack()
{
super();
}
/**
* Construct a IntVector, using the given block size.
*
* @param blocksize Size of block to allocate
*/
public IntStack(int blocksize)
{
super(blocksize);
}
/**
* Copy constructor for IntStack
*
* @param v IntStack to copy
*/
public IntStack (IntStack v)
{
super(v);
}
/**
* Pushes an item onto the top of this stack.
*
* @param i the int to be pushed onto this stack.
* @return the <code>item</code> argument.
*/
public int push(int i)
{
if ((m_firstFree + 1) >= m_mapSize)
{
m_mapSize += m_blocksize;
int newMap[] = new int[m_mapSize];
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
m_map = newMap;
}
m_map[m_firstFree] = i;
m_firstFree++;
return i;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack.
*/
public final int pop()
{
return m_map[--m_firstFree];
}
/**
* Quickly pops a number of items from the stack.
*/
public final void quickPop(int n)
{
m_firstFree -= n;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack.
* @throws EmptyStackException if this stack is empty.
*/
public final int peek()
{
try {
return m_map[m_firstFree - 1];
}
catch (ArrayIndexOutOfBoundsException e)
{
throw new EmptyStackException();
}
}
/**
* Looks at the object at the position the stack counting down n items.
*
* @param n The number of items down, indexed from zero.
* @return the object at n items down.
* @throws EmptyStackException if this stack is empty.
*/
public int peek(int n)
{
try {
return m_map[m_firstFree-(1+n)];
}
catch (ArrayIndexOutOfBoundsException e)
{
throw new EmptyStackException();
}
}
/**
* Sets an object at a the top of the statck
*
*
* @param val object to set at the top
* @throws EmptyStackException if this stack is empty.
*/
public void setTop(int val)
{
try {
m_map[m_firstFree - 1] = val;
}
catch (ArrayIndexOutOfBoundsException e)
{
throw new EmptyStackException();
}
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if this stack is empty;
* <code>false</code> otherwise.
* @since JDK1.0
*/
public boolean empty()
{
return m_firstFree == 0;
}
/**
* Returns where an object is on this stack.
*
* @param o the desired object.
* @return the distance from the top of the stack where the object is]
* located; the return value <code>-1</code> indicates that the
* object is not on the stack.
* @since JDK1.0
*/
public int search(int o)
{
int i = lastIndexOf(o);
if (i >= 0)
{
return size() - i;
}
return -1;
}
/**
* Returns clone of current IntStack
*
* @return clone of current IntStack
*/
public Object clone()
throws CloneNotSupportedException
{
return (IntStack) super.clone();
}
}
/**
* A very simple table that stores a list of int.
*
* This version is based on a "realloc" strategy -- a simle array is
* used, and when more storage is needed, a larger array is obtained
* and all existing data is recopied into it. As a result, read/write
* access to existing nodes is O(1) fast but appending may be O(N**2)
* slow. See also SuballocatedIntVector.
* @xsl.usage internal
*/
class IntVector implements Cloneable
{
/** Size of blocks to allocate */
protected int m_blocksize;
/** Array of ints */
protected int m_map[]; // IntStack is trying to see this directly
/** Number of ints in array */
protected int m_firstFree = 0;
/** Size of array */
protected int m_mapSize;
/**
* Default constructor. Note that the default
* block size is very small, for small lists.
*/
public IntVector()
{
m_blocksize = 32;
m_mapSize = m_blocksize;
m_map = new int[m_blocksize];
}
/**
* Construct a IntVector, using the given block size.
*
* @param blocksize Size of block to allocate
*/
public IntVector(int blocksize)
{
m_blocksize = blocksize;
m_mapSize = blocksize;
m_map = new int[blocksize];
}
/**
* Construct a IntVector, using the given block size.
*
* @param blocksize Size of block to allocate
*/
public IntVector(int blocksize, int increaseSize)
{
m_blocksize = increaseSize;
m_mapSize = blocksize;
m_map = new int[blocksize];
}
/**
* Copy constructor for IntVector
*
* @param v Existing IntVector to copy
*/
public IntVector(IntVector v)
{
m_map = new int[v.m_mapSize];
m_mapSize = v.m_mapSize;
m_firstFree = v.m_firstFree;
m_blocksize = v.m_blocksize;
System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree);
}
/**
* Get the length of the list.
*
* @return length of the list
*/
public final int size()
{
return m_firstFree;
}
/**
* Get the length of the list.
*
* @return length of the list
*/
public final void setSize(int sz)
{
m_firstFree = sz;
}
/**
* Append a int onto the vector.
*
* @param value Int to add to the list
*/
public final void addElement(int value)
{
if ((m_firstFree + 1) >= m_mapSize)
{
m_mapSize += m_blocksize;
int newMap[] = new int[m_mapSize];
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
m_map = newMap;
}
m_map[m_firstFree] = value;
m_firstFree++;
}
/**
* Append several int values onto the vector.
*
* @param value Int to add to the list
*/
public final void addElements(int value, int numberOfElements)
{
if ((m_firstFree + numberOfElements) >= m_mapSize)
{
m_mapSize += (m_blocksize+numberOfElements);
int newMap[] = new int[m_mapSize];
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
m_map = newMap;
}
for (int i = 0; i < numberOfElements; i++)
{
m_map[m_firstFree] = value;
m_firstFree++;
}
}
/**
* Append several slots onto the vector, but do not set the values.
*
* @param numberOfElements Int to add to the list
*/
public final void addElements(int numberOfElements)
{
if ((m_firstFree + numberOfElements) >= m_mapSize)
{
m_mapSize += (m_blocksize+numberOfElements);
int newMap[] = new int[m_mapSize];
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
m_map = newMap;
}
m_firstFree += numberOfElements;
}
/**
* Inserts the specified node in this vector at the specified index.
* Each component in this vector with an index greater or equal to
* the specified index is shifted upward to have an index one greater
* than the value it had previously.
*
* @param value Int to insert
* @param at Index of where to insert
*/
public final void insertElementAt(int value, int at)
{
if ((m_firstFree + 1) >= m_mapSize)
{
m_mapSize += m_blocksize;
int newMap[] = new int[m_mapSize];
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
m_map = newMap;
}
if (at <= (m_firstFree - 1))
{
System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
}
m_map[at] = value;
m_firstFree++;
}
/**
* Inserts the specified node in this vector at the specified index.
* Each component in this vector with an index greater or equal to
* the specified index is shifted upward to have an index one greater
* than the value it had previously.
*/
public final void removeAllElements()
{
for (int i = 0; i < m_firstFree; i++)
{
m_map[i] = java.lang.Integer.MIN_VALUE;
}
m_firstFree = 0;
}
/**
* Removes the first occurrence of the argument from this vector.
* If the object is found in this vector, each component in the vector
* with an index greater or equal to the object"s index is shifted
* downward to have an index one smaller than the value it had
* previously.
*
* @param s Int to remove from array
*
* @return True if the int was removed, false if it was not found
*/
public final boolean removeElement(int s)
{
for (int i = 0; i < m_firstFree; i++)
{
if (m_map[i] == s)
{
if ((i + 1) < m_firstFree)
System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
else
m_map[i] = java.lang.Integer.MIN_VALUE;
m_firstFree--;
return true;
}
}
return false;
}
/**
* Deletes the component at the specified index. Each component in
* this vector with an index greater or equal to the specified
* index is shifted downward to have an index one smaller than
* the value it had previously.
*
* @param i index of where to remove and int
*/
public final void removeElementAt(int i)
{
if (i > m_firstFree)
System.arraycopy(m_map, i + 1, m_map, i, m_firstFree);
else
m_map[i] = java.lang.Integer.MIN_VALUE;
m_firstFree--;
}
/**
* Sets the component at the specified index of this vector to be the
* specified object. The previous component at that position is discarded.
*
* The index must be a value greater than or equal to 0 and less
* than the current size of the vector.
*
* @param value object to set
* @param index Index of where to set the object
*/
public final void setElementAt(int value, int index)
{
m_map[index] = value;
}
/**
* Get the nth element.
*
* @param i index of object to get
*
* @return object at given index
*/
public final int elementAt(int i)
{
return m_map[i];
}
/**
* Tell if the table contains the given node.
*
* @param s object to look for
*
* @return true if the object is in the list
*/
public final boolean contains(int s)
{
for (int i = 0; i < m_firstFree; i++)
{
if (m_map[i] == s)
return true;
}
return false;
}
/**
* Searches for the first occurence of the given argument,
* beginning the search at index, and testing for equality
* using the equals method.
*
* @param elem object to look for
* @param index Index of where to begin search
* @return the index of the first occurrence of the object
* argument in this vector at position index or later in the
* vector; returns -1 if the object is not found.
*/
public final int indexOf(int elem, int index)
{
for (int i = index; i < m_firstFree; i++)
{
if (m_map[i] == elem)
return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Searches for the first occurence of the given argument,
* beginning the search at index, and testing for equality
* using the equals method.
*
* @param elem object to look for
* @return the index of the first occurrence of the object
* argument in this vector at position index or later in the
* vector; returns -1 if the object is not found.
*/
public final int indexOf(int elem)
{
for (int i = 0; i < m_firstFree; i++)
{
if (m_map[i] == elem)
return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Searches for the first occurence of the given argument,
* beginning the search at index, and testing for equality
* using the equals method.
*
* @param elem Object to look for
* @return the index of the first occurrence of the object
* argument in this vector at position index or later in the
* vector; returns -1 if the object is not found.
*/
public final int lastIndexOf(int elem)
{
for (int i = (m_firstFree - 1); i >= 0; i--)
{
if (m_map[i] == elem)
return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Returns clone of current IntVector
*
* @return clone of current IntVector
*/
public Object clone()
throws CloneNotSupportedException
{
return new IntVector(this);
}
}
A very simple unsynchronized stack. This one is faster than the java.util-Version.
/**
*
* JCommon : a free Java report library
*
*
* Project Info: http://www.jfree.org/jcommon/
*
* (C) Copyright 2000-2006, by Object Refinery Limited and Contributors.
*
* This library is free software; you can redistribute it and/or modify it under the terms
* of the GNU Lesser General Public License as published by the Free Software Foundation;
* either version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License along with this
* library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
* Boston, MA 02111-1307, USA.
*
* [Java is a trademark or registered trademark of Sun Microsystems, Inc.
* in the United States and other countries.]
*
* ------------
* $Id: FastStack.java,v 1.3 2008/09/10 09:22:05 mungady Exp $
* ------------
* (C) Copyright 2002-2006, by Object Refinery Limited.
*/
import java.io.Serializable;
import java.util.Arrays;
import java.util.EmptyStackException;
/**
* A very simple unsynchronized stack. This one is faster than the
* java.util-Version.
*
* @author Thomas Morgner
*/
public final class FastStack implements Serializable, Cloneable {
private Object[] contents;
private int size;
private int initialSize;
/**
* Creates a new empty stack.
*/
public FastStack() {
this.initialSize = 10;
}
/**
* Creates a new empty stack with the specified initial storage size.
*
* @param size
* the initial storage elements.
*/
public FastStack(int size) {
this.initialSize = Math.max(1, size);
}
/**
* Returns <code>true</code> if the stack is empty, and <code>false</code>
* otherwise.
*
* @return A boolean.
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* Returns the number of elements in the stack.
*
* @return The element count.
*/
public int size() {
return this.size;
}
/**
* Pushes an object onto the stack.
*
* @param o
* the object.
*/
public void push(Object o) {
if (this.contents == null) {
this.contents = new Object[this.initialSize];
this.contents[0] = o;
this.size = 1;
return;
}
final int oldSize = this.size;
this.size += 1;
if (this.contents.length == this.size) {
// grow ..
final Object[] newContents = new Object[this.size + this.initialSize];
System.arraycopy(this.contents, 0, newContents, 0, this.size);
this.contents = newContents;
}
this.contents[oldSize] = o;
}
/**
* Returns the object at the top of the stack without removing it.
*
* @return The object at the top of the stack.
*/
public Object peek() {
if (this.size == 0) {
throw new EmptyStackException();
}
return this.contents[this.size - 1];
}
/**
* Removes and returns the object from the top of the stack.
*
* @return The object.
*/
public Object pop() {
if (this.size == 0) {
throw new EmptyStackException();
}
this.size -= 1;
final Object retval = this.contents[this.size];
this.contents[this.size] = null;
return retval;
}
/**
* Returns a clone of the stack.
*
* @return A clone.
*/
public Object clone() {
try {
FastStack stack = (FastStack) super.clone();
if (this.contents != null) {
stack.contents = (Object[]) this.contents.clone();
}
return stack;
} catch (CloneNotSupportedException cne) {
throw new IllegalStateException("Clone not supported? Why?");
}
}
/**
* Clears the stack.
*/
public void clear() {
this.size = 0;
if (this.contents != null) {
Arrays.fill(this.contents, null);
}
}
/**
* Returns the item at the specified slot in the stack.
*
* @param index
* the index.
*
* @return The item.
*/
public Object get(final int index) {
if (index >= this.size) {
throw new IndexOutOfBoundsException();
}
return this.contents[index];
}
}
Character Stack
/*******************************************************************************
* Copyright (c) 2008 xored software, Inc.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* xored software, Inc. - initial API and Implementation (Alex Panchenko)
*******************************************************************************/
import java.util.EmptyStackException;
public class CharacterStack {
private char[] buffer;
private int size;
public CharacterStack() {
this(16);
}
/**
* @param capacity
*/
public CharacterStack(int capacity) {
buffer = new char[capacity];
size = 0;
}
/**
* @return
*/
public int size() {
return size;
}
/**
* @return
*/
public char peek() {
final int len = size;
if (size == 0) {
throw new EmptyStackException();
}
return buffer[len - 1];
}
/**
* @return
*/
public char pop() {
int len = size;
if (len == 0) {
throw new EmptyStackException();
}
--len;
final char result = buffer[len];
size = len;
return result;
}
/**
* @param c
*/
public void push(char c) {
if (size == buffer.length) {
char[] newBuffer = new char[buffer.length * 2 + 1];
System.arraycopy(buffer, 0, newBuffer, 0, buffer.length);
buffer = newBuffer;
}
buffer[size++] = c;
}
}
Checking the Top: To get the element without removing: using the peek() method
You"ll get an EmptyStackException thrown if the stack is empty.
import java.util.Stack;
public class MainClass {
public static void main (String args[]) {
Stack s = new Stack();
s.push("A");
s.push("B");
s.push("C");
System.out.println("Next: " + s.peek());
}
}
Next: C
Demonstrate the generic Stack class.
import java.util.EmptyStackException;
import java.util.Stack;
class StackDemo {
static void showpush(Stack<Integer> st, int a) {
st.push(a);
System.out.println("push(" + a + ")");
System.out.println("stack: " + st);
}
static void showpop(Stack<Integer> st) {
System.out.print("pop -> ");
Integer a = st.pop();
System.out.println(a);
System.out.println("stack: " + st);
}
public static void main(String args[]) {
Stack<Integer> st = new Stack<Integer>();
System.out.println("stack: " + st);
showpush(st, 42);
showpush(st, 66);
showpush(st, 99);
showpop(st);
showpop(st);
showpop(st);
try {
showpop(st);
} catch (EmptyStackException e) {
System.out.println("empty stack");
}
}
}
extends ArrayList to create Stack
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.ArrayList;
public class FastStack<T> extends ArrayList<T> {
public void push(T o) {
add(o);
}
public T pop() {
return remove(size() - 1);
}
public boolean empty() {
return size() == 0;
}
public T peek() {
return get(size() - 1);
}
}
Growable int stack with type specific access methods
/*
Copyright (c) 2000-2004, Dennis M. Sosnoski
All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
* Neither the name of JiBX nor the names of its contributors may be used
to endorse or promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.lang.reflect.Array;
/**
* Growable <code>int</code> stack with type specific access methods. This
* implementation is unsynchronized in order to provide the best possible
* performance for typical usage scenarios, so explicit synchronization must
* be implemented by a wrapper class or directly by the application in cases
* where instances are modified in a multithreaded environment. See the base
* classes for other details of the implementation.
*
* @author Dennis M. Sosnoski
* @version 1.0
*/
public class IntStack
{
/** Default initial array size. */
public static final int DEFAULT_SIZE = 8;
/** Size of the current array. */
protected int m_countLimit;
/** The number of values currently present in the stack. */
protected int m_countPresent;
/** Maximum size increment for growing array. */
protected int m_maximumGrowth;
/** The underlying array used for storing the data. */
protected int[] m_baseArray;
/**
* Constructor with full specification.
*
* @param size number of <code>int</code> values initially allowed in
* stack
* @param growth maximum size increment for growing stack
*/
public IntStack(int size, int growth) {
m_countLimit = size;
m_maximumGrowth = growth;
m_baseArray = new int[size];
}
/**
* Constructor with initial size specified.
*
* @param size number of <code>int</code> values initially allowed in
* stack
*/
public IntStack(int size) {
this(size, Integer.MAX_VALUE);
}
/**
* Default constructor.
*/
public IntStack() {
this(DEFAULT_SIZE);
}
/**
* Copy (clone) constructor.
*
* @param base instance being copied
*/
public IntStack(IntStack base) {
this(base.m_countLimit, base.m_maximumGrowth);
System.arraycopy(base.m_baseArray, 0, m_baseArray, 0,
base.m_countPresent);
m_countPresent = base.m_countPresent;
}
/**
* Constructor from array of ints.
*
* @param ints array of ints for initial contents
*/
public IntStack(int[] ints) {
this(ints.length);
System.arraycopy(ints, 0, m_baseArray, 0, ints.length);
m_countPresent = ints.length;
}
/**
* Copy data after array resize. This just copies the entire contents of the
* old array to the start of the new array. It should be overridden in cases
* where data needs to be rearranged in the array after a resize.
*
* @param base original array containing data
* @param grown resized array for data
*/
private void resizeCopy(Object base, Object grown) {
System.arraycopy(base, 0, grown, 0, Array.getLength(base));
}
/**
* Increase the size of the array to at least a specified size. The array
* will normally be at least doubled in size, but if a maximum size
* increment was specified in the constructor and the value is less than
* the current size of the array, the maximum increment will be used
* instead. If the requested size requires more than the default growth,
* the requested size overrides the normal growth and determines the size
* of the replacement array.
*
* @param required new minimum size required
*/
private void growArray(int required) {
int size = Math.max(required,
m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
int[] grown = new int[size];
resizeCopy(m_baseArray, grown);
m_countLimit = size;
m_baseArray = grown;
}
/**
* Ensure that the array has the capacity for at least the specified
* number of values.
*
* @param min minimum capacity to be guaranteed
*/
public final void ensureCapacity(int min) {
if (min > m_countLimit) {
growArray(min);
}
}
/**
* Push a value on the stack.
*
* @param value value to be added
*/
public void push(int value) {
int index = getAddIndex();
m_baseArray[index] = value;
}
/**
* Pop a value from the stack.
*
* @return value from top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
*/
public int pop() {
if (m_countPresent > 0) {
return m_baseArray[--m_countPresent];
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to pop empty stack");
}
}
/**
* Pop multiple values from the stack. The last value popped is the
* one returned.
*
* @param count number of values to pop from stack (must be strictly
* positive)
* @return value from top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
* stack
*/
public int pop(int count) {
if (count <= 0) {
throw new IllegalArgumentException("Count must be greater than 0");
} else if (m_countPresent >= count) {
m_countPresent -= count;
return m_baseArray[m_countPresent];
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to pop past end of stack");
}
}
/**
* Copy a value from the stack. This returns a value from within
* the stack without modifying the stack.
*
* @param depth depth of value to be returned
* @return value from stack
* @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
* stack
*/
public int peek(int depth) {
if (m_countPresent > depth) {
return m_baseArray[m_countPresent - depth - 1];
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to peek past end of stack");
}
}
/**
* Copy top value from the stack. This returns the top value without
* removing it from the stack.
*
* @return value at top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
*/
public int peek() {
return peek(0);
}
/**
* Constructs and returns a simple array containing the same data as held
* in this stack. Note that the items will be in reverse pop order, with
* the last item to be popped from the stack as the first item in the
* array.
*
* @return array containing a copy of the data
*/
public int[] toArray() {
int[] copy = new int[m_countPresent];
System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
return copy;
}
/**
* Duplicates the object with the generic call.
*
* @return a copy of the object
*/
public Object clone() {
return new IntStack(this);
}
/**
* Gets the array offset for appending a value to those in the stack.
* If the underlying array is full, it is grown by the appropriate size
* increment so that the index value returned is always valid for the
* array in use by the time of the return.
*
* @return index position for added element
*/
private int getAddIndex() {
int index = m_countPresent++;
if (m_countPresent > m_countLimit) {
growArray(m_countPresent);
}
return index;
}
/**
* Get the number of values currently present in the stack.
*
* @return count of values present
*/
public int size() {
return m_countPresent;
}
/**
* Check if stack is empty.
*
* @return <code>true</code> if stack empty, <code>false</code> if not
*/
public boolean isEmpty() {
return m_countPresent == 0;
}
/**
* Set the stack to the empty state.
*/
public void clear() {
m_countPresent = 0;
}
}
Growable Object stack with type specific access methods
/*
Copyright (c) 2000-2006, Dennis M. Sosnoski
All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
* Neither the name of JiBX nor the names of its contributors may be used
to endorse or promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.lang.reflect.Array;
/**
* Growable <code>Object</code> stack with type specific access methods. This
* implementation is unsynchronized in order to provide the best possible
* performance for typical usage scenarios, so explicit synchronization must
* be implemented by a wrapper class or directly by the application in cases
* where instances are modified in a multithreaded environment.
*
* @author Dennis M. Sosnoski
*/
public class ObjectStack
{
/** Default initial array size. */
public static final int DEFAULT_SIZE = 8;
/** Size of the current array. */
protected int m_countLimit;
/** The number of values currently present in the stack. */
protected int m_countPresent;
/** Maximum size increment for growing array. */
protected int m_maximumGrowth;
/** The underlying array used for storing the data. */
protected Object[] m_baseArray;
/**
* Constructor with full specification.
*
* @param size number of <code>Object</code> values initially allowed in
* stack
* @param growth maximum size increment for growing stack
*/
public ObjectStack(int size, int growth) {
m_countLimit = size;
m_maximumGrowth = growth;
m_baseArray = new Object[size];
}
/**
* Constructor with initial size specified.
*
* @param size number of <code>Object</code> values initially allowed in
* stack
*/
public ObjectStack(int size) {
this(size, Integer.MAX_VALUE);
}
/**
* Default constructor.
*/
public ObjectStack() {
this(DEFAULT_SIZE);
}
/**
* Copy (clone) constructor.
*
* @param base instance being copied
*/
public ObjectStack(ObjectStack base) {
this(base.m_countLimit, base.m_maximumGrowth);
System.arraycopy(base.m_baseArray, 0, m_baseArray, 0,
base.m_countPresent);
m_countPresent = base.m_countPresent;
}
/**
* Constructor from array of strings.
*
* @param strings array of strings for initial contents
*/
public ObjectStack(Object[] strings) {
this(strings.length);
System.arraycopy(strings, 0, m_baseArray, 0, strings.length);
m_countPresent = strings.length;
}
/**
* Copy data after array resize. This just copies the entire contents of the
* old array to the start of the new array. It should be overridden in cases
* where data needs to be rearranged in the array after a resize.
*
* @param base original array containing data
* @param grown resized array for data
*/
private void resizeCopy(Object base, Object grown) {
System.arraycopy(base, 0, grown, 0, Array.getLength(base));
}
/**
* Discards values for a range of indices in the array. Checks if the
* values stored in the array are object references, and if so clears
* them. If the values are primitives, this method does nothing.
*
* @param from index of first value to be discarded
* @param to index past last value to be discarded
*/
private void discardValues(int from, int to) {
for (int i = from; i < to; i++) {
m_baseArray[i] = null;
}
}
/**
* Increase the size of the array to at least a specified size. The array
* will normally be at least doubled in size, but if a maximum size
* increment was specified in the constructor and the value is less than
* the current size of the array, the maximum increment will be used
* instead. If the requested size requires more than the default growth,
* the requested size overrides the normal growth and determines the size
* of the replacement array.
*
* @param required new minimum size required
*/
private void growArray(int required) {
int size = Math.max(required,
m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
Object[] grown = new Object[size];
resizeCopy(m_baseArray, grown);
m_countLimit = size;
m_baseArray = grown;
}
/**
* Ensure that the array has the capacity for at least the specified
* number of values.
*
* @param min minimum capacity to be guaranteed
*/
public final void ensureCapacity(int min) {
if (min > m_countLimit) {
growArray(min);
}
}
/**
* Push a value on the stack.
*
* @param value value to be added
*/
public void push(Object value) {
int index = getAddIndex();
m_baseArray[index] = value;
}
/**
* Pop a value from the stack.
*
* @return value from top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
*/
public Object pop() {
if (m_countPresent > 0) {
Object value = m_baseArray[--m_countPresent];
m_baseArray[m_countPresent] = null;
return value;
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to pop empty stack");
}
}
/**
* Pop multiple values from the stack. The last value popped is the
* one returned.
*
* @param count number of values to pop from stack (must be strictly
* positive)
* @return value from top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
* stack
*/
public Object pop(int count) {
if (count < 0) {
throw new IllegalArgumentException("Count must be greater than 0");
} else if (m_countPresent >= count) {
m_countPresent -= count;
Object value = m_baseArray[m_countPresent];
discardValues(m_countPresent, m_countPresent + count);
return value;
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to pop past end of stack");
}
}
/**
* Copy a value from the stack. This returns a value from within
* the stack without modifying the stack.
*
* @param depth depth of value to be returned
* @return value from stack
* @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
* stack
*/
public Object peek(int depth) {
if (m_countPresent > depth) {
return m_baseArray[m_countPresent - depth - 1];
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to peek past end of stack");
}
}
/**
* Copy top value from the stack. This returns the top value without
* removing it from the stack.
*
* @return value at top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
*/
public Object peek() {
return peek(0);
}
/**
* Constructs and returns a simple array containing the same data as held
* in this stack. Note that the items will be in reverse pop order, with
* the last item to be popped from the stack as the first item in the
* array.
*
* @return array containing a copy of the data
*/
public Object[] toArray() {
Object[] copy = new Object[m_countPresent];
System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
return copy;
}
/**
* Duplicates the object with the generic call.
*
* @return a copy of the object
*/
public Object clone() {
return new ObjectStack(this);
}
/**
* Gets the array offset for appending a value to those in the stack.
* If the underlying array is full, it is grown by the appropriate size
* increment so that the index value returned is always valid for the
* array in use by the time of the return.
*
* @return index position for added element
*/
private int getAddIndex() {
int index = m_countPresent++;
if (m_countPresent > m_countLimit) {
growArray(m_countPresent);
}
return index;
}
/**
* Get the number of values currently present in the stack.
*
* @return count of values present
*/
public int size() {
return m_countPresent;
}
/**
* Check if stack is empty.
*
* @return <code>true</code> if stack empty, <code>false</code> if not
*/
public boolean isEmpty() {
return m_countPresent == 0;
}
/**
* Set the stack to the empty state.
*/
public void clear() {
discardValues(0, m_countPresent);
m_countPresent = 0;
}
}
Growable String stack with type specific access methods.
/*
Copyright (c) 2000-2006, Dennis M. Sosnoski
All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
* Neither the name of JiBX nor the names of its contributors may be used
to endorse or promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.lang.reflect.Array;
/**
* Growable <code>String</code> stack with type specific access methods. This
* implementation is unsynchronized in order to provide the best possible
* performance for typical usage scenarios, so explicit synchronization must
* be implemented by a wrapper class or directly by the application in cases
* where instances are modified in a multithreaded environment.
*
* @author Dennis M. Sosnoski
*/
public class StringStack
{
/** Default initial array size. */
public static final int DEFAULT_SIZE = 8;
/** Size of the current array. */
private int m_countLimit;
/** The number of values currently present in the stack. */
private int m_countPresent;
/** Maximum size increment for growing array. */
private int m_maximumGrowth;
/** The underlying array used for storing the data. */
private String[] m_baseArray;
/**
* Constructor with full specification.
*
* @param size number of <code>String</code> values initially allowed in
* stack
* @param growth maximum size increment for growing stack
*/
public StringStack(int size, int growth) {
String[] array = new String[size];
m_countLimit = size;
m_maximumGrowth = growth;
m_baseArray = array;
}
/**
* Constructor with initial size specified.
*
* @param size number of <code>String</code> values initially allowed in
* stack
*/
public StringStack(int size) {
this(size, Integer.MAX_VALUE);
}
/**
* Default constructor.
*/
public StringStack() {
this(DEFAULT_SIZE);
}
/**
* Copy (clone) constructor.
*
* @param base instance being copied
*/
public StringStack(StringStack base) {
this(base.m_countLimit, base.m_maximumGrowth);
System.arraycopy(base.m_baseArray, 0, m_baseArray, 0,
base.m_countPresent);
m_countPresent = base.m_countPresent;
}
/**
* Constructor from array of strings.
*
* @param strings array of strings for initial contents
*/
public StringStack(String[] strings) {
this(strings.length);
System.arraycopy(strings, 0, m_baseArray, 0, strings.length);
m_countPresent = strings.length;
}
/**
* Copy data after array resize. This just copies the entire contents of the
* old array to the start of the new array. It should be overridden in cases
* where data needs to be rearranged in the array after a resize.
*
* @param base original array containing data
* @param grown resized array for data
*/
private void resizeCopy(Object base, Object grown) {
System.arraycopy(base, 0, grown, 0, Array.getLength(base));
}
/**
* Discards values for a range of indices in the array. Checks if the
* values stored in the array are object references, and if so clears
* them. If the values are primitives, this method does nothing.
*
* @param from index of first value to be discarded
* @param to index past last value to be discarded
*/
private void discardValues(int from, int to) {
for (int i = from; i < to; i++) {
m_baseArray[i] = null;
}
}
/**
* Increase the size of the array to at least a specified size. The array
* will normally be at least doubled in size, but if a maximum size
* increment was specified in the constructor and the value is less than
* the current size of the array, the maximum increment will be used
* instead. If the requested size requires more than the default growth,
* the requested size overrides the normal growth and determines the size
* of the replacement array.
*
* @param required new minimum size required
*/
private void growArray(int required) {
int size = Math.max(required,
m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
String[] grown = new String[size];
resizeCopy(m_baseArray, grown);
m_countLimit = size;
m_baseArray = grown;
}
/**
* Ensure that the array has the capacity for at least the specified
* number of values.
*
* @param min minimum capacity to be guaranteed
*/
public final void ensureCapacity(int min) {
if (min > m_countLimit) {
growArray(min);
}
}
/**
* Push a value on the stack.
*
* @param value value to be added
*/
public void push(String value) {
int index = getAddIndex();
m_baseArray[index] = value;
}
/**
* Pop a value from the stack.
*
* @return value from top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
*/
public String pop() {
if (m_countPresent > 0) {
String value = m_baseArray[--m_countPresent];
m_baseArray[m_countPresent] = null;
return value;
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to pop empty stack");
}
}
/**
* Pop multiple values from the stack. The last value popped is the
* one returned.
*
* @param count number of values to pop from stack (must be strictly
* positive)
* @return value from top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
* stack
*/
public String pop(int count) {
if (count < 0) {
throw new IllegalArgumentException("Count must be greater than 0");
} else if (m_countPresent >= count) {
m_countPresent -= count;
String value = m_baseArray[m_countPresent];
discardValues(m_countPresent, m_countPresent + count);
return value;
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to pop past end of stack");
}
}
/**
* Copy a value from the stack. This returns a value from within
* the stack without modifying the stack.
*
* @param depth depth of value to be returned
* @return value from stack
* @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
* stack
*/
public String peek(int depth) {
if (m_countPresent > depth) {
return m_baseArray[m_countPresent - depth - 1];
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to peek past end of stack");
}
}
/**
* Copy top value from the stack. This returns the top value without
* removing it from the stack.
*
* @return value at top of stack
* @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
*/
public String peek() {
return peek(0);
}
/**
* Constructs and returns a simple array containing the same data as held
* in this stack. Note that the items will be in reverse pop order, with
* the last item to be popped from the stack as the first item in the
* array.
*
* @return array containing a copy of the data
*/
public String[] toArray() {
String[] copy = new String[m_countPresent];
System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
return copy;
}
/**
* Duplicates the object with the generic call.
*
* @return a copy of the object
*/
public Object clone() {
return new StringStack(this);
}
/**
* Gets the array offset for appending a value to those in the stack.
* If the underlying array is full, it is grown by the appropriate size
* increment so that the index value returned is always valid for the
* array in use by the time of the return.
*
* @return index position for added element
*/
private int getAddIndex() {
int index = m_countPresent++;
if (m_countPresent > m_countLimit) {
growArray(m_countPresent);
}
return index;
}
/**
* Get the number of values currently present in the stack.
*
* @return count of values present
*/
public int size() {
return m_countPresent;
}
/**
* Check if stack is empty.
*
* @return <code>true</code> if stack empty, <code>false</code> if not
*/
public boolean isEmpty() {
return m_countPresent == 0;
}
/**
* Set the stack to the empty state.
*/
public void clear() {
discardValues(0, m_countPresent);
m_countPresent = 0;
}
}
If the size of the stack is zero, true is returned; otherwise, false is returned
import java.util.Stack;
public class MainClass {
public static void main (String args[]) {
Stack s = new Stack();
s.push("A");
s.push("B");
s.push("C");
System.out.println(s.pop());
System.out.println(s.empty());
}
}
C false
Removing Elements: To remove an element from the stack, the pop() method
public Object pop()
C
Stack Basics: last-in, first-out behavior
The java.util.Stack class is a Collection that behaves in a last-in-first-out (LIFO) manner.
import java.util.Stack;
public class MainClass {
public static void main (String args[]) {
Stack s = new Stack();
s.push("A");
s.push("B");
s.push("C");
System.out.println(s);
}
}
[A, B, C]
Stack for boolean values
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* $Id: BoolStack.java 468655 2006-10-28 07:12:06Z minchau $
*/
/**
* Simple stack for boolean values.
* @xsl.usage internal
*/
public final class BoolStack implements Cloneable
{
/** Array of boolean values */
private boolean m_values[];
/** Array size allocated */
private int m_allocatedSize;
/** Index into the array of booleans */
private int m_index;
/**
* Default constructor. Note that the default
* block size is very small, for small lists.
*/
public BoolStack()
{
this(32);
}
/**
* Construct a IntVector, using the given block size.
*
* @param size array size to allocate
*/
public BoolStack(int size)
{
m_allocatedSize = size;
m_values = new boolean[size];
m_index = -1;
}
/**
* Get the length of the list.
*
* @return Current length of the list
*/
public final int size()
{
return m_index + 1;
}
/**
* Clears the stack.
*
*/
public final void clear()
{
m_index = -1;
}
/**
* Pushes an item onto the top of this stack.
*
*
* @param val the boolean to be pushed onto this stack.
* @return the <code>item</code> argument.
*/
public final boolean push(boolean val)
{
if (m_index == m_allocatedSize - 1)
grow();
return (m_values[++m_index] = val);
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack.
* @throws EmptyStackException if this stack is empty.
*/
public final boolean pop()
{
return m_values[m_index--];
}
/**
* Removes the object at the top of this stack and returns the
* next object at the top as the value of this function.
*
*
* @return Next object to the top or false if none there
*/
public final boolean popAndTop()
{
m_index--;
return (m_index >= 0) ? m_values[m_index] : false;
}
/**
* Set the item at the top of this stack
*
*
* @param b Object to set at the top of this stack
*/
public final void setTop(boolean b)
{
m_values[m_index] = b;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack.
* @throws EmptyStackException if this stack is empty.
*/
public final boolean peek()
{
return m_values[m_index];
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack. If the stack is empty, it returns false.
*
* @return the object at the top of this stack.
*/
public final boolean peekOrFalse()
{
return (m_index > -1) ? m_values[m_index] : false;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack. If the stack is empty, it returns true.
*
* @return the object at the top of this stack.
*/
public final boolean peekOrTrue()
{
return (m_index > -1) ? m_values[m_index] : true;
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if this stack is empty;
* <code>false</code> otherwise.
*/
public boolean isEmpty()
{
return (m_index == -1);
}
/**
* Grows the size of the stack
*
*/
private void grow()
{
m_allocatedSize *= 2;
boolean newVector[] = new boolean[m_allocatedSize];
System.arraycopy(m_values, 0, newVector, 0, m_index + 1);
m_values = newVector;
}
public Object clone()
throws CloneNotSupportedException
{
return super.clone();
}
}
To find out if an element is on the stack: the search() method
public int search(Object element)
Next: C D [A, B, C, E]
