Yang terakhir masuk keluar dulu

Satu struktur yang hanya bisa disentuh dari satu ujung, dan kenapa justru batasan itu yang membuatnya berguna.

Sebaiknya baca lebih dulu: Map, data yang ditunjuk dengan nama, Menyimpan yang terbaik sejauh ini.

Tumpukan piring

Struktur seperti itu disebut stack. Dua operasinya: menaruh di atas, dan mengambil dari atas. Yang terakhir masuk adalah yang pertama keluar.

Stack tidak menuntut tipe data khusus. Array biasa sudah cukup, selama yang ditambah dan yang diambil selalu ujung yang sama. Menaruh berarti menambahkan ke belakang, mengambil berarti membaca elemen terakhir lalu memendekkan arraynya satu.

IngatBatasannya bukan kekurangan. Justru karena hanya satu ujung yang dapat disentuh, stack menjawab satu pertanyaan dengan tepat: apa yang paling terakhir belum diselesaikan.

Kurung yang harus berpasangan

Sekarang soalnya. Sebuah deretan kurung sah bila setiap kurung buka punya kurung tutup yang cocok, dan pasangannya tidak saling menyilang. Kurung bulat dan kurung siku dua jenis yang berbeda, jadi kurung bulat tidak dapat ditutup kurung siku.

  • Sah: buka bulat, buka siku, tutup siku, tutup bulat. Yang terakhir dibuka ditutup lebih dulu.
  • Tidak sah: buka bulat lalu tutup siku. Jenisnya tidak cocok.
  • Tidak sah: tutup bulat lalu buka bulat. Kurung tutup datang ketika tidak ada yang menunggu ditutup.
  • Tidak sah: buka bulat lalu buka bulat, tanpa penutup. Masih ada yang menunggu di akhir.
  • Sah: deretan kosong. Tidak ada satu pun kurung yang tidak berpasangan.

Perhatikan butir pertama. Kalimat yang terakhir dibuka ditutup lebih dulu adalah stack, dinyatakan dengan kata lain. Itu sebabnya soal ini dan struktur ini bertemu; aturan kurung memang aturan stack.

SET stack = []
SET sah = TRUE
FOR EACH token IN tokens
  IF token adalah kurung buka
    SET stack = stack + [token]
  ELSE
    IF stack kosong
      SET sah = FALSE
    ELSE IF pasangan(token) != elemen terakhir stack
      SET sah = FALSE
    ELSE
      buang elemen terakhir stack
    END
  END
END
OUTPUT sah AND stack kosong
Baris terakhir memuat dua syarat. Tidak ada pelanggaran DI TENGAH jalan, dan tidak ada yang tersisa DI AKHIR. Keduanya dibutuhkan.

Dua kegagalan yang berbeda

Baris terakhir itu yang paling sering ditulis setengah. Ada dua cara deretan kurung gagal, dan keduanya perlu diperiksa di tempat yang berbeda.

Hanya memeriksa di tengah jalan

OUTPUT sah

Memeriksa juga sisa di akhir

OUTPUT sah AND stack kosong

Pada deretan buka bulat lalu buka bulat, tidak ada satu pun pelanggaran yang terjadi selama penelusuran: tidak ada kurung tutup yang salah pasangan, dan tidak ada kurung tutup pada stack kosong. Kolom kiri menjawab sah. Yang salah bukan langkahnya melainkan keadaan akhirnya, yaitu dua kurung yang masih menunggu ditutup. Kegagalan yang hanya terlihat dari keadaan akhir tidak dapat ditangkap pemeriksaan per langkah.

Melihat stack naik dan turun

SET stack = []
FOR EACH token IN tokens
  IF token adalah kurung buka
    SET stack = stack + [token]
  ELSE
    buang elemen terakhir stack
  END
END
OUTPUT stack kosong
stack[] kosong

Stack dimulai kosong.

Langkah 1 dari 6
tokens berisi buka bulat, buka siku, tutup siku, tutup bulat. Perhatikan stack kembali kosong tepat di akhir.

Perhatikan bahwa kurung siku masuk paling akhir dan keluar paling awal. Itu bukan kebetulan pada contoh ini: aturan kurung memaksa urutan itu, dan stack memberikannya tanpa satu pun baris tambahan. Struktur yang cocok dengan persoalannya membuat kodenya menjadi pendek, dan itu bukan kebetulan yang menyenangkan melainkan tanda strukturnya dipilih benar.

Stack kosong yang disentuh

Satu penjaga yang wajib ada. Kurung tutup yang datang ketika stack kosong tidak punya pasangan untuk dicocokkan, dan membaca elemen terakhir dari array kosong adalah membaca indeks yang tidak ada, tepat persoalan pelajaran 4.1. Jadi urutan pemeriksaannya penting: periksa stack kosong LEBIH DULU, baru cocokkan jenisnya.

Periksa pemahaman

Deretan tutup bulat lalu buka bulat. Pada langkah mana kegagalannya terdeteksi, dan bagaimana?

Ringkasan

  • Stack hanya dapat disentuh dari satu ujung: yang terakhir masuk keluar dulu.
  • Array biasa sudah cukup untuk menjadi stack, selama ujung yang disentuh selalu sama.
  • Aturan kurung adalah aturan stack, dan itu sebabnya kodenya menjadi pendek.
  • Ada dua cara gagal: pelanggaran di tengah jalan, dan sisa yang tertinggal di akhir. Keduanya wajib diperiksa.
  • Periksa stack kosong sebelum mencocokkan jenis, sebab membaca ujung stack kosong adalah membaca yang tidak ada.
  • Deretan kosong sah. Jumlah buka dan tutup yang sama tidak pernah cukup membuktikan kesahan.