Stack adalah struktur data linear yang menggunakan konsep LIFO (Last In
First Out).
Kita hanya bisa menambah dan menghapus elemen dari satu sisi saja, yaitu
top (bagian atas stack).
Operasi yang sering digunakan dalam implementasi stack:
push-> menambah elemen
public void push(String value) {
stack[++top] = value;
}
pop -> menghapus elemen
public String pop() {
return stack[top — ];
}
top (peek) -> function dengan nilai returnnya berupa elemen
pertama (untuk meliat elemen apa yang ada di top atau teratas di
stack)
public String peek() {
return stack[top];
}
isEmpty -> menguji apakah stack masih kosong
public boolean isEmpty() {
return top == -1;
}
isFull menguji apakah stack udah penuh
public boolean isFull() {
return top == max-1;
}
Apa aja implementasi stack di kehidupan kita?
Pas makai text editor misal Word, ketika makai undo/redo sebenarnya kita
lagi melakukan push dan pop “state” dari suatu stack
Pas makai browser, misal lagi buka beranda Instagram, habis tu mengklik
post orang. Ketika mengklik tombol “back”, sebenarnya kita udah
melakukan push (membuka post orang) dan pop (kembali ke beranda)
Pada beberapa literatur menyebutkan bahwa stack umumnya digunakan
untuk memisahkan ekspresi aritmatika. Misal, IDE/compiler mencek apakah
tanda kurung kurawal dikodingan kita sepasang atau jumlahnya sesuai,
mengubah notasi infix menjadi postfix, dll. Teman-teman dapat membaca
referensi infix-postfix yang lumayan lengkap dan mudah dipahami disini:
[Link]
Contoh Program (menggunakan array)
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 void tampilStack(){
for (int i=0; i<= top; i++) {
[Link](stack[i]);
}
}
public static void main(String[] args) {
Stack s = new Stack(5);
[Link]("Berikut ini adalah contoh program stack
menggunakan array dengan jumlah indeks 5: ");
[Link]("-- push() Fisika, Kimia, Matematika");
[Link]("Fisika");
[Link]("Kimia");
[Link]("Matematika");
[Link]();
[Link]("\n");
[Link]("-- peek()");
[Link]([Link]()+"\n"); // return matematika
[Link]("--- push() [Link], Biologi");
[Link]("B. Indonesia");
[Link]("Biologi");
[Link]();
[Link]("\n");
[Link]("-- isEmpty()");
[Link]([Link]() + "\n"); //false
[Link]("-- isFull()");
[Link]([Link]()+"\n"); //true
[Link]("-- pop()");
[Link]([Link]()+"\n"); //remove biologi
[Link]("-- stack sekarang ini berisi:");
[Link]();
[Link]("\n-- isFull()");
[Link]([Link]()+"\n"); //false
}
}
Implementasi Stack menggunakan Array vs Linked List
Array merupakan struktur data yang statis
o Sebelum array dibuat kita harus menentukan sizenya (program
akan mengalokasikan memori dan ruang sejumlah yang kita
pesan)
Masalahnya ialah: stack tidak memiliki batasan sebanyak apa jumlah
elemennya, sehingga stack selalu dapat tumbuuh ke atas dan
ukurannya makin besar
o Apa yang terjadi jika kita menambahkan elemen ke dalam stacj
ketika array udah penuh? Array tidak memiliki ruang lagi
sehingga terjadilah stack overflow
Linked list merupakan struktur data yang dinamis
o Kita bisa menambah ukurannya dengan mudah karena
memori dapat disimpan dimana saja, gak mesti beurutan
karena linked list punya node yang menunjuk alamat memori
node selanjutnya
o Stack overflow pada stack linkedlist sangat jarang terjadi,
hanya terjadi jika memori komputer/mesih kita yang habis