栈（stack）知识点整理总结

往期内容： STL总目录-超详细
Ps：建议与 队列queue 搭配食用对比理解记忆

目录

1. 栈是什么？
2. 栈的相关概念
3. 变量声明及成员函数

栈是什么？

栈(stack)也是c+ +标准模板库中的一个容器，他与queue同样属于线性数据存储结构，所以栈和队列有很多的相似之处。
那么我们来对比着看一看栈的特殊性质：
1.我们知道在队列中，元素遵循FIFO原则，即先进先出原则(First In First Out)。而在栈中，元素遵守的则是FILO原则，即先进后出原则(First In Last Out)，或者也可以成为后进先出等。意思应该也很好理解，就像是一个桶，我们先放入的东西一定在桶的下面而后放入的东西存在桶的上面，取用时，后放入的东西（即在桶顶部）的东西会最先被取走。再比如说，我们洗完碗后，会将干净的碗摞起来，先放的碗在下面，后面的依次放在上面，这就是栈的储存方式。
2.在队列中，我们只能从队尾插入元素而只能从队头取出元素，而在栈中，我们只能从栈的“顶部”取用和存储元素，而栈底一般是不动的，还是和上面的桶一样的例子，你总不能把桶的底拆掉从里面拿东西吧。
所以，对栈的最简单的理解方式就是把它看作一个桶
生活中栈是很常见的：一摞东西，桶，汉诺塔，弹夹......
上图：

栈的相关概念

• 栈顶：栈中允许插入和弹出元素的一端
• 栈底：栈中不是栈顶的另一端 //好像是废话
• 压栈（入栈）：栈中的插入操作，也叫进栈
• 弹栈（出栈）：栈中的删除操作。
• 空栈：没有任何元素的栈

栈的数组表示（part 1）

栈与数组同为作为一种线性结构，我们也可以尝试将栈用数组表示出来：
一个栈可以用一个定长为n的数组表示，在用一个“指针”top指向栈顶元素的位置。那我们根据栈的性质可以得到：
1.当top的值为0时，表示这个“栈”中没有任何元素，即栈空；
2.当top的值为数组的定长n时，表示我们所开的栈已经存满，不能再存入任何元素了。

变量声明及成员函数

头文件

#include <stack>

定义与声明

用法（格式）：stack<类型> 名称

stack<int> a;
//构造一个名为a存储int类型数据的栈
stack<string> b;
//构造一个名为b存储string类型数据的栈

压栈 .push()

拥有了一个栈后，第一步便是向栈中压入一个元素，那么一如既往，我们先来介绍插入元素的操作——压栈
用法（格式）：名称.push(x)x为与定义的栈类型相同的一个数据

stack<int> a;
stack<string> b;
//构造一个存储int类型数据的栈a和一个存储string类型的栈b

a.push(1);
//a:1
b.push("Hello stack!");
//b:Hello stack!
a.push(2);
//a:1 2

弹栈 .pop()

有了输入，那么必然会有输出，再强调一遍：栈只能从栈顶一端插入或弹出元素。
用法（格式）：名称.pop()

stack<int> a;
a.push(1);
a.push(2);
a.push(3);
//a: 1 2 3

a.pop();
//a: 1 2

查看栈中元素的个数 .size()

关于这个STL必备函数，应该也没有什么太多可说的了，你的栈中共存储了几个元素，它的返回值就是几（整型）
用法（格式）：名称.size()

stack<int> a;
a.size() == 0;
a.push(1);
a.size() == 1;
a.push(2);
a.size() == 2;

判断栈是否为空栈 .empty()

rt，他能返回一个bool类型的值，用于判断栈是否为空，即是否存储了元素。
用法（格式）：名称.empty()

stack<int> a;

a.empty() == true;

a.push(1);
a.empty() == false;

访问栈顶元素 .top()

由于栈是一个只有一端可被访问的容器，所以.top()是唯一一个用于查看元素的函数，他的返回值即为栈顶元素的值。它只返回栈顶元素的值而不删除栈顶元素。
用法（格式）：名称.top()

stack<int> a;
a.push(1);

a.top() == 1;
a.push(3);
a.top() == 3;
a.size() == 2;

栈的数组表示（part 2）

在了解了栈的基本操作后，我们回到刚刚提到过的用数组表示的栈，在数组结构中，我们又该怎样执行这些操作呢？
如果top<0，我们称为下溢。（如弹出的次数大于栈中原有的元素个数时）
1、进栈（PUSH）算法
①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②TOP++（栈指针加１，指向进栈地址）；
③S[TOP]=X，结束（X为新进栈的元素）；
2、退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
②X=S[TOP]，（退栈后的元素赋给X）；
③TOP- -，结束（栈指针减１，指向栈顶）。

再次注意：栈指针top永远指向栈顶元素

栈的遍历

啊这个嘛，据我所知，stl中的栈应该没有什么遍历的方法。。。
（算法位招租）

尾声

感觉这期有点短QAQ
栈还是相对比较简单的，因为STL给它提供的内容太少了。。。
图片来自网络，如有侵权立即联系删除~
内容如有错误，或各位巨佬如有补充，敬请指导~
Orz

点赞👍🔼收藏⭐关注✅

ヾ(•ω•`)o掰掰