程序都已经成功通过编译，运行无异常，如果你发现bug，请评论区留言，我们相互交流下经验。
定义：
栈是只能在一端进行数据的插入与删除的线性表。也可以理解为一种“先进后出”的存储结构。
按照内存生成的方式不同分为：
静态栈 动态栈
栈的几个概念：
- 允许进行插入、删除操作的一端称为栈顶。
- 表的另一端称为栈底。
- 当栈中没有数据元素时，称为空栈。
- 栈的插入操作通常称为进栈或入栈。
- 栈的删除操作通常称为退栈或出栈。
静态栈的代码如下：
1.静态栈 不用malloc函数
/*
生成的内存为连续内存
静态栈，当栈生成以后，长度已经定了 也就是一个数组，和一个栈顶元素(保存了，最后一个有效元素的位置)
这种程序结构并不推荐
top保存的为最后一个有效元素的地址
*/
# include <stdio.h>
# define Maxsize 10
/*
定义一个结构体变量
结构体变量有两部分1.是地址连续的数组内容 2.保存了最后那个元素的有效地址编号
*/
typedef struct Student
{
int data[Maxsize];
int top; //top始终为当前元素的位置
}SqStack;
//函数申明
bool TravalList(SqStack * s);
int PopStack(SqStack * s,int &val);
bool PushStack(SqStack * s,int val);
void InitStack(SqStack * s);
int main()
{
int val;
SqStack sq; //当这条语句写下以后，栈已经生成 内存已进行分配 在主函数main中进行
//生成一个结构体变量，操作系统并为之分配相应的内存，创建了一个数组+top的结构体，不用使用动态内存分配的malloc函数分配相应的内存
sq.top=-1; //设置栈顶元素为-1
PushStack(&sq,1); //压栈
PushStack(&sq,2);
PushStack(&sq,3);
PushStack(&sq,4);
PushStack(&sq,5);
PushStack(&sq,6); //压栈
PushStack(&sq,7);
PushStack(&sq,8);
PushStack(&sq,9);
PushStack(&sq,10);
PushStack(&sq,11);
TravalList(&sq);
PopStack(&sq,val);
printf("val = %d\n",val);
}
bool PushStack(SqStack * s,int val)
{
if(s->top == Maxsize-1)
{
printf("栈满\n");
return false;
}
else
{
s->top++;
s->data[s->top]=val;
return true;
}
}
int PopStack(SqStack * s,int &val)//弹栈 出栈
{
if(s->top == -1)
{
printf("栈空\n");
return 0;
}
else
{
val = s->data[s->top];
s->top--;
return val;
}
}
bool TravalList(SqStack * s)//遍历
{
int i;
if(s->top == -1)
{
printf("空栈\n");
return false;
}
else
{
for(i=0;i<=s->top;i++)
{
printf("%d ",s->data[i]);
}
printf("\n");
return true;
}
}
重点：
上面的函数，在主函数中生成的栈，栈的长度已经固定 内存不是用动态分配函数进行分配，而是由主函数自动分配相应的内存。
2.静态栈 用malloc动态分配静态栈的地址程序：
/*
用malloc生成的栈程序
数组栈
内存虽然用malloc动态生成，但是生成的内存大小固定，并不能进行扩展，程序较为死板
*/
# include <stdio.h>
# include <malloc.h>
# define Maxsize 10
typedef struct Student
{
int data[Maxsize];
int top; //top始终为当前元素的位置
} SqStack;
bool TravalList(SqStack * &s);
int PopStack(SqStack * &s,int &val);
bool PushStack(SqStack * &s,int val);
void InitStack(SqStack * &s);
void DestroyStack(SqStack *&s);
bool GetTop(SqStack *s, int &e);
bool StackEmpty(SqStack *s);
int main()
{
int val;
/*
SqStack sq; //当这条语句写下以后，栈已经生成
//生成一个结构体变量，操作系统并为之分配相应的内存，创建了一个数组+top的结构体，不用使用动态内存分配的malloc函数分配相应的内存
SqStack *Sq = &sq; //函数引用时候应该进行的操作，必须进行这样的操作
上面程序虽然也能测试成功，但是会造成内存的二次分配造成内存很大的浪费，所以并不采用上面的程序生成数据
严格来说有很大的bug
*/
SqStack * Sq;//该条程序完全避免了上面的尴尬 该程序只定义了一个指针变量sq，虽然也进行内存的分配，但是只是给指针分配内存 (不论指向什么数据类型都是四个字节) sq指向的数据类型为SqStack
//该条程序也可以理解为定义一个头指针
InitStack(Sq);// 将头指针指向头结点 头结点并不进行数据的赋值，指针的指向
PushStack(Sq,1); //压栈
PushStack(Sq,2);
TravalList(Sq);
PopStack(Sq,val);
printf("val = %d\n",val);
DestroyStack(Sq);
TravalList(Sq);
//printf("%d\n",StackEmpty(Sq));
}
/*
申请一块内存，供其使用 初始化栈内存 s指向一个一个结构体的首地址，并将s->top指向-1
*/
void InitStack(SqStack * &s)
{
s = (SqStack *)malloc(sizeof(SqStack));
s->top = -1;
}
/*
进栈
*/
bool PushStack(SqStack * &s,int val)
{
if(s->top == Maxsize-1)
{
printf("栈满\n");
return false;
}
else
{
s->top++;
s->data[s->top]=val;
return true;
}
}
/*
出栈
*/
int PopStack(SqStack * &s,int &val)
{
if(s->top == -1)
{
printf("栈空\n");
return 0;
}
else
{
val = s->data[s->top];
s->top--;
return val;
}
}
/*
遍历栈内的所有元素
*/
bool TravalList(SqStack * &s)
{
int i;
if(s->top == -1)
{
printf("空栈\n");
return false;
}
else
{
for(i=0;i<=s->top;i++)
{
printf("%d->",s->data[i]);
}
printf("NULL\n");
return true;
}
}
/*
销毁栈元素，将申请的内存释放
*/
void DestroyStack(SqStack *&s)
{
free(s);
}
/*
判断栈是否为空栈，返回值为bool值
*/
bool StackEmpty(SqStack *s)
{
return(s->top==-1);
}
/*
取栈顶元素，返回值为bool，但是可以通过函数参数，进行相应的调用输出
*/
bool GetTop(SqStack *s, int &e)
{
if (s->top == -1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
return true;
}
程序的标注解释较为清晰，不做过多解释。
动态栈：
特点：
定义了一个指向栈首成员和指向栈尾成员变量的结构体
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
/*
定义一个结构体变量，数据域 指针域
可以看做一个自下向上生成的栈 栈顶在最上面 由top指向 在栈顶那进行进栈出栈
*/
typedef struct Student
{
int data;
struct Student * next;
}Node, * pNode;
/*
定义一个结构体，有两个指针 分别指向 栈首 栈尾
*/
typedef struct stack
{
pNode top;
pNode bottom;
}Stack;
void ClearStack(Stack * s);
void TravelStack(Stack * s);
bool PopStack(Stack * s,int &val);
void InitStack(Stack * q);
void PushStack(Stack * s, int val);
int main(void)
{
Stack st;//该程序写下的用时，为st分配相应的内存 创建了一个结构体类型为Stack的结构体变量
int val ;
InitStack(&st);
PushStack(&st,1);
PushStack(&st,2);
PushStack(&st,3);
PushStack(&st,4);
PushStack(&st,5);
TravelStack(&st);
PopStack(&st,val);
printf("val = %d\n",val);
TravelStack(&st);
ClearStack(&st);
TravelStack(&st);
return 0;
}
//初始化栈 栈头指针 栈尾指针分别指向 生成的一块内存 并且 内存的指针域设置为空UNLL 即不指向
void InitStack(Stack * q) // q为创建的Stack结构体变量(主函数创建并分配内存)
{
q->top = (pNode)malloc(sizeof(Node)); //创建头结点 不保存数据 只为操作方便
//为头结点分配相应的内存 并且q结构体变量的top成员(类型为Node * 指向Node类型的指针)变量指向该Node结构体变量
if(q == NULL)
{
printf("内存分配失败\n");
exit(-1);
}
else
{
q->bottom = q->top;//栈首栈尾指针分别指向相应的头结点
q->top->next = NULL;
printf("创建栈成功\n");
}
}
// 压栈 生成一块新的结构体内存 该内存的指针域 指向上一块内存节点 数据域置为val 开始存储数据 并且指针的结构体的栈首指针指向新生成的地址
void PushStack(Stack * s, int val)
{
pNode pNew = (pNode)malloc(sizeof(Node));//生成一块内存 类型为pNode类型 并让pNew指向该内存
//分配一个Node类型大小的内存空间, 并把它赋给Node* 型的变量:pNew
pNew->data = val;
pNew->next = s->top; //将s结构体变量的成员变量top指向的地址(也就是上一个节点的地址)赋值给新生成节点的指针域，即让新生成的节点指向上一个节点
s->top = pNew; //s结构体的top成员变量，指向栈顶元素
}
// 出栈 释放空间
bool PopStack(Stack * s,int &val)
{
if(s->top == s->bottom)
{
printf("空栈\n");
return false;
}
else
{
/*
val = s->top->data;
free(s->top);
s->top = s->top->next;
return true;
*/
pNode r = s->top;//新生成类型为pNode类型的指针 该指针指向栈顶指针指向的节点 二者指向相同的节点
val = r->data; //数据
s->top = r->next; //栈顶元素的下一个元素
free(r);
r = NULL;
return true;
}
}
// 遍历数据
void TravelStack(Stack * s)
{
if(s->top == s->bottom)
{
printf("栈顶指针 等于 栈底指针 空栈\n");
return ;
}
else
{
pNode p;//对栈创建一个节点指针 指针指向栈顶元素
p = s->top; //s->top 即为栈顶结构体的地址 s->top->data 即为栈顶指针的成员变量data 相当于(*p).data p保存栈顶指针的地址 *p即 栈顶结构体
while(p != s->bottom) //当p也就是栈顶指针不为栈底指针的时候 输出data成员 栈底不保存成员data元素 头结点
{
printf("%d->",p->data);
p=p->next;
}
printf("NULL\n");
return ;
}
}
//清空链栈 但栈的头结点仍然存在
void ClearStack(Stack * s)
{
if(s->top == s->bottom)
{
printf("已空栈\n");
}
else
{
pNode p = s->top;
pNode q = NULL;
while(p != s->bottom)
{
q = p->next;
free(p);
p = q;
}
s->top = s->bottom;
}
}
特点：
巧妙采用头插法以及头指针和头结点进行操作的栈
/*
该函数采用头插法进行压栈退栈
创建了一个头指针(主函数中创建) 头结点(InitStack函数中创建)，头指针指向头结点 只为操作方便s->next即为下一个节点，也就是栈顶
*/
# include <stdio.h>
# include <malloc.h>
# define ElemType int
typedef struct linknode
{ ElemType data; //数据域
struct linknode *next; //指针域
}LinkStNode;
void TravelStack(LinkStNode *&s);
void DestroyStack(LinkStNode *&s);
void InitStack(LinkStNode *&s);
bool StackEmpty(LinkStNode *s);
void Push(LinkStNode *&s,ElemType e);
bool Pop(LinkStNode *&s,ElemType &e);
bool GetTop(LinkStNode *s,ElemType &e);
int main(void)
{
int e = 0;
/*
LinkStNode s,*p;
p = &s;
*/
LinkStNode *p;//创建一个指针变量 指向的结构体类型为LinkStNode 也就是链表创建头指针 此时并未指向内容
InitStack(p); //创建一个头结点 头指针p指向头结点 头结点指针域数据域都为NULL
TravelStack(p); //遍历
Push(p,1);
Push(p,2);
Push(p,3);
Push(p,4); //压栈
TravelStack(p);//遍历
GetTop(p,e); //取栈顶元素
printf("e = %d\n",e);
Pop(p,e);//出栈
TravelStack(p);
printf("e = %d\n",e);
DestroyStack(p);//销毁
printf("%d\n",StackEmpty(p));
}
//初始化 链栈 创建一个头结点 头结点不存储数据 只起到数据操作的作用
//创建的内存类型为 结构体的形式 初始化
void InitStack(LinkStNode *&s)
{
s = (LinkStNode *)malloc(sizeof(LinkStNode));//创建一个头结点 头结点内容和指针域都为NULL
s->next = NULL;
s->data = NULL;
}
//判断是否为空，也就是
bool StackEmpty(LinkStNode *s)
{
return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{
LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));
p->data=e; //新建元素e对应的结点*p
p->next=s->next; //插入*p结点作为开始结点 头插法
s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{
LinkStNode *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始结点 此时p和s->next同时指向下一个也就是第一个节点(首节点即为栈顶 在该处进行压栈出栈操作)
e=p->data;
s->next=p->next; //删除*p结点p->next相当于s->next->next 即为首节点的的下一个节点
free(p); //释放*p结点 p和 s->next同时指向栈顶元素 free(p)也就是free(首节点) p为指针变量，并不被free free释放的为内存 也就是结构体LiskStNode的地址
return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{
if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}
void DestroyStack(LinkStNode *&s)
{
LinkStNode *p = s,*q=s->next;
while(q!=NULL)
{
free(p);
p=q;
q=q->next;
}
free(p);
}
void TravelStack(LinkStNode *&s)
{
LinkStNode *p=s->next;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("NULL\n");
}
