【数据结构】栈【详解】

目录

栈的定义：

 栈的声明与定义：

头文件的包含： 

对栈的基本操作： 

 栈的初始化：

摧毁栈:

入栈：  ​编辑

出栈：  ​编辑

输出栈顶位置：

输出栈的当前大小： 

判空操作： 

 测试结果：

 最后，完整代码：

---

栈的定义：

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

图解：

• 栈顶Top：线性表允许插入和删除的那一端。
• 栈底Bottom：固定的，不允许进行插入和删除的另一端。
• 由于只能在栈顶进行插入和删除操作，故栈的操作特性是后进先出LIFO（Last In First Out），称为后进先出的线性表。

 栈的声明与定义：

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

 其中a是用来开辟空间的，top,capacity则分别是存储栈顶信息与栈的最大容量 

头文件的包含： 

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

对栈的基本操作： 

//栈的初始化
void StackInit(ST* ps);
//栈的摧毁
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//输出栈顶的当前位置
STDataType StackTop(ST* ps);
//输出栈的容量大小
int StackSize(ST* ps);
//栈的判空
bool StackEmpty(ST* ps);

 栈的初始化：

//栈的初始化
void StackInit(ST* ps)
{assert(ps);//判空操作ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//为栈开创大小为四个STDataType的空间if (ps->a == NULL){printf("malloc fail\n");//如果开创失败就非正常退出程序exit(-1);}ps->capacity = 4;//否则栈的最大容量为当前开创的空间大小ps->top = 0;//栈顶从头开始
}

摧毁栈:

//摧毁栈
void StackDestory(ST* ps)
{assert(ps);//判空操作free(ps->a);ps->a = NULL;//释放ps->a中的内存并使其指向空，防止内存泄漏ps->top = ps->capacity = 0;//同时容量置空，栈置零
}

入栈：  

代码解释： 

//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//满了就增容if (ps->a == ps->capacity){//用tmp暂时存储当前开创的内存STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;//将内存赋予栈ps->capacity *= 2;//同时容量扩大两倍}}ps->a[ps->top] = x;//入栈ps->top++;
}

出栈：  

 代码解释：

//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);//ps->a[ps->top--]=0;ps->top--;
}

输出栈顶位置：

//输出栈顶位置
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}

输出栈的当前大小： 

//输出栈的当前大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

判空操作： 

//判空操作
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

 测试结果：

 

 最后，完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
//栈的初始化
void StackInit(ST* ps)
{assert(ps);//判空操作ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//为栈开创大小为四个STDataType的空间if (ps->a == NULL){printf("malloc fail\n");//如果开创失败就非正常退出程序exit(-1);}ps->capacity = 4;//否则栈的最大容量为当前开创的空间大小ps->top = 0;//栈顶从头开始
}
//摧毁栈
void StackDestory(ST* ps)
{assert(ps);//判空操作free(ps->a);ps->a = NULL;//释放ps->a中的内存并使其指向空，防止内存泄漏ps->top = ps->capacity = 0;//同时容量置空，栈置零
}
//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//满了就增容if (ps->a == ps->capacity){//用tmp暂时存储当前开创的内存STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;//将内存赋予栈ps->capacity *= 2;//同时容量扩大两倍}}ps->a[ps->top] = x;//入栈ps->top++;
}
//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);//ps->a[ps->top--]=0;ps->top--;
}
//输出栈顶位置
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}
//输出栈的当前大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
//判空操作
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
void TestStack()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n");
}
int main()
{TestStack();return 0;
}

博客到这里也是结束了，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~