java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips arrow java.lang arrow Linked-list Based Stack Implementation
 
 
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: 4101
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:
 
 
 
Linked-list Based Stack Implementation E-mail
User Rating: / 136
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 linked-lists:

// ListStack 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

/**
 * List-based implementation of the stack.
 @author Mark Allen Weiss
 */
public class ListStack implements Stack {
    /**
     * Construct the stack.
     */
    public ListStack( ) {
        topOfStack = null;
    }
    
    /**
     * Test if the stack is logically empty.
     @return true if empty, false otherwise.
     */
    public boolean isEmpty( ) {
        return topOfStack == null;
    }
    
    /**
     * Make the stack logically empty.
     */
    public void makeEmpty( ) {
        topOfStack = null;
    }
    
    /**
     * Insert a new item into the stack.
     @param x the item to insert.
     */
    public void pushObject x ) {
        topOfStack = new ListNodex, topOfStack );
    }
    
    /**
     * Remove the most recently inserted item from the stack.
     @throws UnderflowException if the stack is empty.
     */
    public void pop( ) {
        ifisEmpty( ) )
            throw new UnderflowException"ListStack pop" );
        topOfStack = topOfStack.next;
    }
    
    /**
     * 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"ListStack top" );
        return topOfStack.element;
    }
    
    /**
     * Return and remove the most recently inserted item
     * from the stack.
     @return the most recently inserted item in the stack.
     @throws UnderflowException if the stack is empty.
     */
    public Object topAndPop( ) {
        ifisEmpty( ) )
            throw new UnderflowException"ListStack topAndPop" );
        
        Object topItem = topOfStack.element;
        topOfStack = topOfStack.next;
        return topItem;
    }
    
    private ListNode topOfStack;
}

/**
 * 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( );
}

// Basic node stored in a linked list
// Note that this class is not accessible outside
// of package weiss.nonstandard

class ListNode {
    // Constructors
    public ListNodeObject theElement ) {
        thistheElement, null );
    }
    
    public ListNodeObject theElement, ListNode n ) {
        element = theElement;
        next    = n;
    }
    
    public Object   element;
    public ListNode next;
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 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.