Java/Collections Data Structure/Stack
Версия от 18:01, 31 мая 2010; (обсуждение)
Содержание
- 1 A faster, smaller stack implementation.
- 2 A simple integer based stack.
- 3 A very simple unsynchronized stack. This one is faster than the java.util-Version.
- 4 Bracket Checker
- 5 Character Stack
- 6 Demonstration of Stack Class
- 7 extends ArrayList to create Stack
- 8 Generic stack demo with annotation
- 9 Growable int stack with type specific access methods
- 10 Growable Object stack with type specific access methods
- 11 Growable String stack with type specific access methods.
- 12 Link stack
- 13 Show String Reversals
- 14 Stack data structure
- 15 Stack for boolean values
- 16 Stack in java.util
- 17 String Reverser Through Stack
- 18 Triangular numbers
- 19 Triangular numbers with stack replaces recursion
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;
}
}
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 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];
}
}
Bracket Checker
import java.io.IOException;
public class BracketChecker {
private String input;
public BracketChecker(String in) {
input = in;
}
public void check() {
int stackSize = input.length();
Stack theStack = new Stack(stackSize);
for (int j = 0; j < input.length(); j++)
{
char ch = input.charAt(j);
switch (ch) {
case "{": // opening symbols
case "[":
case "(":
theStack.push(ch); // push them
break;
case "}": // closing symbols
case "]":
case ")":
if (!theStack.isEmpty()) // if stack not empty,
{
char chx = theStack.pop(); // pop and check
if ((ch == "}" && chx != "{") || (ch == "]" && chx != "[")
|| (ch == ")" && chx != "("))
System.out.println("Error: " + ch + " at " + j);
} else
// prematurely empty
System.out.println("Error: " + ch + " at " + j);
break;
default: // no action on other characters
break;
}
}
if (!theStack.isEmpty())
System.out.println("Error: missing right delimiter");
}
public static void main(String[] args) throws IOException {
String input = "{Java [Source] (and) {[(Support)]}}";
BracketChecker theChecker = new BracketChecker(input);
theChecker.check();
}
}
class Stack {
private int maxSize;
private char[] stackArray;
private int top;
public Stack(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) {
stackArray[++top] = j;
}
public char pop() {
return stackArray[top--];
}
public char peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
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;
}
}
Demonstration of Stack Class
// : c11:Stacks.java
// Demonstration of Stack Class.
// From "Thinking in Java, 3rd ed." (c) Bruce Eckel 2002
// www.BruceEckel.ru. See copyright notice in CopyRight.txt.
import java.util.Stack;
public class Stacks {
public static void main(String[] args) {
Stack stack = new Stack();
for (int i = 0; i < 10; i++)
stack.push(new Integer(i));
System.out.println("stack = " + stack);
// Treating a stack as a Vector:
stack.addElement("The last line");
System.out.println("element 5 = " + stack.elementAt(5));
System.out.println("popping elements:");
while (!stack.empty())
System.out.println(stack.pop());
}
} ///:~
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);
}
}
Generic stack demo with annotation
public class Stack<T> {
private T[] items;
private int top;
@SuppressWarnings("unchecked")
public Stack(int size) {
items = (T[]) new Object[size];
top = -1;
}
public void push(T item) throws Exception {
if (top == items.length - 1)
throw new Exception("Stack Full");
items[++top] = item;
}
public T pop() throws Exception {
if (top == -1)
throw new Exception("Stack Empty");
return items[top--];
}
}
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;
}
}
Link stack
public class LinkStack {
private LinkList list;
public LinkStack() {
list = new LinkList();
}
public void push(long j) {
list.insertFirst(j);
}
public long pop() {
return list.deleteFirst();
}
public boolean isEmpty() {
return (list.isEmpty());
}
public void displayStack() {
System.out.print("Stack: ");
list.displayList();
}
public static void main(String[] args) {
LinkStack theStack = new LinkStack();
theStack.push(20);
theStack.push(40);
theStack.displayStack();
theStack.push(60);
theStack.push(80);
theStack.displayStack();
theStack.pop();
theStack.pop();
theStack.displayStack();
}
class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(long d) {
Link newLink = new Link(d);
newLink.next = first;
first = newLink;
}
public long deleteFirst() {
Link buf = first;
first = first.next;
return buf.data;
}
public void displayList() {
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
class Link {
public long data; // data item
public Link next; // next link in list
public Link(long d) {
data = d;
}
public void displayLink() {
System.out.print(data + " ");
}
}
}
}
Show String Reversals
/*
* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. 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.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
*
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/
import java.util.*;
/**
* Show String Reversals
* @version $Id: StringReverse.java,v 1.4 2000/11/25 17:56:18 ian Exp $
*/
public class StringReverse {
public static void main(String[] argv) {
//+
String s = "Father Charles Goes Down And Ends Battle";
// Put it in the stack frontwards
Stack myStack = new Stack();
StringTokenizer st = new StringTokenizer(s);
while (st.hasMoreTokens()) myStack.push(st.nextElement());
// Print the stack backwards
System.out.print(""" + s + """ + " backwards by word is:\n\t\"");
while (!myStack.empty()) {
System.out.print(myStack.pop());
System.out.print(" ");
}
System.out.println(""");
//-
}
}
Stack data structure
public class MyStack {
private int maxSize;
private long[] stackArray;
private int top;
public MyStack(int s) {
maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
public void push(long j) {
stackArray[++top] = j;
}
public long pop() {
return stackArray[top--];
}
public long peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
MyStack theStack = new MyStack(10); // make new stack
theStack.push(20);
theStack.push(40);
theStack.push(60);
theStack.push(80);
while (!theStack.isEmpty()) {
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
}
System.out.println("");
}
}
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();
}
}
Stack in java.util
import java.util.Stack;
public class StackExample {
public static void main(String args[]) {
Stack s = new Stack();
s.push("Java");
s.push("Source");
s.push("and");
System.out.println("Next: " + s.peek());
s.push("Support");
System.out.println(s.pop());
s.push(".");
int count = s.search("Java");
while (count != -1 && count > 1) {
s.pop();
count--;
}
System.out.println(s.pop());
System.out.println(s.empty());
}
}
String Reverser Through Stack
import java.io.IOException;
public class StringReverserThroughStack {
private String input;
private String output;
public StringReverserThroughStack(String in) {
input = in;
}
public String doRev() {
int stackSize = input.length();
Stack theStack = new Stack(stackSize);
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
theStack.push(ch);
}
output = "";
while (!theStack.isEmpty()) {
char ch = theStack.pop();
output = output + ch;
}
return output;
}
public static void main(String[] args) throws IOException {
String input = "Java Source and Support";
String output;
StringReverserThroughStack theReverser = new StringReverserThroughStack(input);
output = theReverser.doRev();
System.out.println("Reversed: " + output);
}
class Stack {
private int maxSize;
private char[] stackArray;
private int top;
public Stack(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) {
stackArray[++top] = j;
}
public char pop() {
return stackArray[top--];
}
public char peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
}
Triangular numbers
import java.io.IOException;
public class Triangle {
public static void main(String[] args) throws IOException {
int theNumber = 100;
int theAnswer = triangle(theNumber);
System.out.println("Triangle=" + theAnswer);
}
public static int triangle(int n) {
if (n == 1)
return 1;
else
return (n + triangle(n - 1));
}
}
Triangular numbers with stack replaces recursion
import java.io.IOException;
public class TriangleStack {
static int num;
static int ans;
static Stack theStack;
public static void main(String[] args) throws IOException {
num = 100;
stackTriangle();
System.out.println("Triangle=" + ans);
}
public static void stackTriangle() {
theStack = new Stack(10000); // make a stack
ans = 0; // initialize answer
while (num > 0) // until n is 1,
{
theStack.push(num); // push value
--num; // decrement value
}
while (!theStack.isEmpty()) // until stack empty,
{
int newN = theStack.pop(); // pop value,
ans += newN; // add to answer
}
}
}
class Stack {
private int maxSize; // size of stack array
private int[] data;
private int top; // top of stack
public Stack(int s) {
maxSize = s;
data = new int[maxSize];
top = -1;
}
public void push(int p) {
data[++top] = p;
}
public int pop() {
return data[top--];
}
public int peek() {
return data[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
