Apa sajakah contoh sederhana dan bagus untuk antrian? [Tutup]

Saya mengajar CS2 ( Java and data structures), dan saya mengalami beberapa kesulitan dengan contoh-contoh bagus untuk digunakan ketika mengajar antrian. Dua aplikasi utama yang saya gunakan adalah untuk multithreadedmengirimkan pesan (tetapi pemrograman MT berada di luar cakupan untuk kursus), dan BFS-style algorithms(dan saya tidak akan membahas grafik sampai nanti dalam jangka waktu).

Saya juga ingin menghindari contoh-contoh yang dibuat-buat. Kebanyakan hal yang saya pikirkan, jika saya benar-benar akan menyelesaikannya dengan cara berulir tunggal, saya hanya akan menggunakan daftar daripada antrian. Saya cenderung hanya menggunakan antrian ketika pemrosesan dan penemuan disisipkan (misalnya pencarian), atau dalam kasus khusus lainnya seperti buffer panjang-terbatas (mis. Mempertahankan item N terakhir ). Sejauh praktis, saya mencoba mengajar murid-murid saya cara yang baik untuk benar-benar melakukan hal-hal dalam program nyata, bukan hanya mainan untuk memamerkan fitur.

Adakah saran yang bagus, algoritme sederhana atau aplikasi antrian yang dapat saya gunakan sebagai contoh tetapi yang membutuhkan minimal pengetahuan sebelumnya?

Ketika saya sedang belajar antrian, profesor saya selalu menggunakan contoh toko. Ada 1 atau lebih register terbuka pada waktu tertentu, dan Pelanggan memasukkan satu antrian atau yang lain dan bergerak melalui antrian itu untuk membeli semua barang mereka.

Kami benar-benar harus mengimplementasikan program sederhana yang dapat menggerakkan Pelanggan melalui RegisterQueue, jadi jika Anda benar-benar mencari program, Anda dapat memberikan para siswa contoh ini sederhana dan mudah, tetapi juga sesuatu yang setiap siswa telah lihat dalam kehidupan nyata dan sebagainya ini dapat membantu mereka memahami konsep dengan lebih baik.

Ketika saya belajar antrian, guru saya memperkenalkan mereka kepada saya menggunakan antrian untuk mobil di kantor polisi. Ada antrian yang memegang mobil ("antrian menunggu") dan petugas polisi akan selalu mengendalikan mobil berikutnya dalam antrian dan mengirimnya ke rekannya untuk diperiksa lebih lanjut atau membiarkan mobil lewat.

Contoh yang sangat sering digunakan adalah antrian di pasar super ...

Mengapa Anda tidak meminta siswa Anda untuk memberikan beberapa contoh sendiri?

Salah satu contoh yang muncul di benak saya adalah jalur pemrosesan hamburger di mis. McDonalds. Ada beberapa jenis burger yang berbeda, masing-masing dapat diproduksi oleh beberapa pekerja yang berbeda dan masing-masing memiliki antrian sendiri. Dari sana, setelah beberapa saat burger siap diambil, dalam urutan FIFO, oleh salah satu kasir yang memesan burger semacam itu.

Jadi ada banyak produsen dan konsumen, dan masing-masing antrian dibatasi.

Saya berpikir tentang menggunakan Amazon sebagai contoh, di suatu tempat dalam sistem besar mereka harus ada antrian pesanan yang perlu ditangani. yang bisa ditangani oleh enqueue dan dequeue sederhana. sistem akan menerima pesanan dalam sistem setiap kali seorang pelanggan membeli buku, dan seorang petugas penyimpanan kemudian akan mengeluarkannya untuk mengambil dan mempostingnya.

Maka akan lebih mudah untuk mulai berbicara tentang antrian prioritas, dengan memperkenalkan pelanggan utama, yang mungkin melompati antrian, Anda dapat memperkenalkan antrian prioritas.

Buku teks apa yang Anda gunakan?

Contoh sempurna dari antrian adalah bank memproses transaksi dengan akun. Biasanya Anda akan melihat daftar transaksi "yang tertunda" pada akhir hari. Ketika akuntansi dilakukan, transaksi tersebut diterapkan ke akun. Anda bahkan bisa masuk ke area antrian prioritas dengan ini. Tampaknya sebagian besar bank memprioritaskan pada debit saat memproses transaksi malam hari sehingga mereka dapat membayar Anda lebih dari biaya konsep sebelum mereka menerapkan kredit yang tertunda.

Transaksi dimasukkan ke dalam antrian dengan urutan waktu dieksekusi dan dequeued dan diterapkan ke akun oleh proses akuntansi.

Saya dulu seorang programmer telekomunikasi jadi ini terlintas dalam pikiran:

Hotline Layanan Pelanggan. Panggilan masuk, tidak ada cukup operator untuk menangani panggilan dan ditempatkan dalam antrian. Panggilan berikutnya masuk dan juga ditempatkan dalam antrian. Kemudian ketika operator berikutnya menjadi tersedia, panggilan pertama yang masuk antrian akan ditugaskan ke operator yang tersedia.

Contoh Dunia Nyata yang jelas adalah hal-hal seperti checkout line, dan semacamnya, tetapi karena Anda sedang mencari contoh yang berakar secara ketat dalam komputasi, bolehkah saya menyarankan antrian penjadwalan pekerjaan ?

Saya tidak tahu berapa banyak siswa Anda telah mengambil kelas Sistem Operasi, tetapi itu adalah pertaruhan yang bagus bahwa mereka semua telah menggunakan Task Manager untuk memeriksa proses mereka di beberapa titik atau lainnya. Anda bisa memperkenalkan contoh sederhana dari antrian penjadwalan, dan menugaskan mereka beberapa pekerjaan rumah untuk menulis sebuah program yang menghasilkan (atau menerima) "tugas" dengan ukuran tertentu, dan memprosesnya dalam urutan FIFO ketika mereka "memulainya".

Ini adalah konsep yang cukup mudah untuk dipahami, menunjukkan ide bahwa antrian beroperasi pada isinya dalam urutan yang menerima mereka, dan memberi mereka pengantar (sangat sederhana dan sederhana) untuk penjadwalan CPU. Hanya dua bit saya.

Anda mungkin memunculkan aplikasi mereka dalam multithreading, tetapi kecuali jika para siswa sudah memiliki pengalaman menulis program berulir, saya tidak akan menugaskan pekerjaan kepada mereka yang mungkin membuat dua frustasi. Saya ingat saya mengalami kesulitan mempelajari struktur data (terutama di Jawa, setelah tidak melakukan C ++ dan tidak belajar apa pun tentang petunjuk) di tahun kedua saya kuliah, jadi contoh sederhana namun praktis yang berkaitan langsung dengan komputasi mungkin yang terbaik.

Dunia nyata:

• Kapan saja orang-orang berbaris: kasir di toko grosir, di restoran menunggu meja (Anda dapat bekerja di beepers yang kadang-kadang mereka berikan dalam analogi), dll. Sangat membantu ketika Anda melihat bahwa di Inggris mereka sering panggil antrian ini alih-alih jalur (umum di NA)
• Membaca seri buku ', author.publish => queue.push dan student.read => queue.pop

Dunia Non-Nyata:

• Memproses data yang dikirimkan dalam lingkungan berulir tunggal tempat pemrosesan membutuhkan waktu lebih lama daripada pengiriman (misalnya checkout) untuk toko online.)
• Setiap koleksi FIFO yang dapat diiterasi dapat menggunakan antrian dan menggunakan while(queue.peek)alih-alih iterator.

Saya suka menggunakan game sebagai contoh karena umumnya sedikit lebih menarik daripada file IO atau apa pun yang bisa Anda buat.

Jadi, ketika Anda ingin mengeluarkan beberapa perintah secara berurutan ke unit dalam permainan strategi (mis. Minta Zergling untuk memeriksa 4 sudut pangkalan secara berurutan, lalu bunuh diri ke tengah pangkalan, antrian akan menjadi pilihan yang baik. .)

Atau mungkin Anda memiliki aplikasi yang hanya dapat memproses 30 frame per detik, tetapi Anda mungkin mendapatkan 4 atau 5 input di antara frame. Jika Anda memiliki input senjata pengganti dan input tembak, Anda ingin memastikan bahwa mereka ditangani sesuai urutan yang diterima atau Anda dapat granat ketika Anda ingin pisau. Dan jika Anda granat ketika Anda ingin pisau, Anda akan memiliki waktu yang buruk. (letakkan itu di meme instruktur ski dan lemparkan ke slide Anda) :)

Server yang menangani permintaan adalah satu lagi yang bagus.

Mesin CNC mengambil input. Mesin hanya bisa berjalan sangat cepat, sehingga perlu mengantri input.

Beberapa contoh yang dapat saya pikirkan:

• Kalkulator - dapat memperkenalkan awalan dan postfix secara bersamaan
• Instruksi untuk mengikat sepatu. Tidak dapat menyelesaikan operasi berikutnya sampai Anda telah melakukan yang terakhir
• Buffer - Mungkin penyangga telepon digunakan untuk menyimpan nomor yang telah dimasukkan pengguna tetapi belum membuat nada suaranya
• Pencernaan

Jalur manufaktur penuh dengan antrian. Pikirkan sebaris botol kosong menuju mesin pengisi. First-in-first-out adalah cara alami untuk menerapkan proses secara berurutan ke banyak objek. Antrian juga digunakan untuk memisahkan satu proses dari proses lainnya: mesin pengisi tidak harus segera berhenti jika ada masalah jangka pendek dengan mesin pelabelan.

Antrian digunakan dalam perangkat lunak dengan cara yang hampir sama. Output dari satu proses dapat diantrikan untuk input ke proses lain. Ini benar apakah Anda berbicara tentang komunikasi antar-proses, komunikasi antar-utas, atau sekadar memecah proses rumit menjadi bagian-bagian yang semuanya mungkin ditangani oleh utas yang sama.

Dalam sistem operasi, antrian sering digunakan untuk memproses input secara berurutan. Sistem file mungkin membaca blok dari perangkat penyimpanan dan menambahkannya ke antrian, misalnya. Atau interupsi yang menangani hal-hal seperti penekanan tombol dan gerakan mouse membuat acara yang ditambahkan ke antrian acara sehingga Anda tidak mendapatkan "uqeeu" daripada "antrian" saat Anda mengetik.

Untuk tugas siswa yang sederhana, saya pikir tugas apa pun yang menerima sejumlah input dan kemudian memprosesnya akan berhasil. Sebagai contoh, Anda dapat meminta mereka menulis evaluator ekspresi postfix sederhana. Itu akan memiliki tiga bagian:

• baca input, tambahkan ke antrian input, dan ulangi sampai tidak ada lagi input

• dapatkan item dari antrian

  • jika item adalah angka, dorong ke tumpukan argumen
  • jika item tersebut adalah operator, pop argumen yang diperlukan dan mengevaluasi
  • tambahkan hasilnya ke antrian output
  • ulangi sampai tumpukan kosong

• baca item dari antrian output, cetak, dan ulangi sampai antrian output kosong

Dalam mengajar struktur data, saya biasanya menggunakan aplikasi simulasi antrian bank di mana pelanggan menunggu dalam antrian dan ada sejumlah jendela layanan.

Masalahnya adalah untuk mensimulasikan proses untuk mengetahui statistik dari berikut ini: pelanggan menunggu waktu dalam antrian (maks, minimum, rata-rata), dan jumlah pelanggan yang menunggu dalam antrian. Saya menggunakan frekuensi yang telah ditentukan untuk tiba pelanggan baru setiap menit dalam sehari dan waktu layanan rata-rata pelanggan di jendela layanan dengan nilai-nilai dari generator nomor acak.

Hasilnya akan menjadi rekomendasi untuk jumlah optimal jendela layanan dan jumlah optimal kursi di ruang tunggu yang akan menjamin kepuasan pelanggan. Aplikasi yang sangat menarik bagi siswa.

Algoritma penjadwalan apa pun hampir selalu melibatkan antrian.

Ini dapat berkisar dari antrian pertama datang pertama dilayani untuk permintaan buffer untuk satu konsumen.

Untuk antrian penjadwalan pekerjaan yang kompleks di mana "tugas" dapat memiliki prioritas dan "pekerja" memiliki kemampuan yang berbeda.

Kasing yang bisa digunakan untuk bermain-main adalah "Anda memiliki server cetak pusat dengan empat printer terpasang dua mampu warna, satu mampu mencetak dua sisi dan satu mampu mencetak pada kertas yang lebih besar. Pengguna dapat membayar ekstra untuk pekerjaan yang terburu-buru, atau, lebih sedikit jika mereka tidak keberatan menunggu lebih lama. Anda bisa dikenai penalti jika Anda terlambat sehingga Anda ingin throughput sebanyak mungkin. "