数据结构——栈

栈

• 什么是栈
• 创建类型
• 初始栈
• 压栈
• 出栈
• 察看栈顶的元素
• 栈的个数
• 栈是否为空
• 栈的销毁

---

什么是栈

栈是一种特殊的线性结构，对数据增加及其删除只能在一端进行 *** 作。
进行数据删除及增加的一端为栈顶，另一端为栈底。
增加数据为压栈。删除数据为出栈。

创建类型

typedef int StackTypeDate;

typedef struct stack
{
	StackTypeDate* arr;
	int top;
	int capacity;
}Stack;

初始栈

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

压栈

压栈的时候要察看栈是不是满了，以及它为空的情况。

void StackPush(Stack* ps, StackTypeDate x)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->arr = (StackTypeDate*)realloc(ps->arr,sizeof(StackTypeDate) * newcapacity);
		ps->capacity = newcapacity;
	}

	ps->arr[ps->top] = x;
	ps->top++;
}

出栈

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

察看栈顶的元素

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

栈的个数

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

栈是否为空

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

	return ps->capacity == 0;
}

栈的销毁

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