剑指offer-栈总结

---

---

前言

栈是一种常用的数据结构，它最大的特点是“后入先出”，即后
进入栈中的元素最先出来。为了确保“后入先出”的顺序，栈的插入
和删除操作都发生在栈顶。
栈的操作可以用日常生活中的洗碗来理解。假设将洗好的碗堆成
一摞。新洗的碗总是放在最上面，每次需要用碗的时候也总是从最上
面拿。这一摞碗就相当于一个栈，放碗、取碗操作都发生在一摞碗的
顶端，最后放入的碗最先被取走。

先进后出

题型

适用于集合或者数组中有元素出栈入栈顺序的题目

方法

主要判断好出栈和入栈的条件

以 剑指 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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结

本章介绍了栈这种常见的数据结构。栈的插入、删除操作都发生
在栈的顶部。在栈中插入、删除数据的顺序为“后入先出”，即最后
添加的数据最先被删除。Java的类型Stack实现了栈的功能。
在分析解决问题时，如果一个数据集合的添加、删除操作满足
“后入先出”的特点，那么可以用栈来实现这个数据集合