数据结构——栈

栈的概念：

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端成为栈底。栈的元素遵守后进先出原则

压栈 : 栈的插入操作，入数据在栈顶

出栈 : 栈的删除操作，出数据也在栈顶

模拟栈可以用数组或者双向链表来实现，单链表不好处理前一个节点

如果想用单链表做栈，可以让后面一个节点当栈顶，头插数据或头删数据即可

但是由于双向链表比单链表多一个指针，所需空间更大了，所以一般不适用双向链表

下面我们将用数组来对栈进行模拟

我们依然用结构体来定义栈

栈的定义： typedef struct Stack { STDataType* a; //开辟数组 int top; //指向栈顶或栈顶的后一个位置（据情况而定注意前后对应）,指的是数组的下标 int capacity; //空间中元素的个数 }ST; 初始化栈： //初始化栈 void STInit(ST* pst) { assert(pst); pst->a = NULL; //top 指向栈顶的下一个位置 pst->top = 0; //top 指向栈顶数据的位置 //pst->top = -1; pst->capacity = 0; }

这里我们需要着重强调的是初始化 pst->top 的时候，有两种情况，一个是 top 指向栈顶元素，一个是 top 指向栈顶元素的下一个元素

当 top 指向栈顶元素时，若没有元素存在，top 是 -1 而不是 0，top永远表示数组的下标，若表示 0 则说明有一个元素，不成立，所以 top 初始化为 -1

当 top 指向栈顶元素的下一个元素时，若没有元素存在，则 top 应该指向数组的第一个元素所在位置，也就是 0 ，所以 top 初始化为 0

销毁栈： //销毁栈 void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } 元素入栈： //入栈 void STPush(ST* pst, STDataType x) { assert(pst); //扩容 if (pst->top = pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType)); //判断 tmp 是否开辟成功 if (tmp == NULL) { perror("realloc fail"); return -1; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; }

我们使用顺序表的扩容方法，栈中空间为 0 则开辟 4 个空间，若不为 0 则在原来空间的基础上乘以 2

同时开辟空间我们也不使用 malloc 而是 realloc ，不用考虑是本地扩容还是异地扩容

元素出栈: //出栈 void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; }

注意这里的出栈不是将元素销毁或删除，而是只将栈顶缩小来表示栈的整体大小减少，相当于有元素被舍弃，但没有真正消失

取栈顶数据: //取栈顶数据 STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } 判断栈是否为空: //判空 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } 获取栈中数据的个数: //获取数据的个数 int STSize(ST* pst) { assert(pst); return pst->top; }