君兮_的个人主页

勤时当勉励 岁月不待人

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++要点——动态内存管理(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;
}

总结

• 今天的内容到这里就结束了，如果你能理解之前讲过的顺序表，链表等，栈的内容其实非常的简单，想学好的话，一定要自己动手试试哦！！
• 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！

新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力！！！

**（可莉请求你们三连支持一下博主！！！点击下方评论点赞收藏帮帮可莉吧）**