java left logo
java middle logo
java right logo
 


 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4084
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Array-based Stack Implementation in Java E-mail
User Rating: / 224
PoorBest 

In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are very widely and extensively used in modern computer systems, and are usually implemented through a combination of hardware and software features.

Following code shows how to implement a stack using arrays:

// ArrayStack class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void push( x )         --> Insert x
// void pop( )            --> Remove most recently inserted item
// Object top( )          --> Return most recently inserted item
// Object topAndPop( )    --> Return and remove most recent item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// top, pop, or topAndPop on empty stack

/**
 * Array-based implementation of the stack.
 @author Mark Allen Weiss
 */
public class ArrayStack implements Stack {
    /**
     * Construct the stack.
     */
    public ArrayStack( ) {
        theArray = new ObjectDEFAULT_CAPACITY ];
        topOfStack = -1;
    }
    
    /**
     * Test if the stack is logically empty.
     @return true if empty, false otherwise.
     */
    public boolean isEmpty( ) {
        return topOfStack == -1;
    }
    
    /**
     * Make the stack logically empty.
     */
    public void makeEmpty( ) {
        topOfStack = -1;
    }
    
    /**
     * Get the most recently inserted item in the stack.
     * Does not alter the stack.
     @return the most recently inserted item in the stack.
     @throws UnderflowException if the stack is empty.
     */
    public Object top( ) {
        ifisEmpty( ) )
            throw new UnderflowException"ArrayStack top" );
        return theArraytopOfStack ];
    }
    
    /**
     * Remove the most recently inserted item from the stack.
     @throws UnderflowException if the stack is empty.
     */
    public void pop( ) {
        ifisEmpty( ) )
            throw new UnderflowException"ArrayStack pop" );
        topOfStack--;
    }
    
    /**
     * Return and remove the most recently inserted item
     * from the stack.
     @return the most recently inserted item in the stack.
     @throws Underflow if the stack is empty.
     */
    public Object topAndPop( ) {
        ifisEmpty( ) )
            throw new UnderflowException"ArrayStack topAndPop" );
        return theArraytopOfStack-- ];
    }
    
    /**
     * Insert a new item into the stack.
     @param x the item to insert.
     */
    public void pushObject x ) {
        iftopOfStack + == theArray.length )
            doubleArray( );
        theArray++topOfStack = x;
    }
    
    /**
     * Internal method to extend theArray.
     */
    private void doubleArray( ) {
        Object [ ] newArray;
        
        newArray = new ObjecttheArray.length * ];
        forint i = 0; i < theArray.length; i++ )
            newArray= theArray];
        theArray = newArray;
    }
    
    private Object [ ] theArray;
    private int        topOfStack;
    
    private static final int DEFAULT_CAPACITY = 10;
    
    
}


/**
 * Exception class for access in empty containers
 * such as stacks, queues, and priority queues.
 @author Mark Allen Weiss
 */
public class UnderflowException extends RuntimeException {
    /**
     * Construct this exception object.
     @param message the error message.
     */
    public UnderflowExceptionString message ) {
        supermessage );
    }
}


// Stack interface
//
// ******************PUBLIC OPERATIONS*********************
// void push( x )         --> Insert x
// void pop( )            --> Remove most recently inserted item
// Object top( )          --> Return most recently inserted item
// Object topAndPop( )    --> Return and remove most recent item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// top, pop, or topAndPop on empty stack
    
    /**
     * Protocol for stacks.
     @author Mark Allen Weiss
     */
    public interface Stack {
        /**
         * Insert a new item into the stack.
         @param x the item to insert.
         */
        void    pushObject x );
        
        /**
         * Remove the most recently inserted item from the stack.
         @exception UnderflowException if the stack is empty.
         */
        void    pop( );
        
        /**
         * Get the most recently inserted item in the stack.
         * Does not alter the stack.
         @return the most recently inserted item in the stack.
         @exception UnderflowException if the stack is empty.
         */
        Object  top( );
        
        
        /**
         * Return and remove the most recently inserted item
         * from the stack.
         @return the most recently inserted item in the stack.
         @exception UnderflowException if the stack is empty.
         */
        Object  topAndPop( );
        
        /**
         * Test if the stack is logically empty.
         @return true if empty, false otherwise.
         */
        boolean isEmpty( );
        
        /**
         * Make the stack logically empty.
         */
        void    makeEmpty( );
    }

 Related Tips

 
< Prev   Next >
Posted by Yogesh, on Wednesday, 28 June 2006 at 9:56

in doubleArray function System.arraycopy method could be used. it is much faster and standard way to do this kind of operations.


 1 
Page 1 of 1 ( 1 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.