美国做旅游网站企业网站建设门户
目录
1.栈
1.1栈的概念及结构
2.栈的实现
3.栈结构对数据的处理方式
3.1对栈进行初始化
3.2 从栈顶添加元素
3.3 打印栈元素
3.4移除栈顶元素
3.5获取栈顶元素
3.6获取栈中的有效个数
3.7 判断链表是否为空
3.9 销毁栈空间
4.结语及整个源码
1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈中的数据后面进的先出，也就是说不能够任意访问，添加和删除数据只能在栈顶进行操作。
入栈过程图解：
出栈过程图解：
2.栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小.不用去修改指针
使用数组实现图解：
使用链表实现图解：
实现栈最好的方式就是使用数组的方式来实现：
静态数组定义栈的方式：
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;但是由于空间指定的问题，实际使用较小，所以最适合栈的实现方式就是：动态数组定义栈
动态数组定义栈的方式：
typedef int STDataType;//直接定义动态版本的栈 栈顶表示就是要插入
typedef struct Stack
{STDataType* arr;//定义指向栈空间的指针int top;//栈顶int capcity;//定义容量}Stack;
3.栈结构对数据的处理方式
3.1对栈进行初始化
首先用户创建一个栈变量过后，我们就要将这个栈首先初始化，方便后续用栈来管理数据。
在初始化动作中，指向栈空间的指针应该置空，后续开辟空间的时候再给定值。容量最初也是0，无可争议。但是对于栈顶的定义要注意初始值的区别。
top栈顶后续会用于访问栈顶元素也就是作为我们数组的下标，如果初始为1，此时栈里面是没有元素的，那么后续进入数据就要注意，栈的大小是top的大小。如果开始为0，栈的大小是top+1.当然这里大家自己实现的时候自由选择定义就好：
void SInit(Stack* pc)
{pc->arr = NULL;pc->capcity = 0;pc->top = 0;
}3.2 从栈顶添加元素
首先：先断言一下我们传入的结构体指针，看是否存在这样一个栈结构，再开始后续操作。
第二：添加元素前我们就要考虑我们这个栈的空间还够不够，不够就要进行扩容。这里由于开始的时候，指向栈空间的指针为空，所以realloc函数会直接开辟空间，所以就没有malloc单独申请空间了。
第三：将对应的容量增加，top增加，将我们每个值赋值。
void StackPush(Stack* pc, STDataType data)
{assert(pc);if (pc->top ==pc->capcity){STDataType* a = (STDataType*)realloc(pc->arr, (pc->capcity+2)*sizeof(STDataType) );if (a == NULL){perror("realloc");}pc->arr = a;pc->capcity+=2;}pc->arr[pc->top] = data;pc->top++;}3.3 打印栈元素
使用遍历的方法打印栈空间中的每一个元素。
void StackPrint(Stack* pc){assert(pc);int i = 0;for (i = 0; i < pc->top; i++){printf("%d ", pc->arr[i]);}
}我们来测试一下刚才的入栈：
3.4移除栈顶元素
也就是顺序表中的尾部删除
首先还是要断言一下传入的指针是否为空
第二，我们移除尾部元素，并不是把尾部元素置空，只是将top--,那么就访问不到那个元素，后续增加元素就会覆盖，容量也没有必要减去了。其次，每次top--,那么就要判断一下top减为或者已经小于0了就不执行了。
void StackPop(Stack* pc)
{assert(pc);assert(pc->top > 0);//top减为0了就别在减去了pc->top--;
}
3.5获取栈顶元素
获取栈顶元素，就是通过top作为下标来访问我们的尾部元素，注意如果top初始值为0，那么直接使用我们的top作为下标即可，但是由于我们每次添加元素后都要++,所以要-1，如果是以1为top的初始值，那么此时的top需要-2.
STDataType StackTop(Stack* pc)
{assert(pc);return pc->arr[pc->top-1];
}
3.6获取栈中的有效个数
也就是我们top
int StackSize(Stack* pc)
{assert(pc);return pc->top;
}.
3.7 判断链表是否为空
我们可以判断此时的容量是否为空，因为就是top为0，但是栈依旧存在，只是无法访问每个元素。
bool StackEmpty(Stack* pc)
{assert(pc);return pc->capcity == 0;
}3.9 销毁栈空间
我们的空间是在堆区上申请来的，用完记得销毁还给操作系统，不让后续造成内存泄漏。
void StackDestory(Stack* pc)
{assert(pc);free(pc->arr);pc->arr == NULL;pc->top = pc->capcity = 0;
}4.结语及整个源码
以上就是本期的所有内容，知识含量蛮多，大家可以配合解释和原码运行理解。创作不易，大家如果觉得还可以的话，欢迎大家三连，有问题的地方欢迎大家指正，一起交流学习，一起成长，我是Nicn，正在c++方向前行的奋斗者，数据结构内容持续更新中，感谢大家的关注与喜欢。
附上源码：
test.c
#include"stack.h"
int main()
{//创建栈Stack stack = { 0 };//初始化栈SInit(&stack);StackPush(&stack, 1);StackPush(&stack, 2);StackPush(&stack, 3);StackPush(&stack, 4);StackPrint(&stack);printf("\n");StackPop(&stack);StackPrint(&stack);printf("\n");/*printf("%d ", StackTop(&stack));*/printf("%d ", StackSize(&stack));return 0;
}
stack.c
#include"stack.h"void SInit(Stack* pc)
{pc->arr = NULL;pc->capcity = 0;pc->top = 0;
}void StackPush(Stack* pc, STDataType data)
{assert(pc);if (pc->top ==pc->capcity){STDataType* a = (STDataType*)realloc(pc->arr, (pc->capcity+2)*sizeof(STDataType) );if (a == NULL){perror("realloc");}pc->arr = a;pc->capcity+=2;}pc->arr[pc->top] = data;pc->top++;}void StackPrint(Stack* pc){assert(pc);int i = 0;for (i = 0; i < pc->top; i++){printf("%d ", pc->arr[i]);}
}void StackPop(Stack* pc)
{assert(pc);assert(pc->top > 0);//top减为0了就别在减去了pc->top--;
}STDataType StackTop(Stack* pc)
{assert(pc);return pc->arr[pc->top-1];
}
bool StackEmpty(Stack* pc)
{assert(pc);return pc->capcity == 0;
}int StackSize(Stack* pc)
{assert(pc);return pc->top;
}void StackDestory(Stack* pc)
{assert(pc);free(pc->arr);pc->arr == NULL;pc->top = pc->capcity = 0;
}stack.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;//直接定义动态版本的栈 栈顶表示就是要插入
typedef struct Stack
{STDataType* arr;//定义指向栈空间的指针int top;//栈顶int capcity;//定义容量}Stack;void SInit(Stack* pc);
//入栈
void StackPush(Stack* pc, STDataType data);
//出栈
void StackPop(Stack* pc);
//获取栈顶元素
STDataType StackTop(Stack* pc);
//检查栈是否为空
bool StackEmpty(Stack* pc);
//栈的大小
int StackSize(Stack* pc);
//打印
void StackPrint(Stack* pc);
//销毁栈
void StackDestory(Stack* pc);