算法模板之栈图文详解

在这里插入图片描述
🌈个人主页：聆风吟
🔥系列专栏：算法模板、数据结构
🔖少年有梦不应止于心动，更要付诸行动。

文章目录

📋前言
一. ⛳️模拟栈
- 1.1 🔔用数组模拟实现栈
- - 1.1.1 👻栈的定义
  - 1.1.2 👻向栈顶插入一个数 x（进栈操作）
  - 1.1.3 👻从栈顶弹出一个元素（出栈操作）
  - 1.1.4 👻判断栈是否为空
  - 1.1.5 👻查询栈顶元素
- 1.2 🌟模板提取(重点)🌟
二. ⛳️题目练习
- 2.1 题目
- 2.2 输入样例
- 2.3 输出样例
- 2.4 c++代码
📝结语

📋前言

💬 hello! 各位铁子们大家好哇，我们上期已经学习了双链表的算法模板，不知道大家都已经掌握了吗？如果你还有缺漏可以通过下面专栏自行跳转学习，今天作者又又又给大家带来了栈的算法模板详细讲解，让我们一起加油进步。
📚 系列专栏：本期文章收录在《算法模板》，大家有兴趣可以浏览和关注，后面将会有更多精彩内容！
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

一. ⛳️模拟栈

1.1 🔔用数组模拟实现栈

1.1.1 👻栈的定义

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。如下图是栈的示意图：
在这里插入图片描述

1.1.2 👻向栈顶插入一个数 x（进栈操作）

根据栈的定义可知，我们可以将数组看作是横放的栈的示意图，即将数组的首元素位置看作栈底、当前元素的位置看作栈顶，便可以实现数组模拟栈的相关操作。如果我们要向栈顶插入一个元素，将栈顶指针向后移动一位将元素插入进去即可。如下图所示：
在这里插入图片描述
代码展示（建议结合图示看注释）：

//top表示栈顶
int stk[N], top = -1;

// 向栈顶插入一个数x
stk[++top] = x;

1.1.3 👻从栈顶弹出一个元素（出栈操作）

根据上面所知，如果我们要从栈顶弹出一个元素，我们只需要将栈顶指针向前移动一位即可。如下图所示：
在这里插入图片描述
代码展示（建议结合图示看注释）：

// 从栈顶弹出一个数
top--;

1.1.4 👻判断栈是否为空

根据上面所知，如果我们要判断栈是否为空，我们只需要判断栈顶指针是否指向数组首元素左边的位置（即判断top是否等于-1位置）。如下图所示：
在这里插入图片描述
代码展示（建议结合图示看注释）：

// 判断栈是否为空，如果 top >= 0，则表示不为空
if (top >= 0)
{
	//输出栈不为空	
}
else
{
	//输出栈为空
}

1.1.5 👻查询栈顶元素

根据下图所示，查询栈顶元素只需要输出数组下标为top的值即可；
在这里插入图片描述
代码展示（建议结合图示看注释）：

// 栈顶的值
stk[top];

1.2 🌟模板提取(重点)🌟

C++代码：

// top表示栈顶
int stk[N], top = -1;

// 向栈顶插入一个数x
stk[++top] = x;

// 从栈顶弹出一个数
top-- ;

// 栈顶的值
stk[top];

// 判断栈是否为空，如果 top >= 0，则表示不为空
if (top >= 0)
{
	//输出栈不为空	
}
else
{
	//输出栈为空
}

二. ⛳️题目练习

⌈ 在线OJ链接,可以转至此处自行练习 ⌋

2.1 题目

在这里插入图片描述

2.2 输入样例

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

2.3 输出样例

5
5
YES
4
NO

2.4 c++代码

#include <iostream>

using namespace std;

const int N = 100010;
int stk[N], top = -1;

int main()
{
    int m = 0;
    cin >> m;
    
    while(m--)
    {
        string s;
        cin >> s;
        if(s == "push")
        {
            //在栈顶插入一个元素
            int x = 0;
            cin >> x;
            stk[++top] = x;
        }
        else if(s == "pop")
        {
            //从栈顶弹出一个元素
            top--;
        }
        else if(s == "empty")
        {
            //判断栈是否为空
            cout << (top >= 0 ? "NO":"YES" ) << endl;
        }
        else
        {
            //查询栈顶元素
            cout << stk[top] << endl;
        }
    }
    
    return 0;
}