一、反向輸出鏈表元素
Ⅰ使用遞歸進行反向輸出
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();*/