前言
本文主要讲述特殊的线性表——栈：
栈是什么，栈的特点
数据结构中有一种特殊的线性表叫栈。
栈有一种特点：
它允许后进入的数据先拿出来。
类似一个弹夹，或是一个装砖头的容器。
栈的基本操作有如上图：
类比一个缸，缸的底端是栈底，顶端是栈顶，放入数据称为入栈，取出数据称为出栈。
对于一个栈，其特点为后进先出
Last In Fist Out
或者
先进后出
Fist Out Last In
所以在实现栈这种特殊的线性表时，当我们拿出数据的时候，只需要取栈顶元素即可，存入数据时，只需往栈顶存放数据。
综合栈的特点，在实现其结构时更适合使用数组 ，而不是链表。
当然使用链表也是可行的，相比而言：
使用链表的缺点有：
1.在压栈时总需要next的指针来维护。
2。出栈时需要记录上一个节点的位置，效率较低。
数组的方式可以解决上述两个问题，且无其他较为严重的缺点。
下面来实现栈的基本功能：
实现栈的基本操作
栈的相关操作声明
void StackInit(ST* ps);//初始化 void StackDestroy(ST* ps); void CheckCapacity(ST** ps);//检查容量 void StackPush(ST* ps,STDataType x);//插入元素 void StackPop(ST* ps);//删除栈顶元素 int StackSize(ST* ps);//计算栈有多少个数据 bool StackEmpty(ST* ps);//判断栈是否为空 STDataType StackTop(ST* ps);//取栈顶元素 注：ps是指向一个结构体的指针，在main函数创建了一个结构体： ST st; 并且传参传的是结构体的地址
1.创建栈
#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;
解读： 定义一个结构体：使用结构体的指针来维护数组栈
top表示栈顶的元素
capacity表示栈的容量大小
2.对栈进行初始化
void StackInit(ST* ps)//初始化 { assert(ps!=NULL); ps->a = NULL; ps->top = ps->capacity = 0; //ps->top可以初始化成-1，此时先++，再赋值 //此时指向的就是栈顶元素 }
3.销毁栈
void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
4.判断栈是否为空
bool StackEmpty(ST* ps)//判断栈是否为空 { assert(ps); return ps->top == 0; }
5.压栈操作
void CheckCapacity(ST**ps)//检查容量 { assert(ps != NULL); if ((*ps)->top == (*ps)->capacity) { STDataType newcapacity = (*ps)->capacity == 0 ? 4 : (*ps)->capacity * 2; STDataType* tmp = (STDataType*)realloc((*ps)->a,(sizeof(STDataType)*newcapacity));//申请的空间是存放STDataType的 //不是用来存放结构体的 //如果第一个参数是一个NULL，realloc的作用就跟malloc一样，所以可以传NULL assert(tmp != NULL); (*ps)->a = tmp;// 把新地址给ps->a (*ps)->capacity = newcapacity; } } void StackPush(ST* ps, STDataType x)//插入元素 { assert(ps); CheckCapacity(&ps);//这里如果传参传的是ps，相当于传值调用，在CheckCapacity函数内部申请的空间就无法返回来了。 ps->a[ps->top] = x; // 先赋值，再++，因为ps->top初始化是0，就是指向栈顶元素的下一个。 ps->top++; }
解读：入栈时首先需要检查栈空间的容量大小，如果栈空间不足则需增容。
在这里分装了一个检查容量的函数。
6.删除栈顶元素
void StackPop(ST* ps)//删除栈顶数据 { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
7.取出栈顶元素
注：第六个函数仅仅删除栈顶元素并未拿到该数据
这里分装函数是更方便的
STDataType StackTop(ST* ps)//取栈顶元素 { assert(ps); assert(!StackEmpty(ps)); //感叹号表达式让语句的逻辑相反 return ps->a[ps->top - 1]; //在这里我初始化top为0，表示指向栈顶元素的下一个位置 //因为初始化为0时，需要先压栈，top值再++，此时就指向了下一个位置了 }
8.计算栈内存放多少个数据
int StackSize(ST* ps)//计算栈有多少个数据 { assert(ps); assert(!StackEmpty(ps)); return ps->top; }
解读：
这里直接返回top，而不是返回top-1
因为我们在初始化的时候是将top置为0，先入栈，top再++
假如入栈三次，那么top此时就是3，但是top指向的位置是入栈的第三个元素的下一个位置。
函数基本功能如下：
总结
掌握了链表的结构之后，实现栈难度是不大的。
