ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 技术分享
  3. 学科学习
  4. 正文

[C++STL教程]3.stack栈入门简明教程,小白都能理解~

2023年3月16日 28点热度 0人点赞 0条评论

在学习之前,先了解一下什么是stack。

std::stack 类是容器适配器,它给予程序员栈的功能——特别是 FILO (先进后出)数据结构。
该类模板表现为底层容器的包装器——只提供特定函数集合。栈从被称作栈顶的容器尾部推弹元素。

FILO指的是First In Last Out,也就是说第一个进来的,是最后一个出去的。我们可以将stack理解为一个上端开口的铁箱子,我们可以从顶部拿出物品或放入物品,且记录物品个数。

stack仅维护一个栈顶,意味着我们只能从一端对数据进行操作。

本文仅从入门和实用角度介绍stack的用法,主要针对初学者或竞赛向。如有不严谨的地方欢迎指正!

🎈 作者:Eriktse
🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀
🎈 个人博客:www.eriktse.com

初始化

在使用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问题。

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ C++STL教程 stack STL 数据结构 数据结构与算法 栈
最后更新:2023年3月17日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 初始化
  • 入栈
  • 出栈
  • 获取栈顶元素
  • 获取栈的大小
  • 判断栈是否为空
  • 清空栈
  • 交换栈
  • 常用函数总结
  • 补充知识

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号