赞
踩
A: 1,4,3,2
B: 2,3,4,1
C: 3,1,4,2
D: 3,4,2,1
思路:这个题的关键是进栈过程中可以出栈
A: 12345ABCDE
B: EDCBA54321
C: ABCDE12345
D: 54321EDCBA
思路:栈遵循先进后出的原则
思路:如果是数字就放入栈中;如果是操作符,就取出栈顶两个元素,进行运算,把结果写回到栈中,继续遍历字符串;栈中最后的元素就是表达式的结果
public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); //遍历字符串 for (String x : tokens) { if (isOperation(x)){ //x是一个数字字符串 int num2 = stack.pop(); int num1 = stack.pop(); switch (x){ case "+": stack.push(num1 + num2); break; case "-": stack.push(num1 - num2); break; case "*": stack.push(num1 * num2); break; case "/": stack.push(num1 / num2); break; } }else { //x不是运算符 stack.push(Integer.parseInt(x));//将x转化为整数 } } return stack.pop(); } //判断字符串是不是操作符 public boolean isOperator(String s){ if(s.equals("+") ||s.equals("-") ||s.equals("*") ||s.equals("/") ){ return true; } return false; }
思路: (1)遍历字符串,如果是左括号,就入栈 (2)如果是右括号,则看栈顶元素是不是和我是匹配的,如果匹配就出栈
(3)直到栈为空且字符串遍历完成,说明左右括号是匹配的
(4)三种不匹配的情况:①当字符串完成遍历之后,栈还是空的,说明是左括号多;②当遇到右括号之后,发现栈还是空的,说明右括号多;③当遇到右括号,栈顶元素是左括号,但是是不匹配的,说明左右括号是不匹配的
public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for(int i = 0;i < s.length();i++){ char ch = s.charAt(i); if(ch == '(' || ch == '[' || ch == '{' ){ //说明此时是左括号 stack.push(ch); }else{ //判断栈是不是为空,右括号多 if(stack.empty()){ return false; } char top = stack.peek();//此处一定是左括号 if(ch == ')' && top == '(' || ch == ']' && top == '['|| ch == '}'&& top == '{'){ stack.pop(); }else{ //左右括号不匹配 return false; } } } if(!stack.empty()){ //左括号多 return false; } return true; }
思路:找到出栈的条件(当栈顶元素和popA数组j所指的元素相同的时候就可以出栈了),注意栈不可为空并且j不要越界
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;//遍历popA数组
for(int i = 0; i < pushA.length; i++){
stack.push(pushA[i]);
//判断出栈的时候
while(j < popA.length && !stack.empty() && stack.peek() == popA[j]){
stack.pop();
j++;
}
}
return stack.empty();
}
public void printList(Node head){
if (head == null){
return;
}
if (head.next == null){
System.out.print(head.val+" ");
return;
}
printList(head.next);
System.out.print(head.val+ " ");
}
思路:遍历链表,让链表中的元素一个一个入栈,之后再让栈不为空的情况之下一个一个弹出栈中的元素
public void printList1(){
Stack<Node> stack = new Stack<>();
Node cur = head;
while (cur != null){
stack.push(cur);
cur = cur.next;
}
while (!stack.empty()){
Node tmp = stack.pop();
System.out.print(tmp.val + " ");
}
System.out.println();
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。