栈（Stack）

一、引言

无论是在日常生活中，还是在极端的条件下都需要用到一些数据结构来处理一些复杂的问题，或者说是简化一些问题。基于栈这一数据结构的特殊性，我们在日常使用中很少用到。一提到栈很多人就会不由自主地想到战争。那我们不妨以古代战争中神出鬼没的骑兵管理为例。话说在古代的战争中，几乎每场战争的都会有骑兵来捧场，他们主要以高机动性和快速闻名。在战争的情报收集、运输、调度、追击中骑兵功不可没。那管理者又是如何犒劳这些功臣的呢？我们以“赏善不遗匹夫”来展开讲讲。

二、栈的定义

栈是一种特殊的数据结构，有多特殊呢？在函数的调用中，栈帧的创建与销毁离不开栈这一数据结构。我们为了将战马更好地管理运用栈的数据结构，这样战马就算有少，我们也可以看最后一匹战马的位置来“一眼丁真”。那我们就要建立好栈这一数据结构。那栈具有什么特点呢？栈具有后进先出的特点，意为后面进入的数据会先被删除，与手枪弹夹构造类似，越是后面进入弹夹的子弹就会越先发射出去。

三、栈的实现

栈的实现是比较简单的，希望大家不要抱畏难心里。同理，在统计物品时也可以用到栈“后进先出”的特性统计。

首先就是栈的构造：

因为要删除栈最末尾的元素保证后进先出的特点。至于在栈中创建一个地址则是为了自由申请大小不同的的数组，更加方便管理。同时为了更好取出栈顶元素，我们在结构体中定义一个_top。（下划线来暗示其他看代码的人这是变量，也是与C++中的类与对象接轨）

typedef int STDataType;

typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

任何数据结构的基本功能都只有几个——插入、调整、删除、销毁，也就是所谓的增删查改。增加数据很简单，只需要先判断数组是否满了，满了或者根本就没有的话realloc扩容一下。就像马棚马满为患就扩大马棚。这个应该是比较容易理解的。

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	int NewCapacity = 0;
	STDataType* mid = NULL;

	if (ps->_top + 1 == ps->_capacity)
	{
		NewCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		mid = (STDataType*)realloc(ps->_a,NewCapacity * sizeof(STDataType));
		
		if(mid == NULL)
		{
			assert(mid);
		}
		ps->_a = mid;
		ps->_capacity = NewCapacity;
	}
	ps->_a[++ps->_top] = data;
}

有入就会有出，正所谓养兵千日用兵一时。为了更好管理马棚和节省空间，毕竟古代资源比较短缺。我们假设这些马速度、品质是没有高低贵贱之分的。（达官贵人的马就不论了，达官贵人的马有专门的弼马温进行照料）那我们用这些马时不用考虑到马的条件，直接迁走最后一匹马就是了。那就涉及到栈顶位置取出数据后删除，毕竟马都不在了，还保留它的记录会造成马匹丢失的误会。

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps->_top + 1);

	return ps->_a[ps->_top];
}

那我们为了保证取到马匹（数据）。加上一个断言（assert）判断马棚里是否还有马匹，没有马匹却能取到马，这不是违反常理吗？当_top为-1时就代表无马，毕竟_top为零时也可以取到元素。同理删除数据也需要断言以此来判断马棚里是否还有马。

void StackPop(Stack* ps)
{
	assert(ps->_top + 1);

	ps->_top--;
}

删除数据就更加简单了。只需要将_top--，减少数据个数即可，后面进入的数据也能通过_top的下标访问将之前的数据改掉即可。

那每隔一个工作周期就需要检查马匹情况就需要获取马匹的数量。毕竟马匹会有大大小小的各种情况。

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	return ps->_top + 1;
}

好的，本期分享到这里就结束了，感谢各位的捧场！下期我们聊聊C++中的类和对象。