前言
栈是一种常用的数据结构，它最大的特点是“后入先出”，即后
进入栈中的元素最先出来。为了确保“后入先出”的顺序，栈的插入
和删除操作都发生在栈顶。
栈的操作可以用日常生活中的洗碗来理解。假设将洗好的碗堆成
一摞。新洗的碗总是放在最上面，每次需要用碗的时候也总是从最上
面拿。这一摞碗就相当于一个栈，放碗、取碗操作都发生在一摞碗的
顶端，最后放入的碗最先被取走。
先进后出
题型
适用于集合或者数组中有元素出栈入栈顺序的题目
方法
主要判断好出栈和入栈的条件
以 剑指 Offer II 037. 小行星碰撞 为例
一定要想好出栈和入栈的条件
class Solution {
// 使用栈得方法解决(反向大小碰撞只剩下大的)
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
// 迭代数组
for(int num : asteroids){
// 满足入栈条件（只有先+后-，才会进行碰撞）
while(!stack.empty() && stack.peek()>0 && stack.peek()<-num){
stack.pop();
}
// +8,-8这种情况
if(!stack.empty() && num<0 && stack.peek()==-num){
stack.pop();
}else if(num>0 || stack.empty() || stack.peek()<0){
// 先-后+永远不可能相撞
stack.push(num);
}
}
return stack.stream().mapToInt(i->i).toArray();
}
}
总结
本章介绍了栈这种常见的数据结构。栈的插入、删除操作都发生
在栈的顶部。在栈中插入、删除数据的顺序为“后入先出”，即最后
添加的数据最先被删除。Java的类型Stack实现了栈的功能。
在分析解决问题时，如果一个数据集合的添加、删除操作满足
“后入先出”的特点，那么可以用栈来实现这个数据集合
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96165.html
