Tumpukan (stack)

Memeriksa apakah kurung dalam {[()()]} berpasangan dengan benar butuh satu tumpukan dan 8 kali push dan pop, satu untuk setiap kurung.

Masuk terakhir, keluar pertama

Bayangkan setumpuk piring. Kamu menaruh piring bersih di atas, dan saat butuh satu, kamu mengambilnya dari atas. Piring yang terakhir ditambahkan menjadi yang pertama keluar. Tumpukan (stack) adalah struktur data dengan aturan persis seperti itu, yang disebut masuk terakhir, keluar pertama (LIFO). Ada dua operasi utama: push menaruh nilai di atas, dan pop mengambil nilai teratas lalu mengembalikannya. Banyak tumpukan juga menyediakan peek, yang melihat nilai teratas tanpa mengambilnya.

Dalam catatan 6.006 MIT, tumpukan adalah kasus khusus dari antarmuka barisan (sequence): insert last(x) dan delete last(). Itu sudah memberi tahu cara membuatnya. Taruh nilai-nilainya di array dinamis dan perlakukan ujung array sebagai bagian atas. Di unit sebelumnya ujung adalah bagian yang murah, jadi push dan pop masing-masing memakan 1 langkah (teramortisasi, karena sesekali ada penyalinan). Ukuran tumpukan tidak berpengaruh. Pop dari tumpukan berisi 3 nilai atau 3 juta nilai sama-sama satu langkah.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, yang terakhir di-push
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Memeriksa kurung

Kegunaan klasik tumpukan adalah memeriksa apakah kurung seimbang, sesuatu yang dilakukan setiap editor kode dan compiler. Baca teksnya dari kiri ke kanan. Setiap kurung buka, (, [, atau {, di-push. Setiap kurung tutup harus cocok dengan kurung buka di puncak tumpukan: kalau cocok, pop kurung buka itu; kalau tumpukan kosong atau puncaknya jenis lain, string itu tidak seimbang. Di akhir, tumpukan harus kosong; kalau tidak, ada kurung buka yang tidak pernah ditutup.

Coba string-string di laboratorium. {[()()]} butuh 4 push dan 4 pop, 8 langkah, dan berakhir dengan tumpukan kosong. ([)] gagal di karakter ketiga: ) datang saat [ ada di puncak. (() terbaca sampai akhir dengan satu ( tersisa. Mengapa tumpukan cocok untuk tugas ini? Kurung bersarang, dan kurung yang paling baru dibuka harus menjadi yang pertama ditutup. Itulah masuk terakhir, keluar pertama.

Di mana lagi tumpukan muncul

• Tumpukan pemanggilan. Saat fungsi a memanggil b dan b memanggil c, komputer melakukan push catatan untuk setiap pemanggilan. Saat c selesai, catatannya di-pop dan b melanjutkan dari tempat ia berhenti. Rekursi tak berujung memenuhi tumpukan ini, dan itulah galat "stack overflow".
• Urungkan (undo). Editor melakukan push setiap perubahan. Undo melakukan pop perubahan terbaru lalu membatalkannya.
• Tombol Kembali. Browser melakukan push setiap halaman yang kamu tinggalkan; Kembali melakukan pop halaman terakhir.
• Pencarian mendalam. Kursus algoritma memakai tumpukan untuk masuk sedalam mungkin di labirin sebelum mundur.