栈知识总结

Julia999

线性结构的两种常见的应用之一：栈定义：一种可以实现“先进后出”的存储结构（类似于箱子）


分类：
静态栈
动态栈：


算法：
出栈
压栈


直接上代码好理解：

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

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

typedef struct Stack
{
        //pTop永远指向顶部，pBottom永远指向底部
        PNODE pTop;
        PNODE pBottom;
}STACK,*PSTACK;

void initStack(PSTACK pS)
{
        //造出一个节点，并且让pTopS指向这个节点
        pS->pTop=(PDONE)malloc(sizeof(NODE));
        if(NULL=pS->pTop)
        {
                printf("动态内存分配失败！");
                exit(-1);
        }
        else
        {
                pS->pButtom=pS->pTop;
                //让指向的这个节点的指针域指向NULL
                pS->pTop->pNext-NULL;
        }
        
}

void push(PSTACK pS,int val)
{
        //先造出一个节点来保存val的值
        PNODE pNew=(PNODE)malloc(sizeof(NDOE));
        //将新的节点的数据域变成val
        pNew->data=val;
        //将新的节点的指针域指向下一个节点（每次压入都是压入栈顶的上方
        pNew->pNext=pS->pTop;
        //将pTop指向新的节点
        pS->pTop=pNew;

}

void traverse(PSTACK pS)
{
        //先定义一个p永远指向栈顶元素
        PNODE p=pS->pTop;
        while(p!=pS->pBottom)
        {
                printf("%d ",p->data);
                p=p->pNext;
        }
        printf("\n");
        return;
}

bool is_empty(PSTACK pS)
{
        if(pS->pTop==pS->pBottom)
                return true;
        else
                return false
}

//把pS所指向的栈出栈一次，并把出栈的元素存入pVal所指向的变量中，如果出栈失败，返回false
bool pop(PSTACK pS,int *pVal)
{
        if(is_empty(pS))  //pS本身存放的就是S的地址
                return false;
        else
        {        
                PNODE r=pS->pTop;
                *pVal=r->data;
                pS->pTop=r->pNext;
                free(r);
                r=NULL;
                return true;
        }

}

void clear(PSTACK pS)  //清空
{
        if(is_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;
        }

}


int main()
{
        int val;
        //相当于我们的S内存中有pTop pBottom两个变量，但是变量里面还没有存放有效的信息
        STACK S;  //STACK等价于struct Stack
        init(&S);  //目的是造出一个空栈
        push(&S,1);   //压栈
        push(&S,2);
        traverse(&S);  //遍历输出

        if(pop(&S,&val))
        {
                printf("出栈成功，出栈的元素是:%d \n",val);
        }
        else
                printf("出栈失败！");

        traverse(&S);  //遍历输出

        clear(&S);
        traverse(&S);  //遍历输出

        return 0;
}

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


线性结构的两种常见的应用之二：队列（先进先出）