栈

定义

一种可以实现“先进后出”的存储结构。

分类

• 静态栈
• 动态栈

算法

• 出栈
• 压栈

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

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

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
} STACT, *PSTACT; //PSTACT 相当于 struct Stack *

void init(PSTACT);
void push(PSTACT, int);
void traverse(PSTACT);
bool pop(PSTACT, int *);

int main(void)
{

    STACT S; //STACT 等价于 struct Stack

    init(&S);    //造出一个空栈
    push(&S, 1); //压栈
    push(&S, 2);
    traverse(&S); //遍历输出

    return 0;
}

void init(PSTACT pS)
{
    pS->pTop = (NODE)malloc(sizeof(NODE));
    if (NULL == pS->pTop)
    {
        printf("动态内存分配失败!\n");
        exit(-1)
    }
    else
    {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL; // pS->pBottom->pNext = NULL
    }
}

//压栈
void push(PSTACT pS, int val)
{
    PNODE pNew = (NODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = pS->pTop;
    pS->pTop = pNew;
    return;
}

//遍历
void traverse(PSTACT pS)
{
    PNODE p = pS->pTop;
    while (p != pS->pBottom)
    {
        printf("%d ", p->data);
        p = pS->pNext;
    }
    printf("\n");
    return;
}

//判断栈是否为空
bool empty(PSTACT pS)
{
    if (pS->pTop == pS->pBottom)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//把 pS 所指向的栈出栈一次,并把出栈的元素存入 pVal 形参所指向的变量中.
//出栈失败返回 false,否则返回 true
bool pop(PSTACT pS, int *pVal)
{
    if (empty(pS) == true)
    {
        return false;
    }
    else
    {
        PNODE r = pS->pTop;
        pS->pTop = r->pNext;
        *pVal = r->data;
        free(r);
        r = NULL;
        return true;
    }
}

//清空
void clear(PSTACT pS)
{
    if (empty(pS))
    {
        return;
    }
    else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while (p != pS->pBottom)
        {
            q = p->pNext;
            free(p);
            p = q;
        }
        pS->pTop = pS->pBottom;
    }
}

应用

• 函数调用
• 中断
• 表达式求值
• 内存分配
• 缓冲处理
• 迷宫