java 實現 stack詳解及例項程式碼

NO IMAGE

棧是限制插入和刪除只能在一個位置上進行的 List,該位置是 List 的末端,叫做棧的頂(top),對於棧的基本操作有 push 和 pop,前者是插入,後者是刪除。

棧也是 FIFO 表。

棧的實現有兩種,一種是使用陣列,一種是使用連結串列。


public class MyArrayStack<E> {
private ArrayList<E> list = new ArrayList<>();
public void push(E e) {
list.add(e);
}
public E pop() {
return list.remove(list.size() - 1);
}
public E peek() {
return list.get(list.size() - 1);
}
public boolean isEmpty() {
return list.size() == 0;
}
}
public class MyLinkStack<E> {
LinkedList<E> list = new LinkedList<>();
public void push(E e) {
list.addLast(e);
}
public E pop() {
return list.removeLast();
}
public E peek() {
return list.getLast();
}
public boolean isEmpty() {
return list.size() == 0;
}
}

棧的應用

平衡符號

給定一串程式碼,我們檢查這段程式碼當中的括號是否符合語法。

例如:[{()}] 這樣是合法的,但是 [{]}() 就是不合法的。

如下是測試程式碼:


public class BalanceSymbol {
public boolean isBalance(String string) {
MyArrayStack<Character> stack = new MyArrayStack<>();
char[] array = string.toCharArray();
for (char ch : array) {
if ("{[(".indexOf(ch) >= 0) {
stack.push(ch);
} else if ("}])".indexOf(ch) >= 0) {
if (isMatching(stack.peek(), ch)) {
stack.pop();
}
}
}
return stack.isEmpty();
}
private boolean isMatching(char peek, char ch) {
if ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == ')')) {
return true;
}
return false;
}
public static void main(String[] args) {
BalanceSymbol symbol = new BalanceSymbol();
String string = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol();}";
String string2 = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol([);}]";
System.out.println(symbol.isBalance(string));
System.out.println(symbol.isBalance(string2));
}
}

字尾表示式

例如一個如下輸入,算出相應的結果,

3 2 3 * 2 = ?

這個在計算順序上不同會產生不同的結果,如果從左到右計算結果是 16,如果按照數學優先順序計算結果是 11。

如果把上述的中綴表示式轉換成字尾表示式:

3 2 3 2 *

如果使用字尾表示式來計算這個表示式的值就會非常簡單,只需要使用一個棧。

每當遇到數字的時候,把數字入棧。

每當遇到操作符,彈出2個元素根據操作符計算後,入棧。

最終彈出棧的唯一元素就是計算結果。


/**
* 簡化版本,每個運算元只一位,並且假設字串合法
*/
public class PostfixExpression {
public static int calculate(String string) {
MyArrayStack<String> stack = new MyArrayStack<>();
char[] arr = string.toCharArray();
for (char ch : arr) {
if ("0123456789".indexOf(ch) >= 0) {
stack.push(ch   "");
} else if (" -*/".indexOf(ch) >= 0) {
int a = Integer.parseInt(stack.pop());
int b = Integer.parseInt(stack.pop());
if (ch == ' ') {
stack.push((a   b)   "");
} else if (ch == '-') {
stack.push((a - b)   "");
} else if (ch == '*') {
stack.push((a * b)   "");
} else if (ch == '/') {
stack.push((a / b)   "");
}
}
}
return Integer.parseInt(stack.peek());
}
public static void main(String[] args) {
System.out.println(calculate("32 32* "));
}
}

中綴表示式轉換成字尾表示式

假設只執行 ,-,*,/,() 這幾種表示式。並且表示式合法。

a b * c – (d * e f) / g 轉換後的字尾表示式如下:

a b c * d e * f g / –

使用棧中綴轉字尾步驟如下:

當讀到運算元立即把它輸出
如果遇到操作符入棧,如果遇到的左括號也放到棧中
如果遇到右括號,就開始彈出棧元素,直到遇到對應的左括號,左括號只彈出不輸出。
如果遇到其他符號,那麼從棧中彈出棧元素知道發現優先順序更低的元素為止。


import java.util.HashMap;
import java.util.Map;
public class ExpressionSwitch {
private static Map<Character, Integer> map = new HashMap<Character, Integer>();
static {
map.put(' ', 0);
map.put('-', 1);
map.put('*', 2);
map.put('/', 3);
map.put('(', 4);
}
private static char[][] priority = {
// 當前操作符
//       -  *  /  ( 
/* 棧   */{ '>', '>', '<', '<', '<'},
/* 頂 - */{ '>', '>', '<', '<', '<'},
/* 操 * */{ '>', '>', '>', '>', '<'},
/* 作 / */{ '>', '>', '>', '>', '<'},
/* 符 ( */{ '<', '<', '<', '<', '<'},
};
public static String switch1(String string) {
StringBuilder builder = new StringBuilder();
char[] arr = string.toCharArray();
MyArrayStack<Character> stack = new MyArrayStack<>();
for (char ch : arr) {
if ("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch) >= 0) {
builder.append(ch);
} else if ('(' == ch) {
stack.push(ch);
} else if (')' == ch) {
while (true && !stack.isEmpty()) {
char tmp = stack.pop();
if (tmp == '(') {
break;
} else {
builder.append(tmp);
}
}
} else {
while (true) {
if (stack.isEmpty()) {
stack.push(ch);
break;
}
char tmp = stack.peek();
if (isPriorityHigh(tmp, ch)) {
builder.append(stack.pop());
} else {
stack.push(ch);
break;
}
}
}
}
while(!stack.isEmpty()) {
builder.append(stack.pop());
}
return builder.toString();
}
private static boolean isPriorityHigh(char tmp, char ch) {
return priority[map.get(tmp)][map.get(ch)] == '>';
}
public static void main(String[] args) {
System.out.println(switch1("a b*c-(d*e f)/g"));
}
}

通過此文,希望大家對Java stack 的知識掌握,謝謝大家對本站的支援!

您可能感興趣的文章:

java堆疊類使用例項(java中stack的使用方法)JAVA Stack詳細介紹和示例學習Java ArrayDeque實現Stack的功能java8 集合之Stack詳解及例項java中stack(棧)的使用程式碼例項Java集合Stack原始碼詳解