[C++STL教程]3.stack栈入门简明教程,小白都能理解~
在学习之前,先了解一下什么是stack
。
std::stack 类是容器适配器,它给予程序员栈的功能——特别是 FILO (先进后出)数据结构。
该类模板表现为底层容器的包装器——只提供特定函数集合。栈从被称作栈顶的容器尾部推弹元素。
FILO
指的是First In Last Out
,也就是说第一个进来的,是最后一个出去的。我们可以将stack
理解为一个上端开口的铁箱子,我们可以从顶部拿出物品或放入物品,且记录物品个数。
stack
仅维护一个栈顶,意味着我们只能从一端对数据进行操作。
本文仅从入门和实用角度介绍queue的用法,主要针对初学者或竞赛向。如有不严谨的地方欢迎指正!
初始化
在使用stack
之前,需要先引入头文件。
#include <stack>
初始化的语法如下:
stack<T> stk;// T 为数据类型
stack<int> stk_int;//声明一个栈,存放类型为int
和其他的stl容器一样,stack
只能存放相同类型的元素,默认初始化为空栈。
入栈
stk.push(x)
将元素x
推入栈stk
的栈顶,复杂度O(1)
。
每入栈一个新元素,会使得栈的大小+1。
// 左边为栈顶
// stk: empty
stk.push(1);
// stk : 1
stk.push(5);
// stk : 5 1
还有一种方法是用emplace()
函数进行入栈,两者差别可以暂时忽略。
stk.emplace(7);
// stk : 7 5 1
出栈
stk.pop()
将stk
的栈顶元素弹出栈,复杂度O(1)
。
// stk : 7 5 1
stk.pop();
// stk : 5 1
stk.pop();
// stk : 1
在出栈时要注意栈是否为空,空栈不允许出栈。这和queue
出队类似,感兴趣的可以看看这篇文章:https://www.eriktse.com/technology/1063.html
你问一个人“push”的反义词是什么?如果他回答“pop”那他一定是程序员。(答案也许是“pull”)
获取栈顶元素
语法:stk.top()
可以获取栈顶元素,但是不会自动将栈顶元素弹出。需要自行pop()
。复杂度O(1)
。
// stk : 7 5 1
cout << stk.top() << '\n';// 7
注意获取栈顶元素的时候也需要保证栈不为空,否则将导致错误!
获取栈的大小
语法:stk.size()
,返回值为一个非负整数,当返回0
时表示栈为空,复杂度O(1)
。
// stk : 1
cout << stk.size() << '\n';// 1
stk.push(9);
// stk : 9 1
cout << stk.size() << '\n';// 2
本文由eriktse原创,未经允许禁止转载!
判断栈是否为空
语法:stk.empty()
,返回值为一个bool
值,当返回true
时表示栈为空,当返回值为false
时表示栈非空。复杂度O(1)
。
// stk : 9 1
cout << st.empty() << '\n';// false
stk.pop(), stk.pop();
// stk : empty
cout << st.empty() << '\n';// true
当然你也可以用stk.size() == 0
来判断栈是否为空。
清空栈
和清空queue
类似,stack
没有clear()
函数,但是可以通过多种办法来实现。
//方法一:只要栈不为空就一直弹出,直到为空
while(!stk.empty())stk.pop();
//方法二:直接赋值一个新的stack,默认为空栈
stk = stack<int>();
交换栈
语法:stk1.swap(stk2)
,返回值为void()
,复杂度O(1)
。
stack<int> s, t;
s.emplace(1);
t.emplace(2);
cout << s.top() << '\n';// 1
s.swap(t);
cout << s.top() << '\n';// 2
常用函数总结
push(x)
将元素x入栈emplace(x)
在栈顶构造元素x,并入栈(可以简单理解push()和emplace()差别不大)pop()
无参数,将栈顶元素弹出size()
返回栈的大小(元素个数)empty()
返回bool值表示栈是否为空stk1.swap(stk2)
交换两个栈
补充知识
栈在处理一些问题的时候非常好用,比如在做深度优先搜索dfs
的时候,需要需要用到栈的思想,其中节点的遍历顺序可以用栈顺序表示。
同时利用栈可以构造一些特殊的数据结构比如单调栈
从而求出一些特殊的东西,比如最大上升/下降子序列
,从而优化一些dp
问题。
相关文章
- C++学习——c++逗号操作符说明(附加全部运算符优先级)
- EasyC++61,this指针
- c++语言截取字符串,详解C++ string常用截取字符串方法
- 深入理解C++11_c++ string char
- C++20 读书笔记(2)
- 类外实现成员函数的好处(C++)
- C++stl库_c++库
- c++界面开发工具_visual c++界面设计教程
- list/forward_list-C++容器
- C++教程系列之-01-C++概述与NOIP案例
- C++智能指针
- C++字符串加密_c++字符串连接函数
- 简单的Python调用C++程序
- c++中的std::stod, stCPP程序说明std::stod():stof, std::stold
- C/C++ 使用Socket模拟远程CMD
- OpenTime做最称心的C++开发时间库
- [C++STL教程]4.map超强的容器,它终于来了!零基础都能理解的入门教程
- [C++STL教程]1.vector容器是什么?可能是全网最好的教程
- 【错误记录】Ubuntu 下 VSCode 编译报错 ( 无法生成和调试,因为活动文件不是 C 或 C++ 源文件。终端进程启动失败(退出代码: -1)。终端将被任务重用,按任意键关闭。 )
- c++基础篇之C++ 模板
- 开心档之C++ STL 教程
- C/C++在Java、Android和Objective-C三大平台下实现混合编程详解编程语言
- 基于 VC 和 MySQL 创建应用程序的简单教程(vc++ mysql)
- C++你可能不知道地方小结
- 浅析C/C++中sort函数的用法