Stack เป็นการจัดเก็บข้อมูลในแบบที่เรียกว่า LIFO : Last-In First Out (เข้าหลัง ออกก่อน) กองซ้อนๆ กันเป็นชั้นๆ
การ Push เป็นการใส่ข้อมูลเข้าไป ในส่วนบนสุดของ Stack
ภาพจาก : http://www.javamadesoeasy.com/2015/01/stacks.html
การ Pop เป็นการลบ ข้อมูลจาก Stack จากส่วนบนสุด
เพื่อให้เข้าใจการใช้งานและประโยชน์ของ Stack ลองตัวอย่างตามนี้ครับ
Example 1 : การแปลงเลขฐานสิบให้เป็นฐานสองโดยการใช้ Stack
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
import java.util.Stack; public class ConvertToBinary { public static void main(String[] args) { if(args.length == 0){ System.exit(1); } Stack<Integer> binaryStack = new Stack<Integer>(); int number = Integer.parseInt(args[0]); int remainder ; System.out.println("Base 10 : \t" + number); while (number!=0){ remainder = number % 2 ; binaryStack.push(remainder) ; number /=2; } System.out.print("Base 2 : \t"); while (!binaryStack.empty()){ System.out.print(binaryStack.pop()); } } } |
ผลลัพธ์
Example 2 : การใช้ Stack ประมวลผลสมการทางคณิตศาสตร์
เช่า (1+2)*((3+4)-5)/6)
มี 2 step หลักๆ ครับ
1. วิธีแปลงนิพจน์ Infix เป็น Postfix
2.ประมวลผล ตาม Postfix ในข้อ 1
ดูการคำนวณ Postfix expression Evaluation
สร้าง class MathSolve ประกอบไปด้วย
Method infixToPostfix แปลงจากสมการคณิตศาสตร์ เป็น posfix expression
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
private char[] infixToPostfix(char[] expression){ System.out.println("Infix : "+new String(expression)); Stack<Character> stack = new Stack<>(); StringBuffer buffer = new StringBuffer(); for (int i = 0; i < expression.length; i++) { System.out.println("exp : "+expression[i]); if (expression[i] == ')') buffer.append(stack.pop()); if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/' ) stack.push(expression[i]) ; if(expression[i] >= '0' && expression[i] <='9') buffer.append(expression[i]); } while(!stack.empty()) buffer.append(stack.pop()); return new String(buffer).toCharArray(); } |
Method solvePostfix ใช้สำหรับคำนวณค่า ตาม postfix ที่ได้จาก method infixToPostfix
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
private Double solvePostfix(char[] postfix){ System.out.println("Postfix : "+new String(postfix)); Stack<Double> calStack = new Stack<>(); Double b , a ; for (int i = 0; i < postfix.length; i++) { System.out.println("postfix: "+postfix[i]); char ch = postfix[i] ; if ('0'<=ch && ch<='9') { calStack.push((double) (ch-'0')); }else { switch (postfix[i]) { case '+': b = calStack.pop(); a = calStack.pop(); calStack.push(a+b); break; case '-': b = calStack.pop(); a = calStack.pop(); calStack.push(a - b); break; case '*': b = calStack.pop(); a = calStack.pop(); calStack.push(a * b); break; case '/': b = calStack.pop(); a = calStack.pop(); calStack.push(a / b); break; case '^': b = calStack.pop(); a = calStack.pop(); calStack.push(Math.pow(a, b)); break; } } } return calStack.pop(); } |
class MathSolve เต็ม
สร้าง Constructor กับ getResult สำหรับใช้งาน class ง่ายๆ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
import java.util.*; public class MathSolve{ private Double result; public MathSolve(String expression){ result = solvePostfix(this.infixToPostfix(expression.toCharArray())) ; } public Double getResult() { return result; } private char[] infixToPostfix(char[] expression){ System.out.println("Infix : "+new String(expression)); Stack<Character> stack = new Stack<>(); StringBuffer buffer = new StringBuffer(); for (int i = 0; i < expression.length; i++) { System.out.println("exp : "+expression[i]); if (expression[i] == ')') buffer.append(stack.pop()); if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/' ) stack.push(expression[i]) ; if(expression[i] >= '0' && expression[i] <='9') buffer.append(expression[i]); } while(!stack.empty()) buffer.append(stack.pop()); return new String(buffer).toCharArray(); } private Double solvePostfix(char[] postfix){ System.out.println("Postfix : "+new String(postfix)); Stack<Double> calStack = new Stack<>(); Double b , a ; for (int i = 0; i < postfix.length; i++) { System.out.println("postfix: "+postfix[i]); char ch = postfix[i] ; if ('0'<=ch && ch<='9') { calStack.push((double) (ch-'0')); }else { switch (postfix[i]) { case '+': b = calStack.pop(); a = calStack.pop(); calStack.push(a+b); break; case '-': b = calStack.pop(); a = calStack.pop(); calStack.push(a - b); break; case '*': b = calStack.pop(); a = calStack.pop(); calStack.push(a * b); break; case '/': b = calStack.pop(); a = calStack.pop(); calStack.push(a / b); break; case '^': b = calStack.pop(); a = calStack.pop(); calStack.push(Math.pow(a, b)); break; } } } return calStack.pop(); } } |
ลอง run ดูครับ main method
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class main { public static void main(String[] args) { String expression = "(3+4)*2" ; MathSolve mathSolve = new MathSolve(expression); Double result = mathSolve.getResult() ; System.out.println("result="+result); } } |
ผลลัพธ์
ref:
https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
http://www.javamadesoeasy.com/2015/01/stacks.html