栈的学习

[HGUFlyingDog]

栈

栈的定义和特点

• 栈是一种特殊的线性表，只能在表尾（栈顶）去进行插入和删除
• 遵循遵循后进先出的原则

栈的主要操作

• 栈的插入操作，叫作进栈，也称压栈、入栈。
• 栈的删除操作，叫作出栈，也称作弹栈。

进栈出栈变化形式

最先入栈不一定是最先出栈的，比如入栈顺序是1,2,3,

• 第一种：是1、2、3进，再3、2、1出。 出栈顺序是3 2 1
• 第二种：是1进，1出，2进，2出，3进，3出。 出栈顺序是1 2 3
• 第三种：1进，2进，2出，1出，3进，3出。 出栈顺序是 2 1 3
• 第四种：1进，1出，2进，3进，3出，2出。 出栈顺序是1 3 2
• 第五种：1进，2进，2出，3进，3出，1出。 出栈顺序是2 3 1

出栈序列种类数公式为

$$ C(2n,n)(n+1) $$

栈的实现

栈的实现一般通过数组和链表的形式去实现。

通过数组相对于通过链表有优势，因为数组在尾插方面比链表有优势：

• 数组判断空间，空间足够直接插入
• 链表需要先申请空间然后，修改前一个节点的指针来完成

代码部分

//栈的初始化
 StackInit(Stack* ps)
{
	assert(ps);
	//assert 用来防止传参为空指针从而避免导致错误
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

//入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->top == ps->capacity)//满了
	{
		ps->a = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
        //扩容一般是原大小的2倍
		if (ps->a == NULL)
		{
			perror("realloc fail");
		}
	}
	else
	{
		ps->a[ps->top = data];
		ps->top++;
	}
}

//自定义的函数，方便调试代码
void StackPrint(Stack* ps)
{
	for (int i = 0; i<ps->top; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

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

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	printf("有效元素个数为%d\n", ps->top );// 为了方便调试
	return ps->top ;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
	return !(ps->top);
}

//栈的销毁
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}