Tumpukan adalah daftar yang membatasi penyisipan dan penghapusan untuk dilakukan hanya dalam satu posisi. Posisi ini adalah akhir dari daftar, yang disebut bagian atas tumpukan. Untuk operasi dasar tumpukan, ada dorongan dan pop. Yang pertama adalah penyisipan dan yang terakhir dihapus.
Tumpukannya juga merupakan meja FIFO.
Ada dua jenis implementasi tumpukan, satu adalah menggunakan array dan yang lainnya adalah menggunakan daftar tertaut.
kelas publik 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; }} kelas publik 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; }} Aplikasi Tumpukan
Simbol Balance
Diberikan serangkaian kode, kami memeriksa apakah tanda kurung dalam kode ini mematuhi sintaks.
Misalnya: [{()}] Ini legal, tetapi [{]} () ilegal.
Berikut ini adalah kode uji:
Public Class BalanceYMBOL {public boolean isalance (string string) {myArrayStack <chorate> stack = myArrayStack baru <> (); char [] array = string.tochararray (); untuk (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) {balancingymbol simbol = new bealancesymbol (); String string = "public static void main (string [] args) {balancingymbol simbol = new bealancesymbol ();}"; String string2 = "public static void main (string [] args) {balancingymbol simbol = new bealancesymbol ([);}]"; System.out.println (simbol.isbalance (string)); System.out.println (simbol.isbalance (string2)); }} Ekspresi sufiks
Misalnya, input berikut menghitung hasil yang sesuai,
3 + 2 + 3 * 2 =?
Ini akan menghasilkan hasil yang berbeda dalam urutan perhitungan yang berbeda. Jika hasil perhitungan adalah 16 dari kiri ke kanan, dan jika hasil perhitungan adalah 11 menurut prioritas matematika.
Jika ekspresi infix di atas dikonversi menjadi ekspresi akhiran:
3 2 + 3 2 * +
Akan sangat sederhana untuk menghitung nilai ekspresi ini menggunakan ekspresi akhiran, cukup gunakan tumpukan.
Setiap kali angka ditemui, letakkan nomor di tumpukan.
Setiap kali operator ditemui, dua elemen muncul untuk menghitung sesuai dengan operator dan kemudian meletakkannya di tumpukan.
Satu -satunya elemen yang muncul tumpukan adalah hasil perhitungan.
/*** Versi yang disederhanakan, setiap operan hanya satu, dan dengan asumsi bahwa string itu legal*/kelas publik postfixexpression {public static int countulate (string string) {myarraystack <string> stack = myArraystack baru <> (); char [] arr = string.tochararray (); untuk (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) + ""); } lain jika (ch == ' -') {stack.push ((a - b) + ""); } else if (ch == ' *') {stack.push ((a * b) + ""); } lain jika (ch == ' /') {stack.push ((a / b) + ""); }} return integer.parseint (stack.peek ()); } public static void main (string [] args) {System.out.println (Hitung ("32+32*+")); }} Mengubah ekspresi infix menjadi ekspresi akhiran
Misalkan hanya ekspresi +, -, *, /, () yang dijalankan. Dan ekspresinya legal.
A + B * C - (D * E + F) / G Ekspresi akhiran yang dikonversi adalah sebagai berikut:
ABC * + de * f + g / -
Langkah -langkah untuk menggunakan stack infix untuk mengonversi sufiks adalah sebagai berikut:
impor java.util.hashmap; import java.util.map; ekspresi kelas publikwitch {peta statis privat <karakter, integer> peta = hashmap baru <karakter, integer> (); static {map.put ('+', 0); peta.put ('-', 1); peta.put ('*', 2); peta.put ('/', 3); Map.put ('(', 4);} private static char [] [] prioritas = {// operator saat ini // + - */(/ * stack + */{'>', '>', '<', '<', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', ', '>', '>', '<'},/ * Make/ */{'>', '>', '>', '>', '<'},/ * karakter ( */{'<', '<', '<', '<', '<'},} public switch1; string.tochararray (); stack.push (ch);} else if (')' == ch) {while (true &&! stack.isempty ()) {char tmp = stack.pop (); Stack.push (CH); } return builder.toString (); } private static boolean ispriorityhigh (char tmp, char ch) {return prioritas [map.get (tmp)] [map.get (ch)] == '>'; } public static void main (string [] args) {System.out.println (switch1 ("a+b*c- (d*e+f)/g")); }}Melalui artikel ini, saya harap semua orang telah menguasai pengetahuan Java Stack. Terima kasih atas dukungan Anda untuk situs web ini!