定义
一种可以实现“先进后出”的存储结构。
分类
- 静态栈
- 动态栈
算法
- 出栈
- 压栈
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *pNext;
} NODE, *PNODE;
typedef struct Stack
{
PNODE pTop;
PNODE pBottom;
} STACT, *PSTACT; //PSTACT 相当于 struct Stack *
void init(PSTACT);
void push(PSTACT, int);
void traverse(PSTACT);
bool pop(PSTACT, int *);
int main(void)
{
STACT S; //STACT 等价于 struct Stack
init(&S); //造出一个空栈
push(&S, 1); //压栈
push(&S, 2);
traverse(&S); //遍历输出
return 0;
}
void init(PSTACT pS)
{
pS->pTop = (NODE)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(PSTACT pS, int val)
{
PNODE pNew = (NODE)malloc(sizeof(NODE));
pNew->data = val;
pNew->pNext = pS->pTop;
pS->pTop = pNew;
return;
}
//遍历
void traverse(PSTACT pS)
{
PNODE p = pS->pTop;
while (p != pS->pBottom)
{
printf("%d ", p->data);
p = pS->pNext;
}
printf("\n");
return;
}
//判断栈是否为空
bool empty(PSTACT pS)
{
if (pS->pTop == pS->pBottom)
{
return true;
}
else
{
return false;
}
}
//把 pS 所指向的栈出栈一次,并把出栈的元素存入 pVal 形参所指向的变量中.
//出栈失败返回 false,否则返回 true
bool pop(PSTACT pS, int *pVal)
{
if (empty(pS) == true)
{
return false;
}
else
{
PNODE r = pS->pTop;
pS->pTop = r->pNext;
*pVal = r->data;
free(r);
r = NULL;
return true;
}
}
//清空
void clear(PSTACT 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;
}
}
应用
- 函数调用
- 中断
- 表达式求值
- 内存分配
- 缓冲处理
- 迷宫
网友评论