栈结构的实现

栈的概念与结构

栈：一种特殊的线性表，只允许再固定的一端进行插入和删除元素操作。栈中的数据元素遵循后进先出的原则。

栈的结构：

栈的数据保存再数组中

typedef struct Stack
{
	STDataType* arr;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

栈的初始化：

void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

入栈：

空间足够的情况下直接插入数据

如果栈的容量和栈顶相等，那么扩大栈的容量。

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail! ");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	ps->arr[ps->top++] = x;
}

栈的判空：

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

出栈：

如果栈为空，不能出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}

输出栈的大小：

直接输出size

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

输出栈顶元素：

直接返回栈的数据即可

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}

栈的销毁：

循环出栈，直到栈为空

注意：栈里的数据不能被遍历，也不被随机访问。 

void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
		ps->arr = NULL;
	ps->top = ps->capacity = 0;
}