|
? ? ? 创建一个栈之前，我们需要先想好栈的特点以及栈如何去使用更加方便。栈可以用顺序表或者链表的方式来实现，我们考虑一下顺序表和链表在创建栈时分别会有什么优缺点。
链栈按需申请空间，不会造成空间浪费，需要存储一个指针消耗一定空间。
顺序栈无法按需申请空间，可能会造成空间浪费，但只需存储数据，并且空间连续，空间利用率高。
? ? ? 由于顺序栈和链栈的插入和删除操作时间复杂度都是O(1)，所以如果所栈元素的数目会在使用过程中发生较大的改变，我们一般使用链栈，而倘如我们栈的元素数目是固定不变的，则最好采用顺序栈的方式来存储。?
? ? ? ? ?对于小白来说，顺序栈可能会更好理解，并且顺序表和链表各有优缺，所以在此使用顺序表建立栈。
? ? ? ? ? 首先需要考虑的是一个栈的结构体需要什么，我们需要栈顶的元素，所以用一个top变量记录，我们存储元素需要数组，记录数组大小需要一个size变量。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
?? ?STDataType* a;
?? ?STDataType top;
?? ?STDataType capacity;
}ST;
? ? ? ?这样一个栈的结构体就建立好了。
一个栈的基本功能应该有这些：
void StackInit(ST* ps);
void StackDestory(ST* ps);
void Stackpush(ST* ps, STDataType);
void StackPop(ST* ps);
STDataType Stacktop(ST* ps);
int Stacksize(ST* ps);
bool StackEmpty(ST* ps);
初始化、销毁、插入、删除、返回栈顶元素、返回栈的大小、判断栈是否为空。
初始化：
void StackInit(ST* ps)
{
?? ?assert(ps);//结构体指针不为空
?? ?ps->a = NULL;
?? ?ps->top = 0;
?? ?ps->capacity = 0;
}
销毁：
void StackDestory(ST* ps)
{
?? ?assert(ps);
?? ?free(ps->a);
?? ?ps->capacity = 0;
?? ?ps->top = 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 = (ST*)realloc(ps->a, sizeof(STDataType)*newCapacity);
? ? ? ? //创建一个变量把申请的空间给他
?? ??? ?if (tmp == NULL)
?? ??? ?{
?? ??? ??? ?printf("realloc fail");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ?ps->a = tmp;//把tmp空间给数组
?? ??? ?ps->capacity = newCapacity;
?? ?}
?? ?ps->a[ps->top] = x;
?? ?ps->top++;
}
删除：
void StackPop(ST* ps)
{
?? ?assert(ps);
?? ?assert(ps->top > 0);//栈顶位置必须大于0
?? ?ps->top--;
}
其他：
int Stacksize(ST* ps)
{
?? ?assert(ps);
?? ?return ps->top;
}
?
bool StackEmpty(ST* ps)
{
?? ?return ps->top<=0;
}
STDataType Stacktop(ST* ps)
{
?? ?return ps->a[ps->top];
}
这样就把一个栈和栈的功能创建完了。
|