last updated 2/12/07
From the taxonomy this structure is Linear - Sequential Access - "Last-in-First-out" access
Features:
Domain:
Structure:
A list where only the most recent item is accessible.
// Stack Interface
// (c) 2002 Dale/Joyce/Weems
public interface StackInterface{
public boolean isEmpty();
public boolean isFull();
public Object top() throws StackUnderflowException;
//sometimes called peek()
public Object pop() throws StackUnderflowException;
//sometimes defined to not return top element
public void push(Object item)throws StackOverflowException;
public int size();
}
When accessing a stack that is empty you either
top and pop can throw an StackUnderflowException if the stack is empty.
push can throw StackOverflowException if the stack is full, and IllegalArgumentException if the item to be pushed is null.
public class StackUnderflowException extends RuntimeException
{
public Stack UnderflowException(){
}
public StackUnderflowException(String message){
super(message);
}
}
public class StackOverflowException extends RuntimeException
{
public Stack OverflowException(){
}
public StackOverflowException(String message){
super(message);
}
}
If your application is stack driven, where the algorithm runs until the stack is empty, then you should explicitly check for the status. Often it's in the form of a while loop.
if( ! myStack.isEmpty())
value = myStack.top();
else
System.out.println("Stack is empty");
Or, use exception handling when an empty stack would be unexpected.
try{
value = myStack.top();
}catch(StackUnderflowException e){
System.out.println("Stack is empty");
}
Many applications naturally use stacks in programming:
In the system: method calls and returns -- track points of return for each call
Parsing expressions in context-free programming languages; nested languages/control structures
Translating infix (algebraic) expressions to postfix and evaluating postfix expressions (interpreter for arithmetic expressions)
"Undo" features in word processing, etc.
Maintaining link histories in a web browser (for support of the back operation)
//----------------------------------------------------------------------
// BalancedApp.java by Dale/Joyce/Weems Chapter 3
//
// Checks for balanced grouping symbols.
// Input consists of a sequence of expressions, one per line.
// Special symbol types are (), [], and {}.
//----------------------------------------------------------------------
import java.util.Scanner;
public class BalancedApp
{
public static void main(String[] args)
{
Scanner conIn = new Scanner(System.in);
// Instantiate new Balanced class with grouping symbols.
Balanced bal = new Balanced("([{", ")]}");
int result; // 0 = balanced, 1 = unbalanced,
// 2 = premature end
String expression = null; // expression to be evaluated
String more = null; // used to stop or continue processing
do
{
// Get next expression to be processed.
System.out.println("Enter an expression to be evaluated: ");
expression = conIn.nextLine();
// Obtain and output result of balanced testing.
result = bal.test(expression);
if (result == 1)
System.out.println("Unbalanced symbols ");
else
if (result == 2)
System.out.println("Premature end of expression");
else
System.out.println("The symbols are balanced.");
// Determine if there is another expression to process.
System.out.println();
System.out.print("Evaluate another expression? (Y=Yes): ");
more = conIn.nextLine();
System.out.println();
}
while (more.equalsIgnoreCase("y"));
}
}
//----------------------------------------------------------------------
// Balanced.java by Dale/Joyce/Weems Chapter 3
//
// Checks for balanced expressions using standard rules.
//
// Matching pairs of open and close symbols are provided to the
// constructor through two string parameters.
//----------------------------------------------------------------------
public class Balanced
{
private String openSet;
private String closeSet;
public Balanced(String openSet, String closeSet)
// Preconditions: No character is contained more than once in the
// combined openSet and closeSet strings.
// The size of openSet = the size of closeSet.
{
this.openSet = openSet;
this.closeSet = closeSet;
}
public int test(String expression)
// Returns 0 if expression is balanced.
// Returns 1 if expression has unbalanced symbols.
// Returns 2 if expression came to end prematurely.
{
char currChar; // current character being studied
int currCharIndex; // index of current character in expression
int lastCharIndex; // index of last character in expression
int openIndex; // index of current character in openSet
int closeIndex; // index of current character in closeSet
boolean stillBalanced = true; // true as long as expression is balanced
BoundedStackInterface stack; // tracks unmatched open symbols
stack = new ArrayStack(expression.length());
currCharIndex = 0;
lastCharIndex = expression.length() - 1;
// while expr. is still balanced and not at end of expr.
while (stillBalanced && (currCharIndex <= lastCharIndex))
{
currChar = expression.charAt(currCharIndex);
openIndex = openSet.indexOf(currChar);
if(openIndex != -1) // if current character is in the openSet
{
// Push the index onto the stack.
stack.push(openIndex);
}
else
{
closeIndex = closeSet.indexOf(currChar);
if(closeIndex != -1) // if current character is in the closeSet
{
try // try to pop an index off the stack
{
openIndex = (Integer)stack.top();
stack.pop();
if (openIndex != closeIndex) // if popped index doesn't match
{
stillBalanced = false; // then expression is not balanced
}
}
catch(StackUnderflowException e) // if stack was empty
{
stillBalanced = false; // then expression is not balanced
}
}
}
currCharIndex++; // set up processing of next character
}
if (!stillBalanced)
return 1; // unbalanced symbols
else if (!stack.isEmpty())
return 2; // premature end of expression
else
return 0; // expression is balanced
}
}
