Antrean dan tumpukan sebagai aturan layanan
INFO9-06
Menelusuri FIFO dan LIFO serta memilih model sesuai tujuan.
Bekal awal: Dapat membaca urutan penambahan dan pengambilan.
Konteks bab
Pembagian giliran adalah model belajar; aturan layanan nyata mengikuti pendamping. Kartu serta jaringan berikut rekaan.
Bacaan dan kasus
2 · Urutan yang berubah tanpa disadari
Bacaan pendalaman
Kasus dan angka yang dibuat untuk latihan adalah simulasi/rekaan; fakta konsep dan sumber dibedakan dalam uraian.
Permintaan berkode A,B,C masuk berurutan. Program model memakai tumpukan sehingga permintaan C keluar lebih dahulu. Pembuat menganggap hasilnya benar karena semua kode masih ada, tetapi petunjuk layanan menjanjikan urutan kedatangan. Masalahnya bukan hilangnya data, melainkan ketidaksesuaian struktur dengan kontrak.
Kelompok membandingkan antrean dan tumpukan di kertas. Mereka menambah D, mengambil dua entri, dan mencatat isi yang tersisa. Daftar langkah memperlihatkan perbedaan yang tidak terlihat dari sekadar jumlah entri. Urutan ternyata bagian penting dari makna data.
Pada tugas lain, mereka menggambar hubungan empat lokasi. Dua jalur mempunyai jumlah sisi sama, tetapi waktu berbeda setelah bobot ditambahkan. Mereka belajar bahwa struktur serta ukuran harus mengikuti pertanyaan. Lebih sedikit langkah, lebih dekat pada gambar, dan lebih cepat di dunia nyata tidak selalu berarti hal yang sama.
Fokus pemeriksaan. Mengapa jumlah entri yang benar belum menjamin perilaku layanan benar?
Antrean mengambil yang lebih dahulu masuk
Antrean FIFO berarti first in, first out: entri yang masuk lebih dahulu diambil lebih dahulu. Model ini cocok untuk giliran permintaan dengan prioritas sama. Jika A, B, C masuk berurutan, pengambilan pertama menghasilkan A. Antrean kosong tidak memiliki entri untuk diambil; program perlu memeriksa keadaan itu.
Tumpukan mengambil yang paling akhir masuk
Tumpukan LIFO berarti last in, first out. Model ini dapat membantu memahami pembatalan langkah terakhir atau tumpukan kartu. Jika A, B, C dimasukkan, pengambilan pertama menghasilkan C. LIFO bukan otomatis salah atau tidak adil; kelayakannya bergantung tujuan. Memakainya untuk layanan yang menjanjikan giliran kedatangan akan melanggar kontrak layanan.
Struktur dan kebijakan perlu dibedakan
Dalam Python, list dapat dipakai sebagai tumpukan melalui append() dan pop(). Untuk antrean, collections.deque menyediakan append() dan popleft(). Penggunaan prioritas khusus memerlukan aturan tambahan; algoritma FIFO sederhana tidak mengetahui kebutuhan mendesak atau izin pendamping. Buku memakai kartu permintaan rekaan, bukan memutus giliran orang nyata.
Dua aturan pada masukan sama
from collections import deque
antrean = deque(["A", "B", "C"])
tumpukan = ["A", "B", "C"]
print(antrean.popleft())
print(tumpukan.pop())Keluaran contoh
A C
Contoh memiliki entri. Pada program yang menerima tindakan pengguna, periksa keadaan kosong sebelum mengambil.
Telusuri contoh
A,B,C masuk lalu satu diambil. Bandingkan FIFO dan LIFO.
- FIFO mengambil A dan menyisakan B,C.
- LIFO mengambil C dan menyisakan A,B.
- Urutan keluaran menunjukkan aturan yang berbeda.
Apa yang dilakukan jika wadah kosong?
- Periksa sebelum mengambil.
- Laporkan tidak ada entri.
- Jangan mengarang hasil atau membiarkan kesalahan tanpa penjelasan.
FIFO dan LIFO adalah aturan berbeda; memilih struktur tidak otomatis menetapkan kebijakan layanan yang adil.
Latihan mandiri
1 Apa kepanjangan dan makna FIFO?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
First in, first out: masuk pertama diambil pertama.
2 Apa contoh tujuan LIFO?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Membatalkan langkah terakhir atau memodelkan tumpukan kartu.
3 Mengapa prioritas khusus perlu aturan tambahan?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Urutan kedatangan saja tidak memuat kebutuhan, izin, atau tingkat prioritas.
4 Pada Python deque, operasi mengambil depan disebut apa?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
popleft(), setelah memastikan antrean tidak kosong.
Perluas pemahamanmu
Rancang satu aturan prioritas rekaan dengan batas yang jelas. Jelaskan bagaimana aturan mengubah urutan FIFO serta alasan perlu diumumkan.
Coba dengan umpan balik
Latihan otomatis membantu pemeriksaan; tuliskan alasan dan langkah untuk membuktikan pemahaman.
1 A,B,C masuk ke tumpukan lalu pop() dijalankan, hasilnya…
Petunjuk awal
Tentukan informasi, konsep dan bukti yang dibutuhkan.
Pembahasan · buka setelah mencoba
C. C. Tumpukan LIFO mengambil entri yang terakhir masuk.
Praktik dan refleksi
Jalankan kartu A,B,C,D pada antrean dan tumpukan. Catat keluaran setelah dua pengambilan dan penambahan E.
Penanda pribadi di perangkat ini; bukan nilai atau bukti penguasaan.