【郝斌数据结构自学笔记】30-34_栈的定义_栈的分类_栈程序演示_栈的日常具体应用

╰半橙微兮° 2022-08-14 04:54 113阅读 0赞

30\_栈的定义

定义

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

栈类似于箱子

分类

算法

应用

31\_栈的分类

分类

静态栈

动态栈

32\_栈可以执行哪些操作

算法

出栈

压栈

\#include<stdio.h>

\#include<malloc.h>

voidf(int k)

int m;

double \*q=(double \*)malloc(200);

intmain(void)

int i=10;

int \*p=(int \*)malloc(100);//静态的或局部变量分配在栈中分配，动态分配在堆中分配

return 0;

33\_栈程序演示

![SouthEast][]![SouthEast 1][]![SouthEast 2][]

\#include<stdio.h>

\#include<malloc.h>

\#include<stdlib.h>

typedefstruct Node

int data;

struct Node \*pNext;

\}NODE,\*PNODE;

typedefstruct Stack

PNODE pTop;

PNODE pBottom;

\}STACK,\*PSTACK;//PSTACK等价于structSTACK\*

voidinit(PSTACK);

voidpush(PSTACK,int);

voidtraverse(PSTACK);

boolpop(PSTACK,int \*);

boolempty(PSTACK);

voidclear(PSTACK);

intmain(void)

STACK S;//STACK等价于structStack

int val;

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

push(&S,1);

push(&S,2);

push(&S,3);

push(&S,4);

push(&S,5);

push(&S,6);

traverse(&S);//目的是便于输出

if(pop(&S,&val))

printf("出栈成功，出栈的元素是%d\\n",val);

else

printf("出栈失败！");

traverse(&S);//目的是便于输出

clear(&S);

traverse(&S);//目的是便于输出

return 0;

voidinit(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;

voidpush(PSTACK pS,int val)

PNODE pNew=(PNODE)malloc(sizeof(NODE));

pNew->data=val;

pNew->pNext=pS->pTop; // pS->pTop不能改成pS->pBottom

pS->pTop=pNew;

voidtraverse(PSTACK pS)

PNODE p=pS->pTop;

while(p!=pS->pBottom)

printf("%d",p->data);

p=p->pNext;

printf("\\n");

return;

boolempty(PSTACK pS)

if(pS->pTop==pS->pBottom)

return true;

else

return false;

//把pS所指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败，返回false，否则返回true

boolpop(PSTACK pS,int \* pVal)

if(empty(pS))//pS本身存放的就是S的地址

return false;

else

PNODE r=pS->pTop;

\*pVal=r->data;

pS->pTop=r->pNext;

free(r); //内存释放，否则容易造成内存泄露

r=NULL;

return true;

//clear清空

voidclear(PSTACK pS)

if(empty(pS))//pS本身存放的就是S的地址

return ;

else

PNODE p=pS->pTop;

PNODE q=NULL;

while(p!=pS->pBottom)

q=p->pNext;

free(p);

p=q;

pS->pTop=pS->pBottom;

![SouthEast 3][]

34\_栈的日常具体应用

应用

函数调用

中断

表达式求值

内存分配

缓冲处理

迷宫

[SouthEast]: https://img-blog.csdn.net/20151122101327911?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20151122101339294?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220731/b680e0cfee4645368b7994a182a6075d.png
[SouthEast 3]: /images/20220731/20e0c8ae04814326804ae88572569a22.png