Stack Struktur Data

Stack (Struktur Data)

    Stack adalah struktur data linear yang mengikuti urutan tertentu dimana operasi dilakukan urutannta mungkin LIFO (last in firs out) atau FILO (first in last out).

       Ada banyak contoh nyata dari tumpukan.perhatikan contoh piring yang ditumpuk satu sama lain dikantin.pelat yang ada dibagian atas adalah yang pertama untuk dilepas,yaitu piring yang telah ditempatkan pada posisi paling bawah tetap ditumpukkan untuk periode waktu terlama.jadi,itu bisa dilihat hanya mengikuti urutan LIFO (last in first out) / FILO (first in last out).

     Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari tumpukan tersebut. Tumpukan dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri tumpukan:

1. TOP merupakan sebutan untuk elemen paling atas dari suatu stack
2. Elemen TOP merupakan elemen yang paling akhir ditambahkan
3. Elemen TOP diketahui
4. penambahan dan penghapusan elemen selalu dilakukan di TOP
5. LIFO

Pemanfaatan tumpukan:

1. Perhitungan ekspresi aritmetika (posfix)
2. algoritme backtraking (runut balik)
3. algoritme rekursif

Pengunaan Stack:

   Pada beberapa literatur menyebutkan bahwa stack umumnya digunakan untuk memisahkan ekspresi aritmatika. Saya pernah mendapat tugas mengubah notasi infix menjadi postfix menggunakan teknik stack. Teman-teman dapat membaca referensi infix-postfix yang menurut saya lengkap dan mudah dipahami disini.

Algortima Stack:

     Dengan memahami contoh yang telah dibahas pada poin sebelumnya, saya pikir cara kerja stack sudah dapat dibayangkan. Sederhananya seperti ini: ketika memasukkan data, uji apakah stack (array) sudah penuh? Jika benar, maka data tidak dapat disimpan. Jika tidak, maka data akan disimpan dan menjadi data yang paling atas dari data sebelumnya. Kemudian bagaimana dengan langkah mengeluarkan data? Sama. Uji apakah stack kosong? Jika benar, maka proses selesai karena tidak ada data yang harus dikeluarkan. Sebaliknya, maka ambil data yang paling akhir (atas) untuk dikeluarkan.

Metode Implementasi pada Stack:

     Ada lima metode penting dalam implementasi stack. Potongan kode berikut saya tulis menggunakan bahasa Java.

push(), berfungsi untuk memasukkan data.

public void push(String value) {

   stack[++top] = value;

}

pop(), berfungsi untuk mengeluarkan data terakhir (atas).

public String pop() {

   return stack[top — ];

}

peek(), berfungsi untuk melihat data yang berada pada tumpukan paling atas (akan dikeluarkan).

public String peek() {

   return stack[top];

}

isEmpty(), berfungsi untuk menguji apakah stack masih kosong.

public boolean isEmpty() {

   return top == -1;

}

isFull(), berfungsi untuk menguji apakah stack telah penuh.

public boolean isFull() {

   return top == max-1;

}

Contoh Implementasi Stack dengan Java:

public class Stack {
 
   private String[] stack;
   private int max;
   private int top;

   public Stack(int size) {
     max = size;
     stack = new String[max];
     top = -1;
   }

   public void push(String value) {
      stack[++top] = value;
   }

   public String pop() {
      return stack[top — ];
   }

   public String peek() {
      return stack[top];
   }

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

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

   public static void main(String[] args) {
     Stack s = new Stack(5);

     // push data
     s.push(“FISIKA”);
     s.push(“KIMIA”);
     s.push(“MATEMATIKA”);
     s.peek(); // MATEMATIKA
     s.push(“B. INDONESIA”);
     s.push(“BIOLOGI”);
     s.isEmpty(); // false
     s.isFull(); // true
     s.pop(); // remove BIOLOGI
     s.isFull(); // false
  }
}

Penjelasan Code:

private String[] stack;

private int max;

private int top;

    Kode diatas merupakan bagian dari pendeklarasian array dan variabel. Array akan digunakan sebagai stack, variabel max sebagai batas kapasitas array dan variabel top sebagai pointer data yang paling akhir.

public Stack(int size) {

   max = size;

   stack = new String[max];

   top = -1;

}

  Selanjutnya, kode diatas merupakan sebuah konstruktor yang digunakan untuk menginisialisasi variabel dan menjadi metode yang pertama dijalankan ketika dilakukan instance object. Pemberian nilai -1 pada variabel top adalah indikator bahwa array masih kosong. Seperti yang diketahui bahwa array mulai menyimpan data pertama pada indeks ke-nol.

public void push(String value) {

   stack[++top] = value;

}

   Lalu kode diatas menjelaskan mengenai proses memasukkan data ke dalam array dengan indeks increment dari nilai variabel top. Apabila sebelumnya nilai dari top adalah -1, maka (-1) + 1 = 0. Data pertama akan disimpan pada indeks ke-0 dan seterusnya.

public String pop() {

   return stack[top — ];

}

   Kode diatas digunakan mengeluarkan data dari urutan paling akhir dan melakukan decrement nilai dari variabel top. Nilai data yang dikeluarkan juga di-return dalam metode pop.

public String peek() {

   return stack[top];

}

    Selanjutnya, kode diatas untuk mengembalikan data yang berada pada indeks yang sama dengan nilai variabel top, dalam artian data yang paling belakang. Program akan error apabila array masih kosong karena dilakukan pengecekan terhadap indeks -1. Teman-teman boleh melengkapi kode di atas untuk memberikan exception.

public boolean isEmpty() {

   return top == -1;

}

    Nah, yang ini untuk mengecek apakah array kosong atau tidak. Mengembalikan nilai benar atau salah dari hasil pengujian top dengan nilai -1. Jika sama, maka nilainya true.

public boolean isFull() {

   return top == max-1;

}

    Jika pengujian benar, maka mengembalikan nilai true dan menyatakan bahwa array telah penuh.

Operasi tumpukan :

1. InsertFirst () biasa disebut Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke tumpukan
2. DeleteFirst () biasa disebut Pop (output E : typeelmt, input/output data : stack ) : menghapus sebuah elemen tumpukan
3. IsEmpty () : mengecek apakah stack kosong atau ada elemennya
4. IsFull () : mengecek apakah stack telah penuh atau belum
5. Clear () : menghapus semua data
6. Peek () : melihat data TOP

Ilustrasi Stack sebagai contoh:

     Terdapat dua buah kotak yang ditumpuk, kotak yang ditumpuk, kotak yang satu akan ditumpuk di atas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, di tambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan di peroleh sebuah stack kotak yang terdiri dari N kotak stack bersifat LIFO (Last In First Out) artinya benda yang terakhir masuk ke dalam stack akan menjadi pertama keluar dari stack

Kelebihan Stack:

      penambahan dan penghapusan data dapat dilakukan dengan cepat, yaitu O (1), selama memori masih tersedia , penambahan data bisa terusdilakukan. Dengan demikian tidak ada kekawatiran terjadinya stack overflow. 

Kekurangan Stack:

      setiap sel tidak hanya menyimpann value saja, melainkan juga pointer ke sel berikutnya. Yang menyebabkan implementasi stack memakai linked list akan memerlukan memori banyak, dan hanya di akses linked list hanya bisa di aksesdengan cara sekuensial, sehingga lambat O(n).

Video tutorial penerapan Stack:

referensi:

https://id.wikipedia.org/wiki/Stack_(struktur_data)

https://www.geeksforgeeks.org/stack-data-structure/

https://medium.com/easyread/memahami-konsep-stack-secara-sederhana-bd4409ec560c


Kelompok 10:
Bagas Wibowo      17520249004
Ibnu Haldun           17520249003
Lisa Purwaningsih 17520244013