目录

前言

一、栈的定义

二、栈的分类

三、栈的一些算法 

四、栈的日常应用 

总结

前言

数据结构的学习笔记，记录第七天

---

一、栈的定义

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

           栈类似于箱子

---

二、栈的分类

分类：

        静态栈

        动态栈

---

三、栈的一些算法 

算法：

        栈的初始化

        出栈

        入栈

        清空栈中全部元素

        判断栈是否为空

        遍历栈中元素

（上述算法实现代码如下，附详细注释）

#include 
#include    //里面包含exit函数
#include    //里面包含malloc函数
#include   //里面包含bool函数

typedef struct Node     //定义一个链表的数据类型
{
    int data;           //数据域
    struct Node * pNext;//指针域
}NODE,* PNODE;

typedef struct Stack   //定义一个栈的数据类型
{
    PNODE pTop;         //头指针域
    PNODE pBottom;      //尾指针域
}STACK,* PSTACK;

void initStack();
void pushStack();
void traverseStack();
bool pop();
void clear();

int main()
{
    STACK S;            //STACK 等价于 struct Stack
    int val;            //保存出栈元素

    initStack(&S);        //函数功能：初始化栈
    pushStack(&S,1);        //函数功能：压入元素入栈
    pushStack(&S,2);
    pushStack(&S,3);
    pushStack(&S,4);
    pushStack(&S,5);
    pushStack(&S,6);
    traverseStack(&S);
    //clear(&S);

    if(pop(&S,&val))        //弹出栈元素
    {
        printf("出栈成功，出栈的元素是%dn",val);
    }
    else
    {
        printf("出栈失败！n");
    }
    traverseStack(&S);    //遍历输出栈中元素

    return 0;
}

void initStack(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL == pS->pTop)
    {
        printf("动态内存分配失败！n");
        exit(0);
    }
    else
    {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL;     //pS->Bottom->pNext = NULL;
    }
}

void pushStack(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));

    pNew->data = val;
    pNew->pNext = pS->pTop;            //pS->Top不能改成pS->Bottom
    pS->pTop = pNew;

    return;
}

void traverseStack(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所指向的栈出栈一次，并把在、出栈元素存入pVal形参所指向的变量中，如果出栈成功返回true,出栈失败则返回false
bool pop(PSTACK pS,int* pVal)
{
    if(empty(pS))        //pS本身存放的就是S的地址
    {
        return false;
    }
    else
    {
        PNODE r = pS->pTop;
        pS->pTop = r->pNext;
        *pVal = r->data;
        free(r);
        r = NULL;

        return true;

    }
}

//clear清空栈中所有元素
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;
    }
}

exit()函数

包含在头文件：stdlib.h中

功能：为退出程序的函数

用法：

       exit(1);  为异常退出     只要括号内数字不为0都表示异常退出

       exit(0);  为正常退出

注意：括号内的参数都将返回给操作系统;

          return() 是返回到上一级主调函数，不一定会退出程序; 

---

四、栈的日常应用 

应用：

        函数应用

        中断

        表达式求值

        内存分配

        缓冲处理

        迷宫

---

总结 

日进一寸，继续加油。