数据结构初阶之栈

今天更新栈

栈其实还蛮简单的，接口函数的实现也主要用的都是前面学过的知识，顺序表那块。

至于什么是栈，看一下百度定义就好，本文重点实现接口函数

栈（计算机术语）_百度百科

#pragma once
#include 
#include 
#include 
#include 

//#define N 10
//typedef int STDataType;
//typedef struct Stack
//{
//	STDataType a[N];
//	int top;
//}ST;
//我们不使用静态的栈


typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;//栈的元素定义

void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//入栈
void StackPop(ST* ps);//出栈
STDataType StackTop(ST* ps);//取栈顶元素
bool StackEmpty(ST* ps);//判断栈是否为空
int StackSize(ST* ps);//栈的大小

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;

}

void StackPush(ST* ps, STDataType x)
{
	//判断容量，不够增容
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType*) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//插入
	ps->a[ps->top] = x;
	ps->top++;
}

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

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));


	return ps->a[ps->top--];
}

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

	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}