数据结构入门-栈

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

分类：

1. 静态栈
2. 动态栈

算法：

1. 出栈
2. 压栈

代码实现：

多敲，多敲，后期改进

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


typedef struct node
{
    int data;
    struct node * pnext;
}node , * pnode;


typedef struct stack
{
    pnode ptop;
    pnode pbottom;
}stack , * pstack;


void init(pstack);
void push(pstack , int);
void traverse(pstack);
bool pop(pstack , int *);
void clear(pstack ps);


int main(void)
{
    stack s; // stack等价于 struct stack
    int val;

    init(&s); // 目的是造出一个空栈

    push(&s , 1); // 压栈
    push(&s , 8);
    push(&s , 23);
    push(&s , 26);
    push(&s , 34);
    push(&s , 45);
    push(&s , 76);
    push(&s , 88);
    traverse(&s); // 遍历输出

    if(pop(&s , &val))
    {
        printf("你删除的是%d\n", val );
        traverse(&s);
        printf("清空数据\n");
        clear(&s);
        traverse(&s);
    }
    else
    {
        printf("删除失败\n");
    }
}




void init(pstack ps)
{
    ps->ptop = (pnode)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(pstack ps, int val)
{
    pnode pnew = (pnode)malloc(sizeof(node));

    pnew->data = val; 

    pnew->pnext = ps->ptop; // 这里需要注意
    ps->ptop = pnew;

    return;
}


void traverse(pstack ps)
{
    pnode p = ps->ptop;

    while(p != ps->pbottom)
    {
        printf("%d ", p->data);
        p = p->pnext;
    }

    printf("\n");
    return;
}


bool empty(pstack ps )
{
    if (ps->ptop == ps->pbottom)
        return true;
    else
        return false;

}


// 把ps所指向的栈出栈一次，并把出栈元素存下
bool pop(pstack ps , int *val)
{

    if (empty(ps))
    {
        return false;
    }
    else
    {
        pnode p = ps->ptop;
        *val = p->data;

        ps->ptop = p->pnext;
        free(p);
        p = null;
        return true;

    }
    
}


// 清空
void clear(pstack 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;
    }
}

应用：

1. 函数调用
2. 中断
3. 表达式求值
4. 内存分配
5. 缓冲处理
6. 迷宫