栈
栈的定义
- 一种可以实现“先进后出”的存储结构
栈的分类
- 静态栈：记录最后一个元素位置的数组，本质是数组
- 动态栈：一个头插法的链表，本质是链表
动态栈的实现及细节
栈的实现的算法大意
用头插法实现单链表，去掉单链表的链表中插入删除排序等功能，只保留头部的插入删除即可。在做单链表的同时用另一个节点来指示链表头节点尾节点的位置就可以实现头插法。
算法图示
动态栈的实现
#include <stdio.h>
#include <stilib.h>
#include <stdbool.h>
typedef struct Node{ //栈节点
int data; //数据域
struct Node *pNext; //指针域
} NODE,*PNODE;
typedef struct Stack{ //指示栈的头节点尾节点的辅助节点，用来实现头插法
PNODE pTop;
PNODE pBottom;
} STACK,*PSTACK;
PSTACK InitStack(void);
/* 操作结果：构造一个空栈*/
void DestoryStack(PSTACK pS);
/* 初始条件：栈已经存在
* 操作结果：栈被销毁
*/
void ClearStack(PSTACK pS);
/* 初始条件：栈已经存在
* 操作结果：栈被清空
*/
bool StackEmpty(PSTACK pS);
/* 初始条件：栈已经存在
* 操作结果：若栈为空，返回TURE，否则返回FALSE
*/
void StackLenth(PSTACK pS);
/* 初始条件：栈已经存在
* 操作结果：返回栈的长度
*/
int GetTop(PSTACK pS,int val);
/* 初始条件：栈已经存在且非空
* 操作结果：返回栈顶元素
*/
void Push(PSTACK pS,int val);
/* 初始条件：栈已经存在
* 操作结果：在栈顶添加新的元素
*/
int Pop(PSTACK pS);
/* 初始条件：栈已经存在且非空
* 操作结果：删除栈顶元素并返回被删除的元素值
*/
void StackTraverse(PSTACK pS);
/* 初始条件：栈已经存在且非空
* 操作结果：从栈顶到栈底依次输出每个元素的值
*/
int OutPut(PSTACK pS,int val);
/* 初始条件：栈已经存在且非空
* 操作结果：遍历输出要求的栈内数据
*/
int main()
{
PNODE pS=InitStack();
}
PSTACK InitStack(void) //构造空栈
{
PSTACK pS=(PSTACK)malloc(sizeof(STACK)); //这里不能使用PSTACK pS，因为这样生成的pS是一个局部变量，它的内存离开此函数就会被系统收回
pS->pTop=(PNODE)malloc(sizeof(NODE)); //创建空栈，同样只能使用malloc函数，同时另pTop和pBottom同时指向这个节点，因为此时只有几个节点，既是头也是尾
if(pS->pTop==NULL){
printf("分配空间失败，程序结束");
exit(-1);
}else{
pS->pBottom=pS->pTop;
pS->pBottom->pNext=NULL;
}
return pS;
}
void DestoryStack(PSTACK pS) //销毁栈
{
PNODE p=pS->pTop;
pS->pTop=pS->pTop->pNext;
while(p->pNext!=NULL){
free(p);
p=p->pNext;
}
}
void ClearStack(PSTACK pS) //清空栈
{
PNODE p=pS->pTop;
while(p!=pS->pBottom){
p->data=0;
p=p->pNext;
}
}
bool StackEmpty(PSTACK pS) //判断栈是否为空
{
PNODE p=pS->pTop;
if(p->pNext==NULL){
return true;
}else{
return false;
}
}
int StackLenth(PSTACK pS) //计算栈长度
{
int i=0;
PNODE p=pS->pTop;
while(p!=pS->pBottom){
i++;
p=p->pNext;
}
printf("栈的长度为%d\n",i);
}
int GetTop(PSTACK pS,int val) //返回栈顶元素
{
PNODE p=pS->pTop;
return p->data;
}
void Push(PSTACK pS,int val) //压栈（在栈顶添加元素）
{
PNODE pNew=(PNODE)malloc(sizeof(NODE)); //这里也是只能用malloc
pNew->pNext=pS->pTop;
pNew->data=val;
pS->pTop=pNew;
}
int Pop(PSTACK pS) //删除栈顶元素并返回被删除的元素值
{
PNODE p=pS->pTop;
int t=p->data;
pS->pTop=pS->pTop->pNext; //这里要先将pS->pTop指向p的下一个元素才可以释放p指向的元素，否则pS->pTop无法指向下一个节点
free(p);
return t;
}
void StackTraverse(PSTACK pS) //从栈顶到栈底依次输出每个元素的值
{
PNODE p=pS->pTop;
while(p!=pS->pBottom){
printf("%d ",p->data);
p=p->pNext;
}
printf("here\n");
}
int OutPut(PSTACK pS,int val) //遍历输出要求的栈内数据
{
int i=0,t=0;
PNODE p=pS->pTop;
while(p!=pS->pBottom){
t=p->data;
i++;
if(t=val){
printf("查找元素在第%d位\n",i);
break;
}
p=p->pNext;
}
return t;
}