【数据结构】带你图文结合深入栈和队列，并具体分步实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】带你图文结合深入栈和队列，并具体分步实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】带你图文结合深入栈和队列，并具体分步实现,初阶数据结构,数据结构,算法,c语言,c++,开发语言

君兮_的个人主页

勤时当勉励岁月不待人

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，我们继续来学习初阶数据结构的内容，今天我们要讲的是栈与队列部分的内容，这篇博客先讲栈，队列我们放到下次再讲
好了，废话不多说，开始今天的学习吧！—

一.栈

1.栈的概念及结构

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

2.栈的实现方式

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的不需要付出很大的代价。
如果使用链表方式实现的话，会出现一个问题，我们的栈实际上是通过尾插实现入栈的，也就是说在入栈时我们每一次都需要通过遍历的方式找尾，或者使用双头循环链表的方式找尾，但是由于数组的连续性和支持随机访问，对比于链表无疑是更加方便的。因此，接下来内容中的栈结构我们就通过数组的方式实现。

3.栈的分类

栈分为静态栈和动态栈

静态栈

// 下面是定长的静态栈的结构，实际中一般不实用
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType a[N];
int _top; // 栈顶
int _capacity; // 容量
}Stack;

动态栈

动态栈是通过动态内存开辟的方式实现的，由于支持动态内存的变化，因此在实际应用中动态栈无疑是更好的选择

typedef int STDataType;//方便以后修改栈中存储的数据类型
typedef struct Stack
{
    STDataType* a;//数组
    int top;//存放栈中有效元素的个数
    int capacity;//栈的容量大小
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
//获取栈底元素
STDataType StackTail(Stack* ps);

4.动态栈的实现

栈的初始化函数 StackInit

无论是什么数据结构，我们都得先初始化

// 初始化栈
void StackInit(Stack* ps)
{
    assert(ps);//断言
    ps->a = NULL;//数组中还没有元素
    //容量和有效元素都为0
    ps->capacity = 0;
    ps->top = 0;
}

入栈函数 StackPush

// 入栈
void StackPush(Stack* ps, STDataType data)
{
    assert(ps);
    //判断是否还有空间
    if (ps->capacity == ps->top)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//通过容量判断此时栈中有没有元素，如果没有元素就申请4个字节的空间，如果有容量，但容量不够时就把容量变为之前的2倍
        STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity* sizeof(STDataType));
        if (tmp == NULL)//判读开辟空间是否成功
        {
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;//成功了就把这个新的空间给我们的a数组
        ps->capacity = newCapacity;//容量也要做相应的动态变化
    }
    ps->a[ps->top] = data;//往栈中存元素
    ps->top++;//有效元素++
}

【数据结构】带你图文结合深入栈和队列，并具体分步实现,初阶数据结构,数据结构,算法,c语言,c++,开发语言

这里可能有些人对于动态内存管理的内容不够了解，可以看看我这篇博客：【C语言进阶】那些你必须掌握的C/C++要点——动态内存管理(1)
这里还有一点要提，这里为什么用realloc开辟空间而不是使用malloc呢？
这里就涉及一些realloc的进阶玩法
我们知道realloc是用来修改动态开辟的内存大小，但是当我们给它传入的是一个空指针，它的功能与malloc就是相同的。

出栈的函数 StackPop

// 出栈
void StackPop(Stack* ps)
{
    assert(ps);
    --ps->top;
}

出栈就非常简单啦，我们直接让top减1就行，由于我们的数组是通过下标的方式访问数组成员的，top只有减少就无法在找到相应的元素啦

获取栈顶元素的函数 StackTop

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    //有效元素为top，数组的下标得-1
    return ps->a[ps->top-1];
}

我们栈中的元素是尾插的，因此最后一个元素就是我们的栈顶元素

获取栈底元素 StackTail

需要栈底的情况其实并不常见，我们会在某些特别情况下才会用到（比如我们之后会带大家写的oj题）

STDataType StackTail(Stack* ps)
{
   assert(ps);
   return ps->a[0];
}

我们的元素是尾插进数组的，因此我们的首元素就是我们的栈底元素。

获取栈中有效元素的个数的函数 StackSize

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}

我们在之前无论是入栈还是出栈都变化了我们的有效元素top，因此返回的top就是我们的有效元素个数。

判断栈是否为空的函数 StackEmpty

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}

top存着我们的有效元素，因此可以通过判断top是否为0来判断栈是否为空

销毁栈的函数

// 销毁栈
void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->a);//free掉动态开辟的数组
    ps->a = NULL;//置空
    ps->top = ps->capacity = 0;//把有效元素和容量全部清空
}

我们的内存是通过动态开辟出来的，因此当我们使用完后就必须把我们的申请的内存给free掉防止内存泄漏。

5.测试栈

我们来试试的效果

void TestStack1()
{
    Stack ST;
    StackInit(&ST);
    StackPush(&ST, 10);
    StackPush(&ST, 20);
    StackPush(&ST, 30);
    while (!StackEmpty(&ST))
    {
        printf("%d ", StackTop(&ST));
        StackPop(&ST);
}
    
    StackDestroy(&ST);
   

}
int main()
{
    
    TestStack1();
    return 0;
}