Tipe data abstrak: kontrak operasi
Diperkenalkan| English | Makna |
|---|---|
| stack/stæk/ | tumpukan |
| queue/kjuː/ | antrean |
Apa yang akan menjelaskan pengamatan ini?
- Simulasi barisan menunggu memerlukan item tertua yang sedang ditunggu sebagai yang pertama. Tumpukan (stack) memberikan item paling baru sebagai yang pertama, jadi kontrak operasi adalah penting.
- Mulailah dengan prediksi. Nyatakan besaran atau fitur apa yang akan Anda bandingkan, lalu tentukan bukti apa yang dapat membedakan dua penjelasan.
Bangun modelnya
- Jenis data abstrak menentukan nilai dan operasi secara bebas daripada implementasi tertentu. Tumpukan adalah masuk terakhir, keluar pertama; barisan (queue) adalah masuk pertama, keluar pertama. Antaramuka koleksi memerlukan tingkah laku yang didefinisikan untuk operasi kosong dan tidak sah.
- stack: Tipe data abstrak last-in-first-out; queue: Tipe data abstrak first-in-first-out.
Struktur mana yang memodelkan antrian tunggu dengan urutan kedatangan biasa?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Antrean adalah pertama datang pertama keluar, yang merupakan kontrak antrean: masuk (enqueue) di belakang, keluar (dequeue) dari depan. Tumpukan (stack) adalah terakhir datang pertama keluar, dan struktur tanpa kontrak tidak memodelkan apa pun secara andal.
Pasangkan setiap istilah teknis dengan maknanya yang tepat.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Gunakan definisi untuk membedakan besaran dan proses yang terkait.
Pilih bukti yang boleh mengujinya
- Pilih struktur untuk corak akses yang diperlukan. Kerumitan bergantung pada implementasi dan asumsi: menyingkirkan item pertama dari array bergeser berbeza daripada memajukan penunjuk kepala dalam barisan.
- Jejakkan urutan operasi secara manual, kemudian bandingkan program dengan keadaan yang dijangka. Uji operasi kosong, tunggal dan berulang. Nyatakan tingkah laku_overflow jika kapasiti adalah tetap.
Dua kebiasaan manakah yang membuat penyelidikan atau model dalam kasus ini lebih dapat dipertanggungjawabkan?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Menyatakan kondisi dan asumsi memungkinkan orang lain mengulangi pekerjaan persis seperti itu, dan mencatat bukti pendukung memungkinkan mereka memeriksa kesimpulan. Menyembunyikan hasil yang bertentangan menghilangkan bukti yang dapat menentang kesimpulan yang salah, dan satu pengukuran tidak pernah dapat menetapkan klaim yang lebih luas.
Bekerja daripada kuantiti yang diketahui
- Nyatakan nilai yang diketahui dan unitnya. Pilih hubungan kerana asumsinya sesuai dengan kes ini, kemudian susun semula sebelum menggantikan.
- Diketahui:Speech A, B dan C, kemudianSpeech dua kali. A dan B keluar; C tinggal. SelepasSpeech D terdapat dua item yang ditunggu, C kemudian D. Push yang sama pada tumpukan akan menyingkirkan C kemudian B.
Barisan bermula kosong, menerima 7 item dan menyingkirkan 4. Cari bilangan yang tinggal. Gunakan urutan yang sama: kuantiti diketahui → model → hubungan → substitusi → unit dan tafsiran.
Sebuah antrian dimulai kosong, menerima 7 item dan menghapus 4. Temukan jumlah item yang tersisa.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Hasilnya adalah 3 item. Diketahui: antrean kosong; 7 masuk (enqueue); 4 keluar (dequeue). Sisa = 7 - 4 = 3 item. Dalam urutan kedatangan, tiga kedatangan terbaru masih menunggu.
Semak kesimpulan dan had-hadnya
- ADT bukan susunan memori spesifik. Barisan tidak mengurut berdasarkan keutamaan kecuali kontraknya mendefinisikan barisan keutamaan.
- Kembali ke pengamatan awal. Jelaskan apa hasil tersebut mendukung, kondisi apa yang diasumsikannya, dan satu cara untuk menguji penjelasan saingan.
Setiap antrean otomatis mengurutkan item berdasarkan prioritas. Klaim ini salah: Antrean biasa melepaskan item secara ketat sesuai urutan kedatangan. Pelayanan berdasarkan kepentingan adalah antrean PRIORITAS—kontrak yang berbeda yang harus dinyatakan secara eksplisit.
Jenis data abstrak: kontrak operasi: Pilih struktur untuk corak akses yang diperlukan. Kerumitan bergantung pada implementasi dan asumsi: menyingkirkan item pertama dari array bergeser berbeza daripada memajukan penunjuk kepala dalam barisan.
Setiap antrian secara otomatis mengurutkan item berdasarkan prioritas.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Antrean biasa melepaskan item secara ketat dalam urutan kedatangan. Pelayanan berdasarkan kepentingan adalah antrean PRIORITAS - kontrak berbeda yang harus dinyatakan secara eksplisit.
Jenis data abstrak last-in-first-out: tulis istilah teknis.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
stack berarti Tipe data abstrak last-in-first-out.