Pengenalan Stack

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 menyediakan operasinya di satu ujung saja. Stack mengeluarkan item yang terakhir ditambahkan lebih dulu. Urutan ini berguna ketika state terbaru harus didahulukan daripada state yang lebih lama. Waktu pertama kali mengimplementasikan stack, saya bikin simpel aja:

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;
  }
}

Menurut saya stack berguna ketika item terbaru menentukan aksi berikutnya. Mencocokkan kurung adalah salah satu contohnya:

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, saya 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, saya 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();
    }
  }
}

Waktu pertama kali belajar soal error stack overflow, saya kira error itu ada hubungannya sama website itu. Error pemrograman ini terjadi ketika stack kehabisan ruang, sering kali karena rekursi yang terlalu dalam. Nama website itu sendiri adalah lelucon pemrograman.

Kompleksitas dan kecocokan

Stack udah jadi salah satu struktur data favorit saya karena aturan LIFO bisa menangani struktur bersarang dan state "paling baru" tanpa logika pengurutan tambahan. Untuk stack yang pakai dynamic array, push itu amortized O(1) dan pop itu O(1).

Kalau sebuah soal meminta item terbaru, pencocokan bersarang, pembalikan urutan, atau perilaku undo, stack adalah kandidat yang natural. Struktur datanya kecil, tapi aturan urutannya bikin kita nggak perlu banyak bookkeeping.