线性结构的常见应用之一 栈
一, 定义
一种可以实现"先进后出"的存储结构(存储方式)
只能在一端入和出
二, 分类
如图 06-静态栈-动态栈.jpg
1, 静态栈
底层 以 静态数组 实现
2, 动态栈
底层 以 链表 实现
三, 算法
1, 节点 Node, 栈 Stack
// 结点
typedef struct Node
{
int data;
struct Node * pNext;
} NODE, * PNODE;
// 栈
typedef struct Stack
{
PNODE pTop; // 栈顶
PNODE pBottom; // 栈底
} STACK, * PSTACK;
2, 初始化 栈, 即造出空栈
void initStack(PSTACK pStack)
{
// "头结点"
pStack->pBottom = (PNODE) malloc( sizeof(NODE) );
checkMemoryAllocat(pStack->pBottom);
pStack->pBottom->pNext = NULL; // "头结点"指针域与空
// 栈底指针 和 栈顶指针 都指向 "头结点"
pStack->pTop = pStack->pBottom;
return;
}
3, 压栈
// 压栈
void push(PSTACK pStack, int value)
{
// 新结点
PNODE pNew = (PNODE) malloc( sizeof(NODE) );
checkMemoryAllocat(pNew);
pNew->data = value;
pNew->pNext = pStack->pTop; // 新结点的指针域 指向 栈顶
pStack->pTop = pNew; // 栈顶 上移, 指向 新结点
return;
}
4, 弹栈, 出栈失败(空栈), pValue保存出栈的数据
// 弹栈
bool pop(PSTACK pStack, int * pValue)
{
if ( isEmpty(pStack) )
{
return false;
}
PNODE pTemp = pStack->pTop; // 指向要删除的结点
*pValue = pTemp->data; // 记录删除结点的数据域
pStack->pTop = pTemp->pNext; // 栈顶指针 下移
free(pTemp); // 释放删除的结点
pTemp = NULL;
return true;
}
5, 遍历
// 遍历
void traverse(PSTACK pStack)
{
printf("遍历-由顶到底:\n");
PNODE p = pStack->pTop;
for (; p != pStack->pBottom; p = p->pNext)
{
printf("%3d\n", p->data);
}
return;
}
6, 检查动态内存是否分配失败, 是则终止
void checkMemoryAllocat(PNODE pNode)
{
if (NULL == pNode)
{
printf("动态内存分配失败,结束程序!");
exit(-1);
}
}
7, 栈是否为空
// 栈是否为空
bool isEmpty(PSTACK pStack)
{
if (pStack->pTop == pStack->pBottom)
{
return true;
}
return false;
}
8, 清空, 删除所有有效数据
// 清空, 删除所有有效数据, 先下移栈顶, 后释放
void clear(PSTACK pStack)
{
PNODE pTemp = pStack->pTop; // 用于指向要释放的 结点
// 释放所有 有效结点
while (pStack->pTop != pStack->pBottom)
{
pTemp = pStack->pTop;
pStack->pTop = pTemp->pNext; // 栈顶下移
// 释放 刚才出栈的结点的内存
free(pTemp);
pTemp = NULL;
}
return;
}
9, 完整代码
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>
// 结点
typedef struct Node
{
int data;
struct Node * pNext;
} NODE, * PNODE;
// 栈
typedef struct Stack
{
PNODE pTop; // 栈顶
PNODE pBottom; // 栈底
} STACK, * PSTACK;
// 初始化 栈, 即造出空栈
void initStack(PSTACK pStack);
// 压栈
void push(PSTACK pStack, int value);
// 弹栈, 出栈失败(空栈), pValue保存出栈的数据
bool pop(PSTACK pStack, int * pValue);
// 遍历
void traverse(PSTACK pStack);
// 检查动态内存是否分配失败, 是则终止
void checkMemoryAllocat(PNODE pNode);
// 栈是否为空
bool isEmpty(PSTACK pStack);
// 清空, 删除所有有效数据
void clear(PSTACK pStack);
int main(void)
{
STACK stack;
// 初始化 栈
initStack( &stack );
// 压栈
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
push(&stack, 4);
// 遍历
traverse(&stack);
// 弹栈
int value;
int i, count;
printf("请输入要出栈的元素个数 : ");
scanf("%d", &count);
for (i = 0; i < count; ++i)
{
if (pop(&stack, &value))
{
printf("出栈: %3d\n", value);
continue;
}
printf("已到栈底, 出栈失败!!!\n");
}
// 遍历
traverse(&stack);
// 清空
clear(&stack);
traverse(&stack);
return 0;
}
void initStack(PSTACK pStack)
{
// "头结点"
pStack->pBottom = (PNODE) malloc( sizeof(NODE) );
checkMemoryAllocat(pStack->pBottom);
pStack->pBottom->pNext = NULL; // "头结点"指针域与空
// 栈底指针 和 栈顶指针 都指向 "头结点"
pStack->pTop = pStack->pBottom;
return;
}
// 压栈
void push(PSTACK pStack, int value)
{
// 新结点
PNODE pNew = (PNODE) malloc( sizeof(NODE) );
checkMemoryAllocat(pNew);
pNew->data = value;
pNew->pNext = pStack->pTop; // 新结点的指针域 指向 栈顶
pStack->pTop = pNew; // 栈顶 上移, 指向 新结点
return;
}
// 遍历
void traverse(PSTACK pStack)
{
printf("遍历-由顶到底:\n");
PNODE p = pStack->pTop;
for (; p != pStack->pBottom; p = p->pNext)
{
printf("%3d\n", p->data);
}
return;
}
// 弹栈
bool pop(PSTACK pStack, int * pValue)
{
if ( isEmpty(pStack) )
{
return false;
}
PNODE pTemp = pStack->pTop; // 指向要删除的结点
*pValue = pTemp->data; // 记录删除结点的数据域
pStack->pTop = pTemp->pNext; // 栈顶指针 下移
free(pTemp); // 释放删除的结点
pTemp = NULL;
return true;
}
void checkMemoryAllocat(PNODE pNode)
{
if (NULL == pNode)
{
printf("动态内存分配失败,结束程序!");
exit(-1);
}
}
// 栈是否为空
bool isEmpty(PSTACK pStack)
{
if (pStack->pTop == pStack->pBottom)
{
return true;
}
return false;
}
// 清空, 删除所有有效数据, 先下移栈顶, 后释放
void clear(PSTACK pStack)
{
PNODE pTemp = pStack->pTop; // 用于指向要释放的 结点
// 释放所有 有效结点
while (pStack->pTop != pStack->pBottom)
{
pTemp = pStack->pTop;
pStack->pTop = pTemp->pNext; // 栈顶下移
// 释放 刚才出栈的结点的内存
free(pTemp);
pTemp = NULL;
}
return;
}
四, 应用
1, 函数调用
2, 中断
3, 表达式求值(操作数栈, 操作符栈)
4, 内存分配
5, 缓冲处理
6, 迷宫