/**
* @brief C語言實(shí)現(xiàn)的順序結(jié)構(gòu)類型的棧
* @author wid
* @date 2013-10-29
*
* @note 若代碼存在 bug 或程序缺陷, 請(qǐng)留言反饋, 謝謝!
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

typedef struct Point2D
{
    int x;
    int y;
}ElemType;      //棧元素結(jié)構(gòu)

typedef struct
{
    ElemType *btm;      //棧底
    ElemType *top;      //棧頂
    int height;         //棧高
    int size;           //棧總大小
}ArrStack;      //棧結(jié)構(gòu)

//棧方法聲明
ArrStack *CreateStack( int nSize );             ///創(chuàng)建一個(gè)大小為nSize的棧
void DestroyStack( ArrStack *pStack );          ///銷毀棧 pStack
void ClearStack( ArrStack *pStack );            ///清空棧 pStack 內(nèi)的元素
int GetHeight( ArrStack *pStack );              ///獲取棧 pStack 的高度
int GetSize( ArrStack *pStack );                ///獲取棧 pStack 的總?cè)萘?BR>int IsEmpty( ArrStack *pStack );                ///檢測(cè)棧 pStack 是否為空棧
int Push( ArrStack *pStack, ElemType *pt );     ///將元素 pt 壓入棧 pStack
int Pop( ArrStack *pStack, ElemType *pt );      ///將棧頂元素出棧到 pt
int GetTop( ArrStack *pStack, ElemType *pt );   ///獲取棧頂元素到 pt
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) );      ///從棧底到棧頂?shù)拿總€(gè)元素依次執(zhí)行 func 函數(shù)
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) );    ///從棧頂?shù)綏５椎拿總€(gè)元素依次執(zhí)行 func 函數(shù)

//棧方法實(shí)現(xiàn)

/**
* @brief 創(chuàng)建一個(gè)大小為 nSize 的棧
*
* @param nSize 棧的初始大小
*
* @return 返回指向創(chuàng)建的棧的指針
*
* @note nSize 初始大小需大于0
*/
ArrStack *CreateStack( int nSize )
{
    //根據(jù)棧結(jié)構(gòu)創(chuàng)建一個(gè)棧
    ArrStack *pStack = (ArrStack *)malloc( sizeof(ArrStack) );

    //申請(qǐng)棧初始空間
    pStack->btm = (ElemType *)calloc( nSize, sizeof(ElemType) );

    //令棧頂指向棧底元素
    pStack->top = &pStack->btm[0];

    //初始化棧高度為 0
    pStack->height = 0;

    //初始化棧大小為初始大小
    pStack->size = nSize;

    return pStack;
}

/**
* @brief 銷毀棧 pStack
*
* @param pStack 指向待銷毀的棧的指針
*
* @return void
*/
void DestroyStack( ArrStack *pStack )
{
    //釋放棧內(nèi)元素
    free( pStack->btm );

    //釋放棧
    free( pStack );
}

/**
* @brief 清空棧內(nèi)元素
*
* @param pStack 指向待清空元素的棧的指針
*
* @return void
*/
void ClearStack( ArrStack *pStack )
{
    //令棧頂指向棧底
    pStack->top = &pStack->btm[0];

    //將棧高度置為 0
    pStack->height = 0;
}

/**
* @brief 獲取棧 pStack 的高度
*
* @param pStack 指向待獲取高度的棧的指針
*
* @param 返回當(dāng)前棧的高度
*/
int GetHeight( ArrStack *pStack )
{
    return pStack->height;
}

/**
* @brief 獲取棧 pStack 的總?cè)萘?BR>*
* @param pStack 指向待獲取總?cè)萘康臈５闹羔?BR>*
* @return 返回棧的當(dāng)前總?cè)萘?BR>*/
int GetSize( ArrStack *pStack )
{
    return pStack->size;
}

/**
* @brief 檢測(cè)棧 pStack 是否為空棧
*
* @param pStack 指向待檢測(cè)的棧的指針
*
* @return 若棧為空, 則返回 TRUE, 否則返回 FALSE
*/
int IsEmpty( ArrStack *pStack )
{
    return pStack->height == 0 ? TRUE : FALSE;
}

/**
* @brief 將元素 pt 壓入棧 pStack
*
* @param pStack 指向待壓入元素的棧的指針
* @param pt 指向待壓入元素的指針
*
* @return 返回成功壓入后棧的高度
*/
int Push( ArrStack *pStack, ElemType *pt )
{
    ///檢測(cè)是否需要擴(kuò)容
    if( pStack->height == pStack->size )
    {   //需要擴(kuò)容

        //重新申請(qǐng)于原棧大小2倍大小的?？臻g
        ElemType *pe = (ElemType *)calloc( pStack->size * 2, sizeof(ElemType) );

        //將舊棧內(nèi)容拷貝到新棧內(nèi)容
        memcpy( pe, pStack->btm, pStack->size * sizeof(ElemType) );

        //重置?？?cè)萘看笮?BR>        pStack->size = pStack->size * 2;

        //釋放舊棧空間
        free( pStack->btm );

        //將棧底指向新開辟的?？臻g
        pStack->btm = pe;

        //棧頂指向新棧最后一個(gè)元素
        pStack->top = &pe[pStack->height-1];
    }

    //將新元素壓入棧
    pStack->btm[pStack->height].x = pt->x;
    pStack->btm[pStack->height].y = pt->y;

    //棧高度自增一
    ++pStack->height;

    //棧頂指向最新棧元素
    pStack->top = &pStack->btm[pStack->height-1];

    return pStack->height;
}

/**
* @brief 將棧頂元素出棧 到 pt
*
* @param pStack 指向待彈出元素的棧的指針
* @param pt 指向接收彈出的元素的指針
*
* @return 出棧成功則返回出棧后棧的高度, 否則返回 -1
*/
int Pop( ArrStack *pStack, ElemType *pt )
{
    ///是否為空棧
    if( pStack->height == 0 )
        return -1;

    //將棧頂元素賦值到 pt
    pt->x = pStack->top->x;
    pt->y = pStack->top->y;

    //棧高度減一
    --pStack->height;

    //棧頂指向棧頂元素的上一個(gè)元素
    pStack->top = &pStack->btm[pStack->height-1];

    return pStack->height;
}

/**
* @brief 獲取棧頂元素到 pt
*
* @param pStack 指向待彈出元素的棧的指針
* @param pt 指向接收彈出的元素的指針
*
* @return 獲取成功則返回棧頂元素的位置, 否則返回 -1
*
* @note 元素位置由 0 計(jì)起
*/
int GetTop( ArrStack *pStack, ElemType *pt )
{
    pt->x = pStack->top->x;
    pt->y = pStack->top->y;

    return pStack->height;
}

/**
* @brief 從棧底到棧頂?shù)拿總€(gè)元素依次執(zhí)行 func 函數(shù)
*
* @param pStack 指向待處理的棧的指針
* @param func 需要執(zhí)行的函數(shù)的指針
*
* @return void
*/
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
    int i = 0;
    for( i = 0; i <  pStack->height; ++i )
    {
        func( &pStack->btm[i] );
    }
}

/**
* @brief 從棧頂?shù)綏５椎拿總€(gè)元素依次執(zhí)行 func 函數(shù)
*
* @param pStack 指向待處理的棧的指針
* @param func 需要執(zhí)行的函數(shù)的指針
*
* @return void
*/
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
    int i = pStack->height - 1;
    for( i; i >= 0; --i )
    {
        func( &pStack->btm[i] );
    }
}

//測(cè)試

void display( ElemType *pt )
{
    printf( "(%d,%d) ", pt->x, pt->y );
}

int main()
{
    ///測(cè)試創(chuàng)建初始大小為 5 的棧
    ArrStack *psk = CreateStack( 5 );

    ///測(cè)試 IsEmpty、GetSize、GetHeight
    if( IsEmpty(psk) == TRUE )
        printf( "Stack Size=%d, Stack Height=%d\n", GetSize(psk), GetHeight(psk) );

    ElemType pt;

    int i = 0;
    ///測(cè)試Push, 向棧內(nèi)壓入8個(gè)元素
    printf( "\n向棧內(nèi)壓入8個(gè)元素后:\n" );
    for( i = 0; i < 8; ++i )
    {
        pt.x = pt.y = i;
        Push( psk, &pt );
    }
    //輸出壓入8個(gè)元素后的棧狀態(tài)
    printf( "Is empty = %d\n", IsEmpty(psk) );
    printf( "Stack size = %d\n", GetSize(psk) );
    printf( "Stack height = %d\n", GetHeight(psk) );

    ///測(cè)試 ForEachStack、ReForEachStack
    printf( "\n測(cè)試 ForEachStack、ReForEachStack:\n" );
    ForEachStack( psk, display );
    putchar('\n');
    ReForEachStack( psk, display );
    putchar('\n');

    ///測(cè)試getTop
    GetTop( psk, &pt );
    printf( "\n棧頂元素為: (%d,%d)\n", pt.x, pt.y );

    ///測(cè)試 Pop
    Pop( psk, &pt );
    printf( "\nPop彈出的元素為(%d,%d), 彈出后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );
    Pop( psk, &pt );
    printf( "\nPop彈出的元素為(%d,%d), 彈出后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );

    ///測(cè)試Push
    pt.x = pt.y = 100;
    Push( psk, &pt );
    printf( "\nPop壓入的元素為(%d,%d), 壓入后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );

    ///執(zhí)行全面出棧操作
    printf( "\n執(zhí)行全面出棧:\n" );
    int n = GetHeight(psk);
    for( i = 0; i < n; ++i )
    {
        Pop( psk, &pt );
        printf( "Pop彈出的元素為(%d,%d), 彈出后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );
    }

    ///銷毀棧
    DestroyStack( psk );

    return 0;
}