数据结构之栈

Hello各位小伙伴们继上期我们讲解了顺序表和链表，今天让我们来学习一下栈吧。

栈的基本概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 ​
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 ​
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

 

 栈的实现

与前两期的类似我们同时创建3个文件，两个.C文件，一个.h文件。

对于栈这样的数据结构我们要实现一下功能：

//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps,STDataType x);//在入栈的时候与顺序表的头插类似
//出栈
void StackPop(ST* ps);//在出栈时候直接让 (top--) 即可
//判断栈是否为空
bool StackEmpty(ST* ps);
//取栈顶元素
STDataType Get_Stack_Top(ST* ps);
//获取栈中元素个数
int STsize(ST* ps);

实现栈这样的数据结构我们底层使用顺序表或者链表都是可以的，当观察栈只会在一端进出栈并且内存还是连续的所以我们选择数组作为它的底层结构。

所以栈这样的结构体为：

typedef struct Stack
{STDataType* arr;int top;//栈顶int capacity;//栈容量
}ST;

1.栈的初始化

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

2.栈的销毁

void STDestroy(ST* ps)
{if (ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}

 3.入栈

在进行入栈操作时，栈的空间会变大，Capacity和top都会变大，需要额外申请空间，所以我们需要使用realloc函数来操作，此操作和顺序表类似，小编在这里就不在详细讲解了。

void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity)//此时空间满{//使用realloc增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//此时空间足够ps->arr[ps->top++] = x;
}

4.出栈

相较于入栈来说，出栈就比入栈要简单，只需要是得top--即可。

void StackPop(ST* ps)
{assert(!StackEmpty(ps));//栈不能为空--ps->top;
}

5.判断栈是否为空

判断栈是否为空，我们只需要判断栈顶元素是否为空，同时我们使用bool类型来进行判断。

bool StackEmpty(ST* ps)
{assert(ps);//传递的参数不能为空return ps->top == 0;//判断栈顶是否为空
}

6.取栈顶元素

取栈顶元素与出栈不同，在进行取栈顶元素的时候，并不是取出的元素，将栈里面的元素销毁，而是读取栈里面栈顶元素。 

STDataType Get_Stack_Top(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];//不可以直接传递ps->top,很·容易误解为是栈顶元素，实则是栈中元素个数
}

7.获取栈中元素个数

//获取栈中元素个数
int STsize(ST* ps)
{assert(ps);return ps->top;
}

小伙伴们在实现栈这样的数据结构的时候写完一个功能要记得在咱们创建的test.c文件中调试一下，这样会为后期的带来极大的便利。

今天的内容就到这里啦，下期我们将会讲解数据结构之队列。我们下期再见！