LIFO atau FIFO? Panduan Tumpukan/Barisan

Menganggap pemahaman tatatanda Big O. Contohnya adalah dalam JavaScript. Rujukan maklumat "Cracking the Coding Interview" oleh Gayle Laakmann McDowell

Hari ini, kita akan meneroka dua struktur data penting: tindanan dan barisan. Kami akan menyelami konsep mereka, kes penggunaan dan melaksanakannya dalam JavaScript menggunakan kedua-dua pendekatan klasik dan berasaskan prototaip.

---

Tindanan: Masuk Terakhir, Keluar Dahulu (LIFO)

Bayangkan timbunan penkek – yang terakhir anda letakkan di atas ialah yang pertama anda makan. Begitulah cara struktur data tindanan berfungsi. Ia mengikut prinsip Masuk Terakhir, Keluar Dahulu (LIFO).

Operasi Utama

• push(item): Tambahkan item pada bahagian atas tindanan
• pop(): Alih keluar item teratas daripada timbunan
• peek(): Kembalikan item teratas tanpa mengeluarkannya
• isEmpty(): Semak sama ada tindanan kosong

Kes Penggunaan

Timbunan amat berguna dalam senario yang melibatkan:

• Algoritma rekursif
• Buat asal mekanisme dalam penyunting teks

Pelaksanaan JavaScript

OOP klasik

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

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

Berasaskan Prototaip

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};

Stack.prototype.size = function() {
  return this.items.length;
};

Stack.prototype.clear = function() {
  this.items = [];
};

---

Beratur: Masuk Pertama, Keluar Dahulu (FIFO)

Sekarang, mari alihkan tumpuan kita kepada baris gilir. Tidak seperti tindanan, baris gilir mengikut prinsip Masuk Pertama, Keluar Dahulu (FIFO). Fikirkan barisan di tempat konsert – orang pertama yang tiba ialah orang pertama yang masuk.

Operasi Utama

• enqueue(item): Tambahkan item pada penghujung baris gilir
• dequeue(): Alih keluar item pertama daripada baris gilir
• peek(): Kembalikan item pertama tanpa mengeluarkannya
• isEmpty(): Semak sama ada baris gilir kosong

Kes Penggunaan

Baris gilir biasanya digunakan dalam:

• Algoritma carian luas didahulukan
• Penjadualan tugas

Pelaksanaan JavaScript

OOP klasik

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

Berasaskan Prototaip

function Node(data) {
  this.data = data;
  this.next = null;
}

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

---

Analisis Prestasi

Kedua-dua tindanan dan baris gilir menawarkan $O(1)$O(1) kerumitan masa untuk operasi teras mereka (tekan/pop untuk tindanan, enqueue/dequeue untuk baris gilir) apabila dilaksanakan dengan cekap. Ini menjadikan mereka berprestasi tinggi untuk kes penggunaan khusus mereka.

Kedua-duanya menyediakan penyelesaian yang elegan kepada banyak masalah pengaturcaraan biasa dan membentuk asas untuk struktur dan algoritma data yang lebih kompleks. Dengan memahami dan melaksanakan struktur ini dalam JavaScript, anda serba lengkap untuk menangani pelbagai masalah Leetcode/Algoritma ?.

Atas ialah kandungan terperinci LIFO atau FIFO? Panduan Tumpukan/Barisan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!