LeetCode Grinding
Data Structures1 menit baca

Pengenalan Stack

Stack mengeluarkan item yang terakhir ditambahkan lebih dulu, dan ini berguna untuk pencocokan, membalik urutan, dan operasi bersarang.

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.

javascript
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:

javascript
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:

javascript
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:

javascript
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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan