参考博客： 浅然的专栏 https://blog.****.net/w_linux/article/details/78219290

 参考百度百科：https://baike.baidu.com/item/%E6%A0%88/12808149?fr=aladdin

一.栈和栈相关术语的定义 

 栈（Stack）（堆栈）是一种操作受限的线性表，只能在表的一端（表头）进行操作。允许操作的的一端称为栈顶（Top），不允许操作的另一端称之为栈底（Bottom）。

空栈是指栈中没有包含任何的数据元素。栈非空时，处于栈顶位置的数据元素称之为栈顶元素。

向一个栈里插入一个新的元素的操作称之为入栈（Push），插入的元素称为新的栈顶元素。

向一个栈里删除一个元素的操作称之为出栈或退栈（Pop），出栈只能删除当前栈顶的元素。

由于栈的操作和删除只能在栈顶进行，最先入栈的元素必定最后出栈，最后入栈的元素必定最先出栈，因此栈又被叫做后进先出线性表。

二.栈的分类

顺序栈：顺序栈就是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素

链栈：链栈就是采用链式存储结构实现的栈，是受限的单链表，只能在单链表表头操作。

三.顺序栈的表示和实现

1.在一开始需要定义2个常量

 2个常量的作用是为了栈满时扩充栈的容量。

#define INIT_SIZE 20 //栈的初始大小
#define INCREMENT 10 //内存不够时申请的增量

2.顺序栈的结构体定义

 顺序栈的结构体，定义了2个地址变量，base是指的栈底的内存地址，top是指的栈顶的内存地址。而*base，*top则表示地址内存的数据。

typedef struct
{
ElemType* base;//声明栈底的内存地址
ElemType* top;//声明栈顶的内存地址
int StackSize;//栈的大小

}SqStack;

3.顺序栈的初始化

 初始化一个栈，首先是申请内存空间，先申请一块内存，用来存放栈，然后申请一块内存，用来存放栈的数据内容。

SqStack * Init_Stack()
{
    SqStack *s=(SqStack*)malloc(sizeof(SqStack));//为栈提供内存
    s->base = (ElemType*)malloc(sizeof(ElemType)*INIT_SIZE);//为栈的内容提供内存
    if (!s&&s->base)return;
    s->top = s->base;//栈顶=栈底  
    s->StackSize = INIT_SIZE;
    return s;
}

 

4.检查空栈

 当栈顶的地址和栈底的地址相等时，表示没有任何数据存放，为空栈。

int Empty_Stack(SqStack *s)//判断空栈
{
    if (s->top == s->base)
    {
        return 1;
    }
    return 0;
}

 

5.入栈操作

 入栈首先需要判断是否栈满，使用realloc函数给s->base扩充内存空间,刷新栈顶指针，同时更新栈的大小。

如果没有栈满，则存放数据放到那个地址空间。同时栈顶指针向下个地址移动。

void Push(SqStack *s,ElemType data)//入栈
{
    if (!s->base&&s)return;
    if (s->top - s->base >= INIT_SIZE)
    {
        s->base = (ElemType*)realloc(s->base, s->StackSize + sizeof(ElemType)*INCREMENT);//分配增量的空间给栈
        if (!s->base)return;
        s->top = s->base + s->StackSize;//重新设置栈顶指针
        s->StackSize += INCREMENT;
    }
    *(s->top) = data;//为栈顶指针指向的地址赋值
    s->top++;//栈顶指针指向下个地址
}

 

6.出栈操作

 出栈首先判断栈空，如果需要知道出栈的元素的话，可以提前存在变量里。主要操作还是栈顶指针移向上一个地址。

ElemType Pop(SqStack *s)//出栈
{
if (Empty_Stack(s))return;
ElemType data = *(s->top - 1);//将出栈的元素记录下来
(s->top)--;//栈顶的位置-1
return data;//返回出栈的元素
}