堆栈数组实现方式(c、c++、java)

2016-07-31 0:43:56 暂无评论阳光倾城算法与数据结构 843

堆栈数组实现方式C代码：

    #include "stackar.h"
        #include "fatal.h"

        #define EmptyTOS ( -1 )
        #define MinStackSize ( 5 )
        struct StackRecord
        {
            int Capacity;
            int TopOfStack;
            ElementType *Array;
        };
/* START: fig3_48.txt */
        int
        IsEmpty( Stack S )
        {
            return S->TopOfStack == EmptyTOS;
        }
/* END */
        int
        IsFull( Stack S )
        {
            return S->TopOfStack == S->Capacity - 1;
        }
/* START: fig3_46.txt */
        Stack
        CreateStack( int MaxElements )
        {
            Stack S;

/* 2*/          Error( "Stack size is too small" );
/* 3*/      S = malloc( sizeof( struct StackRecord ) );
/* 4*/      if( S == NULL )
/* 5*/          FatalError( "Out of space!!!" );
/* 6*/      S->Array = malloc( sizeof( ElementType ) * MaxElements );
/* 7*/      if( S->Array == NULL )
/* 8*/          FatalError( "Out of space!!!" );
/* 9*/      S->Capacity = MaxElements;
/*10*/      MakeEmpty( S );
/*11*/      return S;
        }
/* END */
/* START: fig3_49.txt */
        void
        MakeEmpty( Stack S )
        {
            S->TopOfStack = EmptyTOS;
        }
/* END */
/* START: fig3_47.txt */
        void
        DisposeStack( Stack S )
        {
            if( S != NULL )
            {
                free( S->Array );
                free( S );
            }
        }
/* END */
/* START: fig3_50.txt */
        void
        Push( ElementType X, Stack S )
        {
            if( IsFull( S ) )
                Error( "Full stack" );
            else
                S->Array[ ++S->TopOfStack ] = X;
        }
/* END */
/* START: fig3_51.txt */
        ElementType
        Top( Stack S )
        {
            if( !IsEmpty( S ) )
                return S->Array[ S->TopOfStack ];
            Error( "Empty stack" );
            return 0; /* Return value used to avoid warning */
        }
/* END */
/* START: fig3_52.txt */
        void
        Pop( Stack S )
        {
            if( IsEmpty( S ) )
                Error( "Empty stack" );
            else
                S->TopOfStack--;
        }
/* END */
/* START: fig3_53.txt */
        ElementType
        TopAndPop( Stack S )
        {
            if( !IsEmpty( S ) )
                return S->Array[ S->TopOfStack-- ];
            Error( "Empty stack" );
            return 0; /* Return value used to avoid warning */
        }
/* END */

堆栈数组实现C++代码：

// 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 Object[ DEFAULT_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( ) {
        if( isEmpty( ) )
            throw new UnderflowException( "ArrayStack top" );
        return theArray[ topOfStack ];
    }
    /**
     * Remove the most recently inserted item from the stack.
     * @throws UnderflowException if the stack is empty.
     */
    public void pop( ) {
        if( isEmpty( ) )
            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( ) {
        if( isEmpty( ) )
            throw new UnderflowException( "ArrayStack topAndPop" );
        return theArray[ topOfStack-- ];
    }
    /**
     * Insert a new item into the stack.
     * @param x the item to insert.
     */
    public void push( Object x ) {
        if( topOfStack + 1 == theArray.length )
            doubleArray( );
        theArray[ ++topOfStack ] = x;
    }
    /**
     * Internal method to extend theArray.
     */
    private void doubleArray( ) {
        Object [ ] newArray;
        newArray = new Object[ theArray.length * 2 ];

            newArray[ i ] = theArray[ i ];
        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 UnderflowException( String message ) {
        super( message );
    }
}
// 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    push( Object 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( );
    }

堆栈数组实现java：

声明: 除非转自他站（如有侵权，请联系处理）外，本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明：转自《堆栈数组实现方式(c、c++、java)》
本文地址：https://www.zhiletu.com/archives-7748.html
关注公众号：

赞赏

wechat pay 微信赞赏 alipay pay 支付宝赞赏

java

上一篇：图与网络的基本概念
下一篇：堆栈链表实现方式（C）

堆栈数组实现方式(c、c++、java)

相关文章

在线留言