栈（一）

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。用动态数组实现时唯一的缺陷就是需要扩容；也可以使用单链表实现，单链表的头插头删更方便，所以单链表的头可以当作栈顶，单链表的尾可以当作栈底。本篇文章采用的是动态开辟的数组实现对栈的基本操作。 定义结构体：

typedef int STDataType;
typedef struct Stack {
	STDataType* arr;
	int top;//栈顶元素的下一个坐标
	int capacity;//数组容量
}ST;

1.初始化栈

void StackInit(ST* ps)//初始化栈
{
	assert(ps);//避免传过来的地址为空
	STDataType* tmp = (STDataType*)malloc(sizeof(STDataType*)*4);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ps->arr = tmp;
	ps->top = 0;
	ps->capacity = 4;
}

初始化栈时必须要断言，避免穿过来的指针为空，同时也避免了当定义变量为ST* st=NULL; 对其进行初识化StackInit(st)这种情况的发生。top初始化为0，表示指向栈顶元素的下一个位置，也可以表示栈中的元素个数；top初始化为-1，表示指向栈顶元素。

2.压栈

void StackPush(ST* ps, STDataType x)//压栈
{
	assert(ps);
    //判断是否需要扩容
	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType*) * 2 * ps->capacity);//扩容
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = 2 * ps->capacity;
	}
	ps->arr[ps->top] = x;
	ps->top++;
}

压栈时要检查数组是否已满，是否需要对其进行扩容。