数据结构——栈

栈是一种特殊的线性表，他只允许在固定的一端进行数据的插入删除，我们把固定的一端叫做栈顶，另一端叫做栈底， 压栈：在栈顶插入数据，
出栈：删除栈顶的数据，遵循后进先出的原则

可以看出栈只是用来存储数据的线性表（容器），那么我们之前学习过的两种线性表：顺序表和链表就都可以来做栈
只不过栈只可以在栈顶插入删除数据

可以看出，用顺序表来做栈是相对较方便的
现在我们就用顺序表来实现栈

1、创建一个结构体，里面包括了开辟顺序表的指针，顺序表的有效原数记录变量，顺序表容量记录变量

然后初始化顺序表


2、压栈

void STPush(ST* ps,SltDatatype x)//入栈
{
	assert(ps);
	
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//因为初始化是capacity是0，所有这里需要，如果capacity是0的话，*2也是0,所有要在这里先给他一个值4
		//扩容
		SltDatatype * tmp= (SltDatatype*)realloc(ps->a, sizeof(SltDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps -> a = tmp;
		ps->capacity = newcapacity;

	}
	ps->a[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、出栈（尾删）

void STPop(ST* ps)//出栈
{
	assert(ps);
	assert(ps->top>0);//空
	ps->top--;

}

1
2
3
4
5
6
7
8

获取栈顶元素

SltDatatype STTop(ST* ps)//获取栈顶原数
{

	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
1
2
3
4
5
6
7
8
9

栈元素的访问，因为栈是后进先出，所以在访问（打印）栈元素的时候不能直接通过遍历数组来打印，应该是从栈顶拿一个元素打印一个元素

while (s.top > 0)
	{
		printf("%d",s.a[s.top - 1]);
		STPop(ps);//出栈

	}

1
2
3
4
5
6
7

栈的释放

void STDestroy(ST* ps)//释放
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
1
2
3
4
5
6
7
8