栈的解读 - 【c】

前沿

栈广泛应用在各种软件系统中，所以这块的知识点我们也要好好掌握起来。

定义

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。

简单的来说就是一种可以实现"先进后出" 的存储结构

栈类似于箱子

分类

栈一般分为两类

静态栈（类似于用数组实现）动态栈（类似于用链表实现）

算法

这边我们来看看栈的出栈和入栈的伪算法

先来看看入栈

//伪代码
void push(struct Stack *pS, int val)
{
    struct Node * pNew = (struct Node *)malloc(sizeof(struct Node));
    pNew->data = val;
    pNew->pNext = pS->pTop; 
    pS->pTop = pNew;
    return;
}

首先初始化的时候 pTop 和 pBottom 都指向空然后我们创建一个节点 pNew, 让他指向下一个节点的指针域。这里我们要注意，这里应该指向的是 pTop所指向的指针域最后把 pNew 赋值给 pTop, 完成pTop 指向新的节点。

再来看看出栈 写法

//伪代码
bool pop(struct Stack *pS, int * pVal)
{    
        struct Node * q = pS->pTop;
        *pVal = q->data;
        pS->pTop = q->pNext;
        free(q);
        q = NULL;
        return true;    
}

出栈算法看过去时简单的，但有点要特别注意，就是要记得释放内存，避免野指针所以我们定义一个指针变量 q 来做临时存储使用。最后我们在free()释放内存