🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

一、栈

1 栈的概念及结构

2 栈的实现

​编辑

1.1 栈的各个接口

1.2 栈的初始化

1.3 栈的释放

1.4 入栈

1.5 出栈

1.6 获取栈顶数据

1.7 获取栈中的有效元素个数

1.8 检测栈是否为空

1.9 栈测试

1.10 运行效果

一、栈

1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈符合 - 后进先出（Last In Firsh Out）

2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

如果有特定场合要用链表作为栈的实现，那我们应该将头和尾巴翻过来，示意图:

1.1 栈的各个接口

// 栈的数据结构
typedef int STDataType;
typedef struct Stack
{
    STDataType* data;
    int top;            // 栈顶
    int capacity;       // 容量
}Stack;
​
// 初始化栈 
void StackInit(Stack* pStack);
​
// 栈销毁
void StackDestroy(Stack* pStack);
​
// 入栈
void StackPush(Stack* pStack, STDataType data);
​
// 出栈
void StackPop(Stack* pStack);
​
// 获取栈顶数据
STDataType StackTop(Stack* pStack);
​
// 获取栈中的有效元素个数
int StackSize(Stack* pStack);
​
// 检测栈是否为空，如果为空返回非零的结果，如果不为空返回零。
bool StackEmpty(Stack* pStack);

1.2 栈的初始化

// 初始化栈函数实现
void StackInit(Stack* pStack)
{
    // 断言：保护形参的指针。
    assert(pStack);
    // 初始化
    pStack->data = NULL;
    pStack->top = pStack->capacity = 0;
}

1.3 栈的释放

void StackDestroy(Stack* pStack)
{
    // 断言：保护形参的指针。
    assert(pStack);
    // 释放内存-》初始化
    free(pStack->data);
    pStack = NULL;
    pStack->top = pStack->capacity = 0;
}

1.4 入栈

入栈动图演示

入栈的两种情况

// 入栈函数实现
void StackPush(Stack* pStack, STDataType data)
{
    // 断言：保护形参的指针。
    assert(pStack);
​
    // 检测容量。
    if (pStack->top == pStack->capacity)
    {
        int newCapacity = pStack->capacity == 0 ? 4 : pStack->capacity * 2;
        STDataType* pTemp = (STDataType*)realloc(pStack, newCapacity * sizeof(STDataType));
        if (pTemp == NULL)
        {
            perror("StackPush realloc fail!");
            exit(-1);
        }
​
        // 开辟成功
        pStack->data = pTemp;
        pStack->capacity = newCapacity;
    }
​
    // 入栈顺序
    pStack->data[pStack->top] = data;
    ++pStack->top;
}

1.5 出栈

出栈动图演示

// 出栈函数实现
void StackPop(Stack* pStack)
{
    // 断言：保护形参的指针。
    assert(pStack);
    assert(StackEmpty(pStack->top)); // 检测栈是否为空
​
    --pStack->top;
}

1.6 获取栈顶数据

// 获取栈顶数据函数实现
STDataType StackTop(Stack* pStack)
{
    // 断言：保护形参的指针。
    assert(pStack);
    assert(!StackEmpty(pStack)); // 检测栈是否为空
    
    return pStack->data[pStack->top-1];
}

1.7 获取栈中的有效元素个数

// 获取栈中的有效元素个数
int StackSize(Stack* pStack)
{   
    // 断言：保护形参的指针。
    assert(pStack);
​
    return pStack->top;
}

1.8 检测栈是否为空

// 检测栈是否为空，如果为空返回非零的结果，如果不为空返回零。
bool StackEmpty(Stack* pStack)
{
    // 断言：保护形参的指针。
    assert(pStack);
​
    return pStack->top == 0;
}

1.9 栈测试

void TestStack()
{
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    StackPush(&st, 5);
​
    // 栈不为空可以访问
    while (!StackEmpty(&st))
    {
        printf("%d ",StackTop(&st));
        StackPop(&st);
    }
    printf("\n");
}

1.10 运行效果