栈知识总结
线性结构的两种常见的应用之一：栈定义：一种可以实现“先进后出”的存储结构（类似于箱子）分类：
静态栈
动态栈：
算法：
出栈
压栈
直接上代码好理解：
#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;
}
应用：
函数调用
中断
表达式求值
内存分配
缓冲处理
迷宫
线性结构的两种常见的应用之二：队列（先进先出）
页:
[1]