B.4 · Tipe data abstrak (HL saja)

Fokus HL yang didukung. Target penilaian pertama 2027; PDF resmi mengembalikan 403; brief perolehan lama adalah penilaian akhir 2026. Panduan, persyaratan penilaian, dan praktis lainnya tetap mempertahankan catatan yang tercatat.

Prasyarat: baca kuantitas dan satuan yang disebutkan, gunakan aritmatika, dan kondisi model di bawah ini. Setiap pelajaran mengembangkan metodenya sendiri sebelum transfer mandiri.

Ini adalah contoh pengajaran asli atau fiksi eksplisit, bukan pengukuran aktual atau penyelidikan pembelajaran yang selesai dan dinilai.

Apa yang akan menjelaskan observasi 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.

Pilih bukti yang dapat 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.

Bekerja dari kuantitas 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.

Contoh:

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.

Periksa kesimpulan dan batasannya

• 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.

Peringatan:

Setiap barisan secara automatik mengurut item berdasarkan keutamaan. Klaim ini adalah salah: ADT bukan susunan memori spesifik. Barisan tidak mengurut berdasarkan keutamaan kecuali kontraknya mendefinisikan barisan keutamaan.

Kunci:

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.

Jejak dan batas dapat dijalankan

from collections import deque
queue = deque()
queue.extend(["A", "B"])
print(queue.popleft())
queue.append("C")
print(queue.popleft())
print(list(queue))
queue.clear()
print(queue.popleft() if queue else "EMPTY")

Output yang diharapkan:

A
B
['C']
EMPTY

Penghapusan dari sisi kiri menerapkan FIFO. Pengaman kosong eksplisit menentukan hasil batas; deque.popleft tanpa hal ini akan memicu IndexError. Stack sebaliknya menghapus dari sisi kanan.