java 完成 stack詳解及實例代碼。本站提示廣大學習愛好者：（java 完成 stack詳解及實例代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是java 完成 stack詳解及實例代碼正文
棧是限制拔出和刪除只能在一個地位長進行的 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 的常識控制，感謝年夜家對本站的支撐！
