当前位置 博文首页 > ljy320672584的博客：LeetCode笔记---Java语言-＞递归与栈-＞844
栈的简述：
栈：FILO先进后出，后进先出。从哪入从哪出
栈适合解决的问题：可以处理具有完全包含关系的问题（表达式求值，递归，括号匹配，二叉树遍历）。
栈的典型应用场景：
场景一：操作系统中的线程栈
场景二：表达式求值
此题思路
遇到退格出栈
此题也是针对后面数据的操作，所以我们采用栈这个数据结构，当我们遇到退格符号时，就将栈顶元素弹出。不是退格符号，就将元素压入。
class Solution {
public boolean backspaceCompare(String s, String t) {
LinkedList<Character> s1 = new LinkedList();//保存s字符串的栈
LinkedList<Character> t1 = new LinkedList();//保存t字符串的栈
/*遍历s字符串*/
for(int i = 0;i<s.length();i++){
if(s.charAt(i)=='#'){//遇到退格，只要栈不为空，就将栈顶元素弹出
if(!s1.isEmpty())
s1.pop();
}else{
s1.push(s.charAt(i));//压入元素
}
}
/*遍历t字符串*/
for(int i = 0;i<t.length();i++){
if(t.charAt(i)=='#'){//遇到退格，只要栈不为空，就将栈顶元素弹出
if(!t1.isEmpty())
t1.pop();
}else{
t1.push(t.charAt(i));//压入元素
}
}
if(s1.size()!=t1.size())//如果两个栈大小不一样，那么肯定两者不相等
return false;
while(!s1.isEmpty()){//循环条件，两者大小一致，同时弹出元素，所以判断其中一个是否为空就行
if(s1.pop()!=t1.pop())//有一个位置上的元素不相同就返回false
return false;
}
return true;
}
}
