Связанный список основан стек реализация

В компьютерной науке, стек временного абстрактных типов данных и их структуры, основанной на принципе Последний In First Out (LIFO). Стеки очень широко и широко используется в современных компьютерных системах, и, как правило, осуществляется через сочетание аппаратных и программных функций.

Следующий код показывает, как реализовать стек с помощью связанных списков:


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

}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>