【数据结构】--- 探索栈和队列的奥秘-???? 栈

对于这么坨书，我们要拿到最下面的书是不是要最后才能拿到；而对于最上面的书它是最晚放上去的却能最先拿到，这样的一个场景就跟我们接下来要介绍的栈类似 — Last in First out(后进先出)

???? 何为栈

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

压栈：栈数据的插入操作叫做压栈/入栈/进栈，入数据在栈顶。
出栈：栈数据的删除操作叫做出栈，出数据也在栈顶。

???? 栈后进先出是相对的

由图中我们可知，栈的后进先出是对于同时在栈里的数据而言的

???? 栈的实现

通过前面的分析我们知道，我们需要一个栈顶来表示数据，这跟我们链表的头结点有点相似，但是对于单链表来说实现栈，尾部插入数据并不方便，因此我们选择数组实现栈

• 动态栈

typedef int Datatype;
typedef struct Stack
{
	Datatype* arr;
	int top;
	int capacity;
}ST;

• 栈的初始化与销毁

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

关于top的初始化：1.top表示栈顶元素的下一个位置时，让top初始化为0，插入数据时先top后++ ；2.top表示栈顶元素 时，top初始化为-1，此时先++后再用top

// 销毁栈 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

• 栈的插入数据和删除数据
  这里有了前面顺序表的基础就很简单了，不过要注意压栈和出栈都是在栈顶

//入栈
void StackPush(ST* ps, Datatype data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{//扩容
		int newcapacity = 0;
		newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype));
		if (temp == NULL)
		{
			perror("malloc failed");
			return;
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
	//入栈
	ps->arr[ps->top++] = data;

}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//栈不能为空
	assert(ps->top != 0);
	ps->top--;
}

• 获取栈顶元素

// 获取栈顶元素 
Datatype StackTop(ST* ps)
{
	assert(ps);
	//栈不能为空
	assert(ps->top != 0);
	return ps->arr[ps->top - 1];
}

• 判断是否为空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0 ? 1 : 0;

}

• 获取栈中有效数据个数

// 获取栈中有效元素个数 
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

---