Memahami Struktur Data Tindanan: Panduan Langkah demi Langkah untuk Melaksanakan Tindanan dalam JavaScript

Timbunan ialah struktur data linear ringkas yang berfungsi seperti timbunan plat ?️. Ia mengikut prinsip Masuk Terakhir, Keluar Dahulu (LIFO). Fikirkannya sebagai longgokan pinggan: anda hanya boleh menambah atau mengeluarkan pinggan dari bahagian atas longgokan.

Untuk pemahaman yang lebih baik tentang timbunan, mari kita mulakan perjalanan imaginasi yang singkat ?.
Bayangkan anda berada di restoran mewah ?️, dan kakitangan dapur sedang bersiap untuk malam yang sibuk ?‍?. Di kawasan hidangan, terdapat timbunan pinggan yang tinggi menunggu untuk digunakan. Apabila pengunjung tiba dan pesanan masuk, kakitangan mengambil pinggan dari bahagian atas timbunan. Apabila pinggan bersih ditambah, ia akan berada tepat di atas. Sistem mudah ini memastikan bahawa plat di bahagian bawah tindanan yang paling lama berada di sana digunakan terakhir, manakala pinggan yang baru dibersihkan di atas digunakan terlebih dahulu ✨.

Ini, pada dasarnya, ialah cara struktur data Stack berfungsi. Tindanan ialah struktur data linear yang mengikut prinsip Keluar Dahulu Terakhir (LIFO). Sama seperti timbunan plat kami, item terakhir yang ditambahkan pada Tindanan ialah yang pertama dialih keluar.

Jadual Kandungan

Dalam tutorial komprehensif tentang struktur data tindanan ini, kami akan meneroka topik berikut dengan pendekatan yang mudah dan mesra pemula:

1. Apakah Tindanan?
2. Kebaikan dan Keburukan Menggunakan Tindanan
3. Aplikasi Tindanan Dunia Sebenar
4. Kendalian Utama pada Tindanan
5. Pelaksanaan Tindanan dalam JavaScript
6. Kesimpulan

---

---

Adakah anda bersedia? Jom selami

Apakah Stack?

Timbunan ialah struktur data linear yang mengikut prinsip Masuk Terakhir, Keluar Dahulu (LIFO). Ini bermakna elemen terakhir yang ditambahkan pada timbunan akan menjadi elemen pertama yang akan dialih keluar. Anggap ia seperti timbunan buku: anda hanya boleh menambah atau mengalih keluar buku dari bahagian atas timbunan.

Kebaikan dan Keburukan Menggunakan Stack

Sebelum kami meneruskan aliran dan menulis beberapa kod, adalah bagus untuk memahami tempat dan tempat untuk tidak menggunakan Stack. Jadual di bawah memberikan Kebaikan dan Keburukan Tindanan secara terperinci.

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

Operasi Utama pada Tindanan

Operasi asas yang boleh dilakukan pada tindanan ialah:

1. push(): Menambah elemen pada bahagian atas tindanan.
2. pop(): Mengalih keluar elemen paling atas daripada tindanan.
3. peek(): Mengembalikan elemen teratas tindanan tanpa mengalihkannya.
4. isEmpty(): Semak sama ada tindanan kosong.
5. size(): Mengembalikan bilangan elemen dalam tindanan.

Aplikasi Tindanan Dunia Sebenar

Timbunan ada di mana-mana dalam sains komputer dan pembangunan perisian. Berikut ialah beberapa aplikasi biasa:

1. Buat Asal Fungsi: Dalam penyunting teks atau perisian reka bentuk grafik, setiap tindakan ditolak ke dalam timbunan. Apabila anda menekan "buat asal", tindakan terbaharu muncul dari timbunan dan diterbalikkan.

2. Sejarah Penyemak Imbas: Apabila anda melawat halaman baharu, ia ditolak ke dalam timbunan. Butang "kembali" memaparkan halaman semasa dari timbunan, mendedahkan halaman sebelumnya.

3. Timbunan Panggilan Fungsi: Dalam bahasa pengaturcaraan, panggilan fungsi diuruskan menggunakan tindanan. Apabila fungsi dipanggil, ia ditolak ke timbunan panggilan. Apabila ia kembali, ia muncul.

4. Penilaian Ungkapan: Tindanan digunakan untuk menilai ungkapan aritmetik, terutamanya dalam tatatanda postfix.

5. Algoritma Penjejakan Belakang: Dalam masalah seperti penyelesaian maze atau penyelesaian teka-teki, tindanan boleh menjejaki laluan yang diambil, membolehkan pengesanan belakang mudah apabila diperlukan.

Pelaksanaan Tindanan dalam JavaScript

Sekarang, mari kita laksanakan Tindanan dalam JavaScript. Adalah penting untuk mengetahui bahawa terdapat cara yang berbeza untuk melaksanakan tindanan dalam JavaScript. Salah satu cara biasa untuk melaksanakan tindanan adalah menggunakan tatasusunan, cara lain ialah menggunakan senarai terpaut. Dalam artikel ini, kami akan melaksanakan tindanan menggunakan senarai terpaut (senarai pautan tunggal).

Laksanakan Tindanan menggunakan Senarai Terpaut

Saya harap anda masih ingat cara senarai terpaut berfungsi? Anda mungkin perlu menyemak pelaksanaan senarai terpaut dalam salah satu artikel kami sebelum ini dalam siri yang sama ini.

Cara Melaksanakan Senarai Pautan Tunggal dalam JavaScript

Penyelesaian Hebat ? ・ 4 Okt

#javascript #pemula #pengaturcaraan #dsa

Sekarang, mari kita mula melaksanakan tindanan kami menggunakan senarai pautan tunggal. Boleh?

Pertama, kami akan mencipta kelas Nod untuk mewakili item individu tindanan kami.

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

Kemudian, kami akan mencipta kelas Tindanan untuk mewakili tindanan kami.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

Operasi Tolak

Operasi tolak menambah elemen baharu pada bahagian atas tindanan. Ia mencipta StackNode baharu, menetapkan penuding seterusnya ke bahagian atas semasa, dan kemudian mengemas kini bahagian atas untuk menghala ke nod baharu ini. Akhirnya, saiznya bertambah.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

Operasi Pop

Operasi pop mengalih keluar elemen paling atas daripada tindanan. Ia mula-mula menyemak sama ada timbunan kosong. Jika ya, ia mengembalikan mesej ralat. Jika tidak, ia mengalih keluar elemen atas, mengemas kini penunjuk atas ke nod seterusnya dan mengurangkan saiz. Akhirnya, ia mengembalikan elemen yang dialih keluar.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Operasi Intai

Operasi mengintip mengembalikan elemen teratas tanpa mengalih keluarnya. Ia mula-mula menyemak sama ada timbunan kosong. Jika ya, ia mengembalikan mesej ralat. Jika tidak, ia mengembalikan data elemen teratas.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

adalah Operasi Kosong

Operasi isEmpty menyemak sama ada tindanan kosong. Ia kembali benar jika tindanan kosong, dan palsu sebaliknya.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

Operasi getSize

Operasi getSize mengembalikan saiz tindanan. Ia mengembalikan bilangan elemen dalam tindanan.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Operasi Cetak

Operasi cetakan mencetak tindanan. Ia mengembalikan data elemen teratas.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result += current.data + " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Contoh Penggunaan

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

Dalam pelaksanaan ini, kami menggunakan struktur (senarai pautan tunggal) senarai terpaut untuk mewakili tindanan kami. Setiap elemen ialah Nod dengan nilai data dan rujukan kepada Nod seterusnya. Bahagian atas tindanan sentiasa Nod yang paling baru ditambah.

Kesimpulan

Tindanan ialah struktur data asas dalam sains komputer yang mengikut prinsip Masuk Terakhir, Keluar Dahulu (LIFO). Ia digunakan dalam pelbagai aplikasi, termasuk mengurus panggilan fungsi, melaksanakan kefungsian buat asal dan menilai ungkapan aritmetik.

Dalam tutorial ini, kami telah membincangkan asas tindanan, kebaikan dan keburukan penggunaannya serta pelaksanaannya dalam JavaScript (menggunakan senarai terpaut). Memahami tindanan bukan hanya tentang mengetahui cara melaksanakannya, tetapi juga mengenali apabila ia adalah alat yang tepat untuk menyelesaikan masalah.

Sambil anda meneruskan perjalanan anda dalam pembangunan perisian, anda akan mendapati tindanan adalah alat yang sangat diperlukan dalam kit alat penyelesaian masalah anda. Ia mudah tetapi berkuasa dan menguasainya dengan ketara akan meningkatkan keupayaan anda untuk mereka bentuk algoritma dan struktur data yang cekap.

---

---

Kekal Kemas Kini dan Terhubung

Untuk memastikan anda tidak terlepas mana-mana bahagian dalam siri ini dan untuk berhubung dengan saya untuk perbincangan yang lebih mendalam tentang Pembangunan Perisian (Web, Pelayan, Mudah Alih atau Mengikis / Automasi), struktur data dan algoritma serta teknologi menarik yang lain topik, ikuti saya di:

• GitHub
• Linkedin
• X (Twitter)

Nantikan dan selamat mengekod ?‍??

Atas ialah kandungan terperinci Memahami Struktur Data Tindanan: Panduan Langkah demi Langkah untuk Melaksanakan Tindanan dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!