Hello大家好,我是PomeloMars!

首先啊恭喜我们的“「数据结构与算法」链表 —— 看这一篇就够了(超详细)”一文

入选了数据结构与算法领域第18名!!!

谢谢大家对我的支持!!!

好了一起让我们“栈”胜过去,冲向未来吧!

一、栈之简介

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。它的进出规律为先进后出(故得名FILO(First In Last Out)结构)

如果你觉得想象不出来它是什么东西,那你就拿出你的水杯来看看.水杯的杯口那就叫做栈顶,另一段就是栈底:

二、栈之创建

栈有两种存储表示方法——顺序栈和链栈,顺序栈可以用数组来表示,这里我们着重介绍顺序栈(因为简单).

我们先创建一个结构体名叫TStack,里面包含StackLst(栈的数组,容量为10(volume)个数据元素)还有一个top指针(说是指针,其实只是一个索引而已),接着再创建一个TStack的实例Stack:

const int volume = 10;
struct TStack{
    int StackLst[volume];
    int top=-1;
}Stack;

三、栈之判空

我们可以通过判断top是否为-1来决定栈是不是空的:

bool IsEmptyStack(int top){
    if (top==-1){
        return true;
    }
    return false;
}

如果你的top是0的话也可以这样写:

bool IsEmptyStack(int top){
    if (!top){
        return true;
    }
    return false;
}

注意,我们这里使用了!这个逻辑运算符,意思为“非”,比如!1就是0,!0就是1.

四、栈之判满

我们只需要将top这个变量与你栈的容量(volume)比较即可:

bool IsFullStack(int top){
    if (top==volume){
        return true;
    }
    return false;
}

五、栈之进栈

在进栈之前,我们先要判断这个栈是否是满的,如果是则不能进栈(所以刚才的IsFullStack函数就派上用场了):

bool StackPush(int value){
    if (IsFullStack(Stack.top)) return false;
    Stack.StackLst[++Stack.top] = value;
    return true;
}

在判断好是否为满栈后我们将StackLst的++top项设为value(如果你的top初始化为0的话则改为top++,具体见后面即将出品的“C++ 自加自减”一文)

六、栈之出栈

在出栈之前,我们先要判断这个栈是否为空的,如果是则不能进栈(所以刚才的IsEmptyStack函数就派上用场了):

bool StackPop(){
    if (IsEmptyStack(Stack.top)) return false;
    Stack.top--;
    return true;
}

如果你想在出栈的同时获取出栈元素,可以把返回值设为int(推荐):

int StackPop(){
    if (IsEmptyStack(Stack.top)) return false;
    return Stack.StackLst[Stack.top--];
}

注意,前面的StackPush函数与StackPop函数的返回值类型也可以是void类型,我这里只是判断是否成功,所以用bool类型

七、完整代码

接下来就给大家完整代码,如果想了解链栈(就是用链表的方式来存储栈),链表超详细文章见「数据结构与算法」链表 —— 看这一篇就够了(超详细)https://blog.csdn.net/Pomelo_ABC/article/details/126482099 直接上代码:

#include <iostream>
using namespace std;

const int volume = 10;
struct TStack{
    int StackLst[volume];
    int top=-1;
}Stack;

bool IsEmptyStack(int top){
    if (top==-1){
        return true;
    }
    return false;
}

bool IsFullStack(int top){
    if (top==volume){
        return true;
    }
    return false;
}

bool StackPush(int value){
    if (IsFullStack(Stack.top)) return false;
    Stack.StackLst[++Stack.top] = value;
    return true;
}

int StackPop(){
    if (IsEmptyStack(Stack.top)) return false;
    return Stack.StackLst[Stack.top--];
}

八、关于栈的题目

国内许多OJ题目都会考到栈的操作,比如CCF的CSP等等.尽然都学了栈,那也来做做吧:

第一题:

这种题的话也是最常考的题,难度属于简单,只要不断的尝试就行了:

第一选项:正确,像出栈顺序和入栈顺序完全相反和完全一样的选项都是对的,一个是全部都放进去再全都拿出来,一个是放进去就拿出来
第二选项:错误,b不可能在c之前出栈
第三选项:正确
同一

答案: B

第二题:

这道题有了上道题的讲解因该可以秒杀了

答案: D(见上一题第一选项分析)

第三题:

这道题着重考我们第一部分——栈之简介的知识点,相信仔细看的同学已经选出答案了

答案: D

第四题:

这是一道关于链栈的题目,大家可以通过完整代码部分的链接进行学习

答案: B

九、结束语

好了,今天的内容就到此结束啦,如果这篇文章对你有所帮助的话,请一键三连支持一下作者吧,我们下期再见!

本文含有隐藏内容，请开通VIP 后查看

「数据结构与算法」栈 —— 栈胜过去(超详细讲解)