栈的实现-c语言实现

用c语言实现栈，谢谢大家支持！

1. 栈的结构

typedef int StackDataType;

typedef struct Stack
{
	StackDataType* a; //数组
	int capacity; //容量
	int top; //栈顶
}Stack;
1
2
3
4
5
6
7
8

为什么需要容量？

和顺序表很相似，在压栈的时候需要realloc开辟空间，realloc开辟空间需要知道对应的开辟多少字节的空间

2. 初始化

void StackInit(Stack* stack)
{
	assert(stack);

	stack->a = NULL;
	stack->capacity = 0;
	stack->top = -1;

}	
1
2
3
4
5
6
7
8
9

为什么需要初始化？

如果不初始化，结构体中top,capacity都是随机值，a是野指针，而我们的目的是让top=-1，并且初始容量为0，所以需要初始化。（初始化是根据我们最初的状态而定的）

3. 打印栈数据

void StackPrint(Stack* stack)
{
	for (int i = 0; i <= stack->top; ++i) 
	{
		printf("%d ", stack->a[i]);
	}

	printf("\n");
}
1
2
3
4
5
6
7
8
9

这里可以不可以实参不用指针？

可以的，这里用指针的目的是为了让程序都是传址

4. 压栈

void StackPush(Stack* stack, StackDataType x)
{
	assert(stack);

	//扩容问题
	if ((stack->top) + 1 == stack->capacity)
	{
		int newcapacity = stack->capacity == 0 ? 4 : (stack->capacity) * 2;
		StackDataType* tmp = (StackDataType*)realloc(stack->a, sizeof(StackDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("StackPush:realloc failed!");
			exit(-1);
		}

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

和顺序表类似，需要考虑扩容问题，因为realloc要知道开辟多大空间

5. 出栈

void StackPop(Stack* stack)
{
	assert(stack);
	//栈为空的时候不能出栈
	assert(stack->top > -1);

	stack->top--;
}
1
2
3
4
5
6
7
8

这里需不需要stack->top–后再把上一个数据置0呢？

不需要的，如果再次放数据时会覆盖原来的数据

6. 拿到栈顶元素

StackDataType TestStackTop(Stack stack)
{

	return stack.a[stack.top];
}
1
2
3
4
5

7. 判断栈是否为空

bool StackEmpty(Stack* stack)
{
	assert(stack);

	return stack->top == -1;
}
1
2
3
4
5
6

8. 栈中元素总数

StackDataType StackSize(Stack* stack)
{
	assert(stack);

	return stack->top + 1;
}
1
2
3
4
5
6

为什么这么这三个这么简单的程序还写成接口呢？

原因：当你拿到这个程序时你不需要知道栈顶的下标直接调用接口就可以实现功能，不要需要关心程序底层逻辑

9. 栈销毁

void StackDestroy(Stack* stack)
{
	assert(stack);

	stack->capacity = 0;
	stack->top = -1;
	free(stack->a);
	stack->a = NULL;
}
1
2
3
4
5
6
7
8
9

为什么这里stack->a需要置空？

原因：这个不是局部变量而是realloc出来的，必须置空，否则是野指针！