Timbunan Java

Tindanan dalam Java biasanya bermaksud kelas daripada Rangka Kerja Koleksi yang melaksanakan antara muka Senarai. Ia berfungsi pada prinsip struktur data Stack, yang digunakan untuk mengatur salah satu jenis memori. Juga ia boleh menjadi sebahagian daripada ingatan untuk menyimpan data, Dalam artikel ini kita akan memberi perhatian pertama sekali kepada kelas Stack , pertimbangkan kaedahnya dan berikan contoh. Tetapi kita juga akan bercakap tentang struktur data seperti Stack dan untuk kegunaannya.

Apakah Struktur Data Tindanan

Pertama sekali, mari kita lihat dengan cepat apa itu struktur data tindanan. Ia ialah struktur data linear yang berdasarkan prinsip Keluar-Masuk-Masuk Dahulu (LIFO). Ia agak anti beratur. Bayangkan dek kad atau timbunan buku di dalam kotak. Buku yang anda masukkan ke dalam tindanan dahulu adalah di bahagian bawah, dan yang pertama yang akan kami keluarkan dari kotak ialah buku yang berada di bahagian atas - iaitu, buku yang terakhir masuk ke dalam kotak. Berikut ialah gambar gif untuk menunjukkan prinsip ini. Apa yang berlaku di sini? Kami mempunyai kelalang di mana hanya satu bola boleh memukul pada satu masa. Yang pertama dalam kelalang ialah bola oren, kemudian ungu, dan akhirnya hijau (saya memohon maaf kepada mereka yang tahu nama yang lebih tepat bagi warna-warna ini). Walau bagaimanapun, untuk mengekstrak bola oren dari timbunan kelalang kami, kami perlu mengekstrak bola yang terakhir sampai di sana (yang hijau), kemudian bola yang terakhir terakhir (tetapi pada masa pengekstrakan itu adalah yang terakhir. satu). Struktur data tindanan dalam Java atau tempat lain dalam pengaturcaraan mempunyai dua operasi yang paling penting, push dan pop . Operasi tolak memasukkan elemen ke dalam tindanan dan operasi pop mengalih keluar elemen dari bahagian atas tindanan.

Untuk apa struktur data Stack?

Salah satu kegunaan timbunan yang paling penting ialah untuk mengatur panggilan subrutin. Titik panggilan pada tindanan menyimpan alamat pemulangan daripada subrutin selepas ia ditamatkan (dan mungkin parameter lulus). Dengan setiap panggilan bersarang (termasuk rekursif) subrutin, alamat pemulangan baharu ditambahkan pada timbunan. Dengan setiap operasi pemulangan daripada subrutin (pemulangan), alamat pemulangan dikeluarkan daripada timbunan dan kawalan dipindahkan kepadanya. Aplikasi ini sangat penting untuk pengaturcaraan yang dalam kebanyakan pemproses tindanan kembali dilaksanakan dalam perkakasan dalam set arahan. Walau bagaimanapun, dalam kes lain, timbunan perlu dimodelkan pada struktur data yang lebih umum.

Rangka Kerja Koleksi Kelas Timbunan Java

Dalam Java Stack Class ialah kelas daripada rangka kerja Koleksi yang melaksanakan antara muka Senarai dan memanjangkan kelas Vektor. Ia juga melaksanakan antara muka Collection, Iterable, Cloneable, Serializable. Seperti yang anda mungkin sudah meneka kelas ini mewakili tindanan LIFO objek. Berikut ialah panggilan kepada pembina kelas Stack , iaitu penciptaan objek kelas ini.

Stack<E> stack = new Stack<E>();

Di mana E ialah jenis Objek.

Kaedah Timbunan Java

Kelas ini hanya mempunyai satu pembina lalai dan semua kaedah kelas Vektor . Selain itu, Stack mempunyai 5 kaedah sendiri:

• boolean empty() kaedah menyemak sama ada timbunan kosong atau tidak. Mengembalikan benar jika tindanan kosong, palsu jika tidak.

• Object peek() kaedah mengembalikan elemen yang berada di bahagian atas timbunan.

• Object pop() kaedah mengembalikan elemen yang berada di bahagian atas timbunan dan mengeluarkannya.

• Tolak objek(elemen objek) kaedah menambah elemen yang ditentukan ke bahagian atas timbunan.

• int search(elemen objek) kaedah mencari timbunan untuk elemen yang ditentukan. Jika elemen yang diperlukan ditemui, "jarak"nya dari atas (nombor siri) dikembalikan. Jika elemen tidak dijumpai, -1 dikembalikan.

Contoh kod tindanan

Mari buat contoh program yang berfungsi seperti gambar gif di atas. Kami akan meletakkan tiga "bola", oren, ungu dan hijau, pada timbunan. Mari kita periksa timbunan untuk kekosongan. Kemudian, kami akan mengeluarkan bola dari timbunan sehingga timbunan itu kosong.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Berikut adalah output program ini: Memandangkan Stack diwarisi daripada Kelas Vektor dan melaksanakan antara muka Senarai , Stack , sebagai tambahan kepada operasi tolak dan pop klasik untuk struktur data ini untuk menambah dan mengekstrak elemen, juga mempunyai standard untuk struktur senarai tambah() dan keluarkan() operasi. Dalam contoh kami, menambah elemen boleh dilaksanakan dengan cara yang sama menggunakan kaedah add() . Walau bagaimanapun anda boleh mengekstrak menggunakan remove() hanya dengan elemen yang ditentukan, yang tidak masuk akal untuk struktur data tindanan.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Hasil kerja program, tentu saja, akan sama.

Bagaimana dengan pelaksanaan Stack anda sendiri?

Anda boleh membuat struktur data tindanan anda sendiri dalam Java menggunakan tatasusunan atau kelas senarai terpaut. Dalam kes pertama, tatasusunan sel berterusan diperuntukkan untuk menyimpan nilai dalam ingatan, yang digunakan mengikut keperluan. Dalam yang kedua, untuk setiap elemen timbunan, satu blok memori dipesan, mencukupi untuk menyimpan nilai dan rujukan kepada elemen timbunan sebelumnya dan seterusnya. Pelaksanaan berasaskan tatasusunan adalah lebih mudah, lebih cekap dan lebih cekap memori, tetapi ia memerlukan pengetahuan awal tentang had saiz tindanan dan boleh membawa kepada pepijat yang sukar ditemui. Pelaksanaan berasaskan senarai adalah lebih mantap tetapi kurang cekap. Mari kita buat pelaksanaan berasaskan tatasusunan ringkas bagi timbunan. Ia akan merangkumi fungsi.

• push — kaedah yang akan memastikan penambahan elemen (di kedudukan teratas)

• pop — kaedah yang akan menyediakan penyingkiran elemen (dari kedudukan teratas)

• readTop — kaedah yang akan mengembalikan nilai elemen yang berada di kedudukan teratas

• sEmpty — kaedah yang akan menyemak timbunan untuk kekosongan

• isFull — kaedah yang akan menyemak sama ada tatasusunan kami tempat kami menyimpan timbunan tidak penuh

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;
      
   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());
      
       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

Sekarang mari kita laksanakan contoh dengan tiga bola berdasarkan timbunan kami:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

Outputnya ada di sini: Jika anda melihat dengan teliti, pembolehubah teratas sebenarnya mengandungi indeks elemen terakhir, dan rujukan kepada objek kekal dalam tatasusunan. Jadi pelaksanaan ini memerlukan sedikit penambahbaikan. Fikirkan cara paling mudah untuk melakukan ini.

Patutkah kita menggunakan Java Stack?

Malah, Java Stack , seperti induk Vektornya , ialah kelas warisan. Sebaliknya, kelas ArrayList biasanya digunakan. ArrayList tidak disegerakkan manakala Vektor disegerakkan. Ini bermakna dengan Vektor hanya satu utas pada satu masa boleh mengakses kod, manakala ArrayList boleh berfungsi dengan berbilang utas. Selain itu, ArrayList lebih cekap dan lebih pantas. Jadi kemungkinan besar anda akan melihat kelas ini hanya dalam kod warisan. Tetapi struktur data Stack digunakan dalam pengaturcaraan dengan kerap.