栈与队列 数据结构 C语言

目录

一、栈

1、类型定义

2、接口函数

3、功能实现

初始化栈

进栈

删除栈顶

出栈

销毁栈

其他功能

一、栈

先进后出（后进先出）

1、类型定义

typedef int STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

2、接口函数

void StackInit(ST* ps);

void StackDestroy(ST* ps);

void StackPush(ST* pa, STDataType x);

void StackPop(ST* ps);

STDataType StackTop(ST* ps);

int StackSize(ST* ps);

bool StackEmpty(ST* ps);

3、功能实现

初始化栈

void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    //初始化时，top给的是0，意味着top指向栈顶数据的下一个
    //初始化时，top给的是-1，意味着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 = realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            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--;
}

出栈

无特定函数

//打印数据,取数据
    while (!StackEmpty(&st))//当栈不为空时
    {
        printf("%d ", StackTop(&st));
        StackPop(&st);//销毁当前栈顶，使下一个数成为栈顶
    }

销毁栈

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

其他功能

STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

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

    return ps->top;
}

bool StackEmpty(ST* ps)
{
    assert(ps);
    
    /*if (ps->top > 0)
    {
        return true;
    }
    else
    {
        return false;
    }*/

    return ps->top == 0;
}