- 1.Java中栈的使用（目前已不推荐使用）
- 2.Deque双端队列实现栈结构（优先使用）
- 2.1等效方法
- 3。题解
为什么用栈这种数据结构解题？
比如上题第二个例子可能存在括号中还有括号的情况，所以先把数字之前的元素先放入栈中，等到取到数字再进行元素计数操作。
所以只有括号出现的时候我们才使用栈来操作，“（”这个字符作为调用栈的信号。
栈：后进先出
Stack stack = new Stack();
//判断Stack是否为空
stack.empty();
//取栈顶值
stack.peek();
//进栈
stack.pop();
public class StackDemo {
public static void main(String[] args) {
//实例化一个Stack
Stack stack = new Stack();
//判断Stack是否为空。 因为栈中无元素，所以输出false
System.out.println(stack.empty());
//将1压入栈
stack.push(new Integer(1));
//输出true
System.out.println(stack.empty());
//peek()：输出栈顶元素。
System.out.println(stack.peek());
//将2压入栈
stack.push(new Integer(2));
stack.push(new Integer(3));
System.out.println(stack.peek());//3
stack.pop();//将3弹出
System.out.println(stack.peek());//2
int a = stack.size();
System.out.println("栈中元素的个数"+a);
System.out.println("判断栈中是否无元素"+stack.isEmpty());
}
}
20. 有效的括号
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
for(int i = 0;i
2.Deque双端队列实现栈结构（优先使用）
726. 原子的数量
输入: formula = "Mg(OH)2"
输出: "H2MgO2"
解释:
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。
例子2
输入：formula = "K4(ON(SO3)2)2"
输出："K4N2O14S4"
解释：
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。
Deque： double ended queue 双端队列，既可以当做栈使用，也可以当作队列使用。
Queue是队列，只能一头进，一头出。
Deque 既可以添加到队尾，也可以添加到队首，既可以从队首获取，也可以从队尾获取。
public static void main(String[] args) {
Deque deque = new linkedList<>();
//添加元素到队尾
deque.offerLast("a");
deque.offerLast("b");
deque.offerLast("c");
//c->b->a
System.out.println(deque.peekFirst());//a
System.out.println(deque.peekLast());//c
}
add()和offer()的区别
当超出队列界限的时候，add()方法抛出异常，offer()方法返回false。
PS:offer()实际上就是offerLast();
2.1等效方法
Stack Deque push() addFirst() pop() removeFirst() peek() peekFirst()
3。题解
class Solution {
int i, n;
String formula;
public String countOfAtoms(String formula) {
this.i = 0;
this.n = formula.length();
this.formula = formula;
//初始化一个栈
Deque> stack = new linkedList>();
//压入一个哈希表
stack.push(new HashMap());
while (i < n) {
char ch = formula.charAt(i);
if (ch == '(') {//如果是（）则把元素全部放到栈顶的Map里
i++;
stack.push(new HashMap());
// 将一个空的哈希表压入栈中，准备统计括号内的原子数量
} else if (ch == ')') {
i++;
int num = parseNum(); // 括号右侧数字
Map popMap = stack.pop(); // 弹出括号内的原子数量
Map topMap = stack.peek();
for (Map.Entry entry : popMap.entrySet()) {
String atom = entry.getKey();
int v = entry.getValue();
topMap.put(atom, topMap.getOrDefault(atom, 0) + v * num);
// 将括号内的原子数量乘上 num，加到上一层的原子数量中
}
} else {//这一部分就是对栈顶的操作（思维盲区）
String atom = parseAtom();
int num = parseNum();
//查看栈顶元素
Map topMap = stack.peek();
//把原子加入到栈顶元素
//getOrDefault如果没有元素则返回0；
topMap.put(atom, topMap.getOrDefault(atom, 0) + num); // 统计原子数量
}
}
Map map = stack.pop();
TreeMap treeMap = new TreeMap(map);
StringBuffer sb = new StringBuffer();
for (Map.Entry entry : treeMap.entrySet()) {
String atom = entry.getKey();
int count = entry.getValue();
sb.append(atom);
if (count > 1) {
sb.append(count);
}
}
return sb.toString();
}
public String parseAtom() {
StringBuffer sb = new StringBuffer();
sb.append(formula.charAt(i++)); // 扫描首字母
while (i < n && Character.isLowerCase(formula.charAt(i))) {
sb.append(formula.charAt(i++)); // 扫描首字母后的小写字母
}
return sb.toString();
}
public int parseNum() {
if (i == n || !Character.isDigit(formula.charAt(i))) {
return 1; // 不是数字，视作 1
}
int num = 0;
while (i < n && Character.isDigit(formula.charAt(i))) {
num = num * 10 + formula.charAt(i++) - '0'; // 扫描数字
}
return num;
}
}
作者：LeetCode-Solution
