前言

一道题目卡两天还行，大脑升级就完事了奥。

it->second.begin()->first.begin()->first.end() //码风丢人到国外了。

顺便说一个小彩蛋，看完今天这文回去上机试一试，故意写一个溢出的栈，然后去调内存，如果不出意外的话，应该就是我的名字哈哈哈哈哈(0xC00005)

这篇文章我不打算在简书发，大佬太多发这么基础还写不好的东西肯定会被D死的QAQ

后期喵：我去简书搜索了一下我靠全是各种全栈调用栈内存大佬，像我这样子供向的文章还是不要拉出去丢人了吧qwq

1.栈

0x01 why 栈

某集训队的大大大佬汝佳曾经说过这样一句话：
要判断一个人是不是OIer:该死的死肥宅Coder，只需要问他push的和反义词是什么？
正常人会回答back，死肥宅会说pop同时给你一个诡异的微笑。

作为一个最最最重要的数据结构（也是学起来挺白痴的数据结构），相信读文的各位应该都已经在别的语言中接触了栈那种先进后出的数据结构了，没接触过？

图片来自极客学院
栈（stack），又名堆栈，是一种运算受限制的线性表类型的数据结构。其限制是只允许在栈的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

但是在实际操作中你基本上不会用到栈底这个概念，不然就是你数据结构用错了因为如果使用栈底了，那么先进后出的数据特性还有什么用呢qwq

可以想象往子弹夹中装子弹的情形，正常情况下只能往子弹夹入口那端装入子弹，这一步就好比向栈中压入元素，称为push，射击的时候，弹夹会从顶端弹出子弹，这一步就好比从栈顶弹出元素，称为pop，可以发现，从栈顶弹出的子弹是最后一个压进去的子弹，这也是栈的一个重要性质，先进后出（FILO——first in last out）。另外，用一个top指针来标示当前栈顶的位置。

我永远喜欢416.jpg

其实栈底和栈顶并不是两个人为规定的数字或者位置，其实只不过是两个指针而已，pop也并没有把数据从内存中删除，只是pop指针换了一个位置而已

0x02 make a 栈

谢天谢地STL已经为你提供了现成了stack头文件，你只需要引用就完事了，

#include<stack>

你绝对不想体验用结构体，指针手写栈的感觉

很好，416也不想写

int stack[maxsize], top = 0;
void push(int x) {
    stack[top++] = x;
}
void pop() {
   --top;
}
int topval() {
    return stack[top - 1];
}
int empty() {
    return top > 0;
}

手写还要手动固定数组的缓存大小，所以嘛.....
引用搬砖就成了。

然后按照STL一贯的命名方法来进行命名

stack<int> S

这里定义了一个整数的空栈

0x03 推入子弹，射击！

这次终于不是insert而是push了，这也太棒了吧

    S.push(1);

现在我们要倾斜我们的火力，先检查一下弹夹是不是空的，然后扣动扳机【这样表述栈会比较形象些？】

吃我416的x16小核弹

while(!S.empty())
    {
        cout<<S.top()<<endl; //访问栈顶的元素
        S.pop(); //射击
    }

其实说起来没什么技术难度，重要的是做做题并且熟练的掌握所谓的套路，确认过眼神，是对的数据结构就好了

队列

0x01 Why 队列

栈是后进先出，那么队列就是先进先出了。
如果说栈是手枪射击的过程的话，队列就是跑到食堂去买饭，双向队列就是插队的你吧
或者说马克沁大水枪也可以，不用弹匣用弹链的那种。

队列（queue） 是一种线性的数据结构，和栈一样是一种运算受限制的线性表。其限制只允许从表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。一般允许进行插入的一端我们称为队尾，允许删除的一端称为队首。

队列的插入操作又叫入队，队列的删除操作又叫出队。 可以把队列想象成购物时排队结账的时候的队伍，先排队的人会先结账，后排队的人会后结账，并且不允许有插队的行为，只能在队伍的末尾进行排队。这就是队列的特点，具有先进先出（FIFO——First In First Out）的性质。

图片来自：计蒜客

非常重要的是，队列也不是像数组一样的是有规律的可以通过下标访问的那种【不知道该怎么表达】，最重要的前端和后端只不过是两个指针而已，档然咯比赛中不会深究这个，只需要了解就好啦~

队列的主要操作包括：

• 入队（push）
• 出队（pop）
• 判断队列是否为空（empty）
• 统计队列元素的个数（size）
• 访问队头元素（front）
• 访问队尾元素（back）
  注意这里没有访问中间任意元素这一说，我们能访问的元素只有两个，即最上面和最下面

0x02 make a 队列(后期：应该是一队队列，不是a)

按照以往STL的尿性，肯定有现成的库给你用啦~
这不：

#include<queue>

然后你懂的，定义一个实例：

queue<int> q;

0x03 制作弹链

可能很多同学不明白为什么标题要写制作弹链，首先队列也是一种单向链表嘛【啊呸】

窑子摸爆
对于少女前线中机枪的击发相信大家都很熟悉，弹链从左边开始装填，从左往右，然后再把最早左边装填的弹药塞【嗯？】进枪里面。

首先我们推三发子弹进去：

    q.push(1);
    q.push(2);
    q.push(3);

好了，如果现在把弹链换成弹夹，我开枪应该打出来的是3（最后一个装填的子弹）对不对？
但是弹链（queue）的话，应该是1被弹出了，因为1在最左边，整个弹链是从左往右击发，所以现在打出来的应该是1。

好了我们现在来清空一下我们的弹药：

while(!q.empty())
    {
        cout<<q.front()<<endl;
        q.pop();
    }

老王摸摸狗！哒哒哒~

如果有时候需要用到循环队列的话，可以进行手写，但是要事先预估大小，有STL写你🐎呢

#define maxsize 10000
class queue {
    int q[maxsize];
    int front, rear, count;
    queue() {
        front = 0;
        rear = 0;
        count = 0;
    }
    void push(int x) {
        count++;
        if (count == maxsize) {
            // 溢出
        }
        q[rear] = x;
        rear = (rear + 1) % maxsize;
    }
    int pop() {
        count--;
        front = (front + 1) % maxsize;
        return q[front];
    }
    int front_val() {
        return q[front];
    }
    bool empty() {
        if (count == 0) {
            return true;
        }
        return false;
    }
};

你写你🐎呢

后记

少前真好玩，不说了我去玩少前了，
参考资料：
计蒜客
你应该去打一把少女前线

最后的最后

我都不公开发表了还写广告干甚？