数据结构——栈

链式栈结构体

struct Stack包含栈PNODE 类型的顶指针pTop, 栈底指针pBottom；PNODE类型指针指向栈中数据节点**

创建链式栈

malloc 函数分配 Stack 数据结构空间，同时malloc创建节点，pTop、pBottom指针指向该节点，初始化节点的pNext指向NULL。
此节点作为栈的起始地址，pBottom始终指向此节点

数据入栈函数push_stack()

创建入栈的节点，初始化节点数据，插入栈中

#include 
#include 
#include 

struct Nodes {
    int data;
    struct Node *pNext;
};
typedef struct Nodes NODE, *PNODE;

typedef struct Stack {
    PNODE pTop;
    PNODE pBottom;
}STACK, *PSTACK;

PSTACK create_stack(void);
void push_stack(PSTACK pS, int val);
bool pop_stack(PSTACK pS, int *pData);
bool is_empty(PSTACK pS);
void traverse_stack(PSTACK pS);
void clear_stack(PSTACK pS);


int main()
{
    int data_pop;
    //创建一个空的栈，pS指针指向该栈
    PSTACK pS = create_stack();

    //向该栈中压入数据，遍历该栈并输出栈中的数据
    push_stack(pS, 2);
    push_stack(pS, 12);
    push_stack(pS, 32);
    push_stack(pS, 123);
    traverse_stack(pS);

    pop_stack(pS, &data_pop);
    traverse_stack(pS);
    //从该栈中推出数据，遍历该栈并输出栈中的数据
    if(pop_stack(pS, &data_pop))
        printf("pop succeed, the data poped out is: %d\n", data_pop);
    else
        printf("pop failed\n");


    traverse_stack(pS);
    //清空栈，遍历该栈并输出栈中的数据
    clear_stack(pS);
    printf("data cleared!\n");
    traverse_stack(pS);

    return 0;
}

/**
 * @brief Create a stack object
 * 
 * @return PSTACK 
 */
PSTACK create_stack(void)
{
    PSTACK pS = (PSTACK)malloc(sizeof(STACK));
    pS->pTop = (PNODE)malloc(sizeof(NODE));

    if(NULL == pS || NULL == pS->pTop) {
        printf("malloc failed\n");
        exit(-1);
    } else {
        pS->pBottom = pS->pTop;
        pS->pBottom->pNext = NULL;
    }

    return pS;
}

/**
 * @brief 向pS指针指向的栈中压入数据 val
 * 
 * @param pS 
 * @param val 
 */
void push_stack(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew) {
        printf("malloc failed\n");
        exit(-1);
    } else {
        pNew->data = val;
        pNew->pNext = (struct Node *)pS->pTop;
        pS->pTop = pNew;
    }
    return ;
}

/**
 * @brief 从栈中推出数据，
 *      并将推出的数据保存在pData指针所指向的位置
 * 
 * @param pS 
 * @param pData 
 */
bool pop_stack(PSTACK pS, int *pData)
{
    if (is_empty(pS)) 
        return false;
    else {
        PNODE p = pS->pTop;
        *pData = p->data;
        pS->pTop = (PNODE)p->pNext;
        free(p);
        p = NULL;
        return true;
    }
}

/**
 * @brief 判断 pS 所指向的栈是否为空
 * 
 * @param pS 
 * @return true 
 * @return false 
 */
bool is_empty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom)
        return true;
    else
        return false;
}

/**
 * @brief 遍历栈 pS，并自栈顶向栈底输出栈中的数据
 * 
 * @param pS 
 */
void traverse_stack(PSTACK pS)
{
    PNODE pCurrent = pS->pTop;
    printf("Now datas int the stack are:\n");
    while (pCurrent != pS->pBottom) 
    {
        printf("%d  ", pCurrent->data);
        pCurrent = (PNODE)pCurrent->pNext;
    }
    printf("\n");
    return ;
}

/**
 * @brief 清空栈 pS，即将其还原位空栈
 * 
 * @param pS 
 */
void clear_stack(PSTACK pS)
{
    if (is_empty(pS)) {
        return ; 
    } else {
        PNODE p = pS->pTop;
        PNODE r = NULL;
        while (p != pS->pBottom)
        {
            r = (PNODE)p->pNext;
            free(p);
            p = r;
        }
        pS->pTop = pS->pBottom;
    }
}