数据结构03：栈

/*

 * 根据郝斌老师视频整理

 * 编译环境：

 * guo@linux:~$ gcc --version

 * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

 */

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>



#define FALSE 0

#define TRUE 1



typedef struct Node

{

        int data;

        struct Node *pNext;

}NODE, *PNODE;



typedef struct Stack

{

        PNODE pTop;

        PNODE pBottom;

}STACK, *PSTACK;



/**********************声明**********************************/

/*初始化栈*/

void InitStack(PSTACK );

/*压栈*/

void PushStack(PSTACK , int );

/*遍历*/

void TraverseStack(PSTACK );

/*判断栈是否为空*/

int  IsEmpty(PSTACK );

/*出栈*/

int  PopStack(PSTACK ,int *);

/*清空栈*/

void ClearStack(PSTACK );





/*

 * 函数名称：InitStack。

 * 输入参数：pStack栈变量的地址。

 * 输出参数：无。

 * 函数说明：新建一个栈。栈的特点是"先入后出"。

 */

void InitStack(PSTACK pStack)

{

        /*申请一块内存，将内存地址赋值给栈变量所指向的pTop成员*/

        pStack->pTop = (PNODE)malloc(sizeof(NODE));

        if (NULL == pStack->pTop)

        {

                printf("动态分配内存失败！\n");

                exit(-1);

        }

        pStack->pBottom = pStack->pTop;

        pStack->pBottom->pNext = NULL;



        return;

}



/*

 * 函数名称：PushStack。

 * 输入参数：pStack栈变量的地址;val压栈的值。

 * 输出参数：无。

 * 函数说明：将一个元素压入栈中。

 */

void PushStack(PSTACK pStack, int val)

{

        PNODE pNew = (PNODE)malloc(sizeof(NODE));

        if (NULL == pNew)

        {

                printf("动态分配内存失败！\n");

                exit(-1);

        }

        

        pNew->data = val;

        pNew->pNext = pStack->pTop;

        pStack->pTop = pNew;



        return;

}



/*

 * 函数名称：TraverseStack。

 * 输入参数：pStack栈变量的地址。

 * 输出参数：无。

 * 函数说明：将一个栈遍历输出。

 */

void TraverseStack(PSTACK pStack)

{

        PNODE p = pStack->pTop;



        if (pStack->pTop == pStack->pBottom)

        {

                printf("栈为空！\n");

        }

        else

        {

                while (p != pStack->pBottom)

                {

                        printf("%d ",p->data);

                        p = p->pNext;

                }

                printf("\n");

        }



        return;

}



/*

 * 函数名称：IsEmpty。

 * 输入参数：pStack栈变量的地址。

 * 输出参数：如果栈为空返回TRUE；否则返回FALSE。

 * 函数说明：判断栈是否为空。

 */

int IsEmpty(PSTACK pStack)

{

        if (pStack->pTop == pStack->pBottom)

                return TRUE;

        else

                return FALSE;

}





/*

 * 函数名称：PopStack。

 * 输入参数：pStack栈变量的地址；pVal保存出栈的值。

 * 输出参数：出栈成功返回TRUE；否则返回FALSE。

 * 函数说明：出栈。

 */

int PopStack(PSTACK pStack,int *pVal)

{

    if ( IsEmpty(pStack) )

    {

        return FALSE;

    }

    else

    {

        PNODE r = pStack->pTop;

        *pVal = r->data;

        pStack->pTop = r->pNext;

        free(r);

        r = NULL;

        return TRUE;

    }

}



/*

 * 函数名称：ClearStack。

 * 输入参数：pStack栈变量的地址。

 * 输出参数：无。

 * 函数说明：清空栈。

 */

void ClearStack(PSTACK pStack)

{

    if ( IsEmpty(pStack) )

    {

        return ;    

    }

    else

    {

        PNODE p = pStack->pTop;

        PNODE q = NULL;

        while (p != pStack->pBottom)

        {

            q = p->pNext;

            free(p);

            p = q;

        }

    }

    pStack->pTop = pStack->pBottom;

}



int main(void)

{

        STACK Stack;

    int val;



        InitStack(&Stack);

        PushStack(&Stack, 1);

        PushStack(&Stack, 2);

        PushStack(&Stack, 3);

        PushStack(&Stack, 4);

    PushStack(&Stack, 5);

    PushStack(&Stack, 6);

    PushStack(&Stack, 7);

    PushStack(&Stack, 8);

        TraverseStack(&Stack);



    if ( PopStack(&Stack, &val) )

    {

        printf("出栈的元素是%d\n", val);

    }

    else

    {

        printf("出栈失败!\n");

    }

    printf("出栈后遍历：\n");

    TraverseStack(&Stack);



    if ( PopStack(&Stack, &val) )

    {

        printf("出栈的元素是%d\n", val);

    }

    else

    {

        printf("出栈失败!\n");

    }

    printf("出栈后遍历：\n");

    TraverseStack(&Stack);



    ClearStack(&Stack);

    printf("清空后遍历：\n");

    TraverseStack(&Stack);



        return 0;

}