目录

【数据结构】——拿捏 栈和队列_C语言

一、栈

栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶

【数据结构】——拿捏 栈和队列_接口实现_02

出栈：栈的删除操作叫做出栈。出数据也在栈顶

【数据结构】——拿捏 栈和队列_栈和队列_03

栈的实现

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

【数据结构】——拿捏 栈和队列_C语言_04

顺序表可以把使用的空间写成固定值，也可以构建动态开辟内存；但是如果写成固定的数组形式当存的数据满了就不能再使用了，所以下面我们实现的是动态开辟内存的形式。

所以我们先创建一个顺序表结构体类型，结构体类型中有指针，下标，容量。
指针： 用来维护在堆上连续的一段空间，
下标：表示数据存放到哪一个位置了，因为数据只能一个接着一个地存放，要有个下标来记录我数据放到哪一个位置了。
容量：与下标相比较，当下标与容量相等就表示空间存储满了，要进行扩容处理。
创建类型如下：


typedef int STDataType; //对int类型重新起个名字叫DataType

//创建一个栈结构体类型
struct Stack   
{
    STDataType* a; //数据的指针
    int top;    //栈顶
    int capacity; //记录开辟空间的最大下标处
};

//对顺序表类型struct Stack类型重新起个名字叫SL
typedef struct Stack ST;

栈内存布局

【数据结构】——拿捏 栈和队列_C语言_05

栈的接口实现

1.栈的初始化和销毁

栈的初始化和销毁都与顺序表类似，这里就不再详细解释，只是顺序表中的size(有效元素个数)，换成了这里的栈顶。

//初始化变量st
void StackInit(ST* ps)
{
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

//栈的销毁
void StackDestroy(ST* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

2.入栈

与顺序表一样，增加元素时必须先判断容量是否足够，容量不够时需扩容。

这里的入栈和顺序表的尾插一样。

//入栈
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    //内存满了要扩容
    if (ps->capacity == ps->top)
    {
        ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2;
        STDataType* tmp = 
        (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);
        if (tmp == NULL)
        {
            perror("erron ");
            exit(-1);
        }
        ps->a = tmp;
    }
    //没有满就直接在后面入栈
    ps->a[ps->top] = x;
    ps->top++;

}

3.栈销毁

【数据结构】——拿捏 栈和队列_接口实现_06

//栈销毁函数
void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

4.出栈

出栈即尾删，删除元素需判断栈是否为空，空栈不能出栈。

判断栈是否为空在下面实现。

【数据结构】——拿捏 栈和队列_接口实现_07

//出栈函数
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top>0);
    
    ps->top--;        
}

5.获取栈顶元素

栈顶元素即顺序表中最后一个元素，直接根据下标即可找到。

当然栈不能为空。

【数据结构】——拿捏 栈和队列_C语言_08

//取栈顶部函数
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

6.栈大小

//栈大小函数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

7.遍历栈打印

【数据结构】——拿捏 栈和队列_接口实现_09

while (!StackEmpty(&stack))
    {
        printf("%d ", StackTop(&stack));
        StackPop(&stack);
    }