一、反向输出链表元素
Ⅰ使用递归进行反向输出
package stack;
public class Test2 {static class Node{public String val;public Node next;//构造方法public Node(String val) {this.val = val;this.next = null;}}//利用递归来反向输出链表public static void reverse(Node head){if (head == null){return;}reverse(head.next);System.out.print(head.val+" ");}public static Node build(){Node a = new Node("a");Node b = new Node("b");Node c = new Node("c");Node d = new Node("d");a.next = b;b.next= c;c.next =d ;return a;}public static void main(String[] args) {Node head = build();reverse(head);}
}
Ⅱ利用栈进行链表元素的反向输出
package stack;import java.util.Stack;public class Test2 {static class Node{public String val;public Node next;//构造方法public Node(String val) {this.val = val;this.next = null;}}//利用栈来进行反向输出public static void reversePrint(Node head){//创建栈Stack<Node> stack = new Stack<>();//栈里面放的应该是节点，之后打印才可以通过节点引出他门的val//1.首先判断特殊情况if(head== null){return;}//把链表元素进行入栈操作for(Node cur = head;cur!= null;cur = cur.next){stack.push(cur);}while(!stack.isEmpty()){System.out.print(stack.pop().val);}}public static Node build(){Node a = new Node("a");Node b = new Node("b");Node c = new Node("c");Node d = new Node("d");a.next = b;b.next= c;c.next =d ;return a;}public static void main(String[] args) {Node head = build();reversePrint(head);}
}三、有关stack的oj题
解题思路：
1.准备栈并且遍历字符串中的每个字符
2.如果发现当前字符是左括号，就直接入栈
3.如果发现当前字符是右括号，取出刚才的栈顶元素，用当前的右括号和栈顶左括号去判定匹配
如果是配对就继续往下遍历
如果不配对，返回false
class Solution {public boolean isValid(String s) {//首先创建一个栈 这个栈用来存放字符 所以类型选用的是CharacterStack<Character> stack = new Stack<>();//然后进行入栈操作for(int i =0 ;i<s.length();i++){char c = s.charAt(i);//如果是左括号就入栈if(c=='['||c=='('||c=='{'){stack.push(c);continue;}//如果是右括号，就进行判定括号匹配if(c==']'||c==')'||c=='}'){//取出栈顶元素//如果栈为空，无法取到栈顶//由于当前读到了一个右括号，要求必须得在栈里面有一个匹配的左括号//但是栈是空的，说明没有匹配的左括号，那么直接返回falseif(stack.isEmpty()){return false;}//取出栈顶元素char top = stack.pop();if(top =='['&& c==']'){continue;}if(top =='('&&c==')'){continue;}if(top =='{'&& c =='}'){continue;}//其他情况，匹配失效return false;}}//整个循环结束，再来检查栈是否为空//如果栈为空，说明所有括号都匹配成功//如果栈不为空，说明还有未匹配的左括号if(stack.isEmpty()){return true;}return false;}
}
class Solution {public static Boolean isNum(String token){//如果token是运算符，就返回false，否则就返回trueif(token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){return false;}return true;}public int evalRPN(String[] tokens) {//1.准备一个栈，用来存放操作数Stack<Integer> stack = new Stack<>();//2.遍历tokens，取出每个元素for(String token:tokens){//3.判断token是数字if(isNum(token)){//直接入栈stack.push(Integer.parseInt(token));continue;}//4.判定token是运算符//出栈两个元素，先出栈的是第二个操作数，后出栈的是第一个操作数int num2 = stack.pop();int num1 = stack.pop();//5.判定当前的运算符是哪个并且进行运算把得到的结果重新入栈if(token.equals("+")){stack.push(num1+num2);}else if(token.equals("-")){stack.push(num1-num2);}else if(token.equals("*")){stack.push(num1*num2);}else if(token.equals("/")){stack.push(num1/num2);}}//最终整个表达式的结果就是栈里的唯一一个元素return stack.pop();}
}
解题思路：1.先有一个栈
2.遍历pushA，把每个元素，依次出栈
3.在每次入栈一个元素之后，都拿着popA进行判定
a)检测栈是否未空
b)如果栈不为空，判定栈顶元素是不是等于popA的当前元素
c)如果发现符合上述要求
出栈，并且增加popA的下标
出栈成功，回到(a)继续循环处理
d）如果不符合上述要求，回到2.继续遍历下一个pushA元素
4.pushA遍历完毕之后，如果栈为空，说明当前的结果就是true，如果栈不为空，说明结果就是false。
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code here//1.准备一个栈Stack<Integer> stack = new Stack<>();//2.针对pushV进行遍历int pushIndex =0;int popIndex = 0;for(;pushIndex <pushV.length;pushIndex++){//3.把当前的pushIndex指向的元素入栈stack.push(pushV[pushIndex]);//4.拿着popV的当前元素和栈顶进行比较，循环比较的过程，只要比较成功就出栈，并且进行下次循环//也就是比较popA的下一个元素和栈顶的元素while(!stack.isEmpty() && stack.peek()==popV[popIndex]){stack.pop();popIndex++;}//上述条件不匹配，说明当前popIndex指向的元素和栈顶元素是不一样的//此时就需要再次入栈新的元素找新的机会//此处结束循环进入下次即可}//5.当中整个pushA遍历完毕，说明“所有的机会”都用完了//此时如果栈已经是空了，说明前面popA的元素就都匹配成功；如果栈非空，还有popA的元素是无法匹配的if(stack.isEmpty()){return true;}return false;}
}
class MinStack {private Stack<Integer> stack1 = new Stack<>();private Stack<Integer> stack2 = new Stack<>();public MinStack() {// 这个方法空着就行了, 不需要.}public void push(int val) {// stack1 就是正常入栈.stack1.push(val);// 针对 stack2, 就需要比较 val 和 stack2 栈顶元素的大小, 把小的元素入栈.if (stack2.isEmpty()) {// 如果 stack2 栈为空, 直接入栈.stack2.push(val);return;}int min = stack2.peek();if (val < min) {stack2.push(val);} else {stack2.push(min);}}public void pop() {if (stack1.isEmpty()) {// 在做 OJ 题的时候, 不要抛出异常.return;}// 把这两个栈的元素都出栈.stack1.pop();stack2.pop();}public int top() {// 取正常的栈顶元素.if (stack1.isEmpty()) {// 由于不是 Integer, 无法返回 null. 而且右不能修改人家方法的返回值类型. 此处就返回 0 .return 0;}return stack1.peek();}public int getMin() {// 取 stack2 栈顶元素.if (stack2.isEmpty()) {return 0;}return stack2.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/