Tumpukan Jawa

Stack di Java biasanya berarti kelas dari Collection Framework yang mengimplementasikan antarmuka Daftar. Ini bekerja berdasarkan prinsip struktur data Stack, yang digunakan untuk mengatur salah satu jenis memori. Juga bisa menjadi bagian dari memori untuk menyimpan data, Pada artikel ini kita akan memperhatikan pertama-tama kelas Stack , pertimbangkan metodenya dan berikan contoh. Tetapi kami juga akan berbicara tentang struktur data seperti Stack dan kegunaannya.

Apa itu Struktur Data Tumpukan

Pertama-tama, mari kita lihat sekilas apa itu struktur data tumpukan. Ini adalah struktur data linier yang didasarkan pada prinsip Last-in-First-out (LIFO). Ini semacam anti-antrian. Bayangkan setumpuk kartu atau setumpuk buku di dalam sebuah kotak. Buku yang pertama kali Anda taruh di tumpukan ada di bawah, dan yang pertama kita keluarkan dari kotak adalah buku yang ada di atas - yaitu, yang terakhir masuk ke dalam kotak. Berikut adalah gambar gif untuk menunjukkan prinsip ini. Apa yang terjadi di sini? Kami memiliki termos di mana hanya satu bola yang dapat dipukul pada satu waktu. Yang pertama di dalam labu adalah bola oranye, lalu ungu, dan terakhir hijau (saya minta maaf kepada mereka yang mengetahui nama yang lebih akurat dari warna ini). Namun untuk mengekstrak bola oranye dari tumpukan labu kami, pertama-tama kita perlu mengekstrak bola yang sampai di sana terakhir (yang hijau), lalu yang kedua dari belakang (tetapi pada saat ekstraksi itu adalah yang terakhir). satu). Struktur data tumpukan di Java atau di tempat lain dalam pemrograman memiliki dua operasi terpenting, push dan pop . Operasi push memasukkan elemen ke dalam tumpukan dan operasi pop menghapus elemen dari bagian atas tumpukan.

Untuk apa struktur data Stack?

Salah satu penggunaan stack yang paling penting adalah mengatur panggilan subrutin. Titik panggilan pada tumpukan menyimpan alamat pengirim dari subrutin setelah diakhiri (dan mungkin parameter yang diteruskan). Dengan setiap pemanggilan subrutin bersarang (termasuk rekursif), alamat pengirim baru ditambahkan ke tumpukan. Dengan setiap operasi pengembalian dari subrutin (kembali), alamat pengirim dihapus dari tumpukan dan kontrol ditransfer ke sana. Aplikasi ini sangat penting untuk pemrograman sehingga di sebagian besar prosesor, tumpukan pengembalian diimplementasikan di perangkat keras di set instruksi. Namun, dalam kasus lain, tumpukan harus dimodelkan pada struktur data yang lebih umum.

Kerangka Pengumpulan Kelas Java Stack

Di Java Stack Class adalah kelas dari kerangka Koleksi yang mengimplementasikan antarmuka Daftar dan memperluas kelas Vektor. Itu juga mengimplementasikan Koleksi antarmuka, Iterable, Cloneable, Serializable. Seperti yang mungkin sudah Anda duga, kelas ini mewakili tumpukan objek LIFO. Inilah panggilan ke konstruktor kelas Stack , yaitu pembuatan objek kelas ini.

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

Di mana E adalah jenis Objek.

Metode Tumpukan Java

Kelas ini hanya memiliki satu konstruktor default dan semua metode kelas Vektor . Plus, Stack memiliki 5 metodenya sendiri:

• boolean empty() metode ini memeriksa apakah stack kosong atau tidak. Mengembalikan nilai true jika stack kosong, false jika tidak.

• Objek mengintip () metode mengembalikan elemen yang ada di bagian atas tumpukan.

• Object pop() metode mengembalikan elemen yang ada di bagian atas tumpukan dan menghapusnya.

• Push objek (Elemen objek) metode menambahkan elemen yang ditentukan ke bagian atas tumpukan.

• int search(Object element) metode mencari stack untuk elemen yang ditentukan. Jika elemen yang diperlukan ditemukan, "jarak" dari atas (nomor seri) dikembalikan. Jika elemen tidak ditemukan, -1 dikembalikan.

Contoh kode tumpukan

Mari kita buat contoh program yang berfungsi seperti gambar gif diatas. Kami akan meletakkan tiga "bola", oranye, ungu dan hijau, di tumpukan. Mari kita periksa tumpukan untuk kekosongan. Kemudian, kami akan mengekstrak bola dari tumpukan hingga tumpukan 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 dari program ini: Karena Stack diwariskan dari Vector Class dan mengimplementasikan antarmuka List , Stack , selain operasi push dan pop klasik untuk struktur data ini untuk menambahkan dan mengekstraksi elemen, juga memiliki standar untuk operasi add() dan remove() struktur daftar. Dalam contoh kita, menambahkan elemen dapat diimplementasikan dengan cara yang sama menggunakan metode add() . Namun Anda dapat mengekstrak menggunakan remove() hanya dengan elemen yang ditentukan, yang tidak masuk akal untuk struktur data tumpukan.

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 tentunya akan sama persis.

Bagaimana dengan implementasi Stack Anda sendiri?

Anda dapat membuat struktur data tumpukan Anda sendiri di Java menggunakan array atau kelas daftar tertaut. Dalam kasus pertama, larik sel kontinu dialokasikan untuk menyimpan nilai dalam memori, yang digunakan sesuai kebutuhan. Yang kedua, untuk setiap elemen tumpukan, satu blok memori dipesan, cukup untuk menyimpan nilai dan referensi ke elemen tumpukan sebelumnya dan berikutnya. Implementasi berbasis array lebih sederhana, lebih efisien, dan lebih hemat memori, tetapi memerlukan pengetahuan sebelumnya tentang batas ukuran tumpukan dan dapat menyebabkan bug yang sulit ditemukan. Implementasi berbasis daftar lebih kuat tetapi kurang efisien. Mari kita buat implementasi tumpukan berbasis array sederhana. Ini akan mencakup fungsi.

• push — metode yang akan memastikan penambahan elemen (di posisi teratas)

• pop — metode yang akan memberikan penghapusan elemen (dari posisi teratas)

• readTop — metode yang akan mengembalikan nilai elemen yang berada di posisi teratas

• sEmpty — metode yang akan memeriksa tumpukan untuk kekosongan

• isFull — metode yang akan memeriksa apakah array tempat kita menyimpan tumpukan 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 terapkan contoh dengan tiga bola berdasarkan tumpukan kita:

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 perhatikan lebih dekat, variabel teratas sebenarnya berisi indeks elemen terakhir, dan referensi ke objek tetap ada di dalam array. Jadi implementasi ini perlu beberapa perbaikan. Pikirkan tentang cara termudah untuk melakukan ini.

Haruskah kita menggunakan Java Stack?

Faktanya, Java Stack , seperti vektor induknya, adalah kelas warisan. Sebaliknya, kelas ArrayList biasanya digunakan. ArrayList tidak disinkronkan saat Vector disinkronkan. Itu berarti dengan Vector hanya satu utas yang dapat mengakses kode, sedangkan ArrayList dapat bekerja dengan banyak utas. Juga, ArrayList lebih efisien dan lebih cepat. Jadi kemungkinan besar Anda akan melihat kelas ini hanya dalam kode lawas. Tetapi struktur data Stack sangat sering digunakan dalam pemrograman.