栈的实现-

栈

栈的概念及结构

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中元素遵循**后进先出 LIFO（Last In First Out）**的原则。

压栈：栈的插入数据操作称为进栈/压栈/入栈。入数据在栈顶。
出栈：栈的输出数据操作称为出栈。出数据也在栈顶。

请添加图片描述
进栈1 2 3 4，出栈可能是1 2 3 4，因为没有出栈要求，可能是刚进栈就出栈。

栈的实现

栈的实现一般可以使用数组或则链表实现，相较而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

若使用数组，则第一个有效元素为栈底，最后一个有效元素为栈顶。
若使用单链表实现栈，则使用表头当栈顶（即链表第一个有效节点）。

注：数组实现栈的话，说得上弊端的也就是扩容，除此之外也没什么不好的地方。对于现在的硬件设备，扩容不是什么大问题。
使用数组或链表都差不多，但数组的缓存命中率高。

代码

Stack.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>//动态栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;STDataType top;STDataType capacity;
} ST;//初始化栈
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//进栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检查是否为空
bool STEmpty(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);

Stack.c

#include "Stack.h"//初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("STInit()::malloc fail");return;}ps->capacity = 4;ps->top = 0;  //top是栈顶元素的下一个位置//ps->top = -1;  //top是栈顶元素位置
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
//进栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("STPush()::realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}
//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//检查是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

Test.c

#include "Stack.h"int main()
{ST st;ST* pst = &st;STInit(pst);STPush(pst, 1);STPush(pst, 2);STPush(pst, 3);STPush(pst, 4);STPush(pst, 5);while (!STEmpty(pst)){//要访问栈底元素，要先将栈顶元素出栈printf("%d ", STTop(pst));STPop(pst);}STDestroy(&st);return 0;
}