Stack muncul di function call, riwayat undo dan redo, dan evaluasi ekspresi. Aturan yang berguna di sini adalah LIFO, atau Last In, First Out: item yang paling terakhir ditambahkan bakal dikeluarkan lebih dulu.
LIFO dalam praktik
Stack menambah dan mengeluarkan item dari ujung yang sama. Di sini, array JavaScript menyimpan item dan elemen terakhirnya menjadi puncak stack.
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items.pop();
}
peek() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
Untuk mencocokkan kurung, kurung pembuka terakhir harus cocok dengan kurung penutup berikutnya:
function isValidParentheses(s) {
const stack = [];
const pairs = { "(": ")", "[": "]", "{": "}" };
for (let char of s) {
if (pairs[char]) {
stack.push(char); // Opening bracket
} else {
if (stack.length === 0) return false;
const last = stack.pop();
if (pairs[last] !== char) return false;
}
}
return stack.length === 0;
}
Untuk membalik urutan, aku push setiap item lalu pop item-item itu belakangan:
function reverseString(str) {
const stack = [];
for (let char of str) {
stack.push(char);
}
let reversed = "";
while (stack.length > 0) {
reversed += stack.pop();
}
return reversed;
}
Untuk perilaku undo, aku menyimpan state-state sebelumnya di dalam stack:
class Editor {
constructor() {
this.content = "";
this.undoStack = [];
}
type(text) {
this.undoStack.push(this.content); // Save state
this.content += text;
}
undo() {
if (this.undoStack.length > 0) {
this.content = this.undoStack.pop();
}
}
}
Kompleksitas dan kecocokan
Untuk stack yang memakai dynamic array, push butuh amortized O(1) dan pop butuh O(1). Menyimpan n item memakai O(n) space.
Aku pakai stack kalau item terakhir yang belum selesai harus ditangani berikutnya. Dalam contoh kurung, item itu adalah kurung pembuka terakhir yang belum ditutup.

Memuat komentar...