Prinsip Implementasi Antrian Java
Kata "antrian" adalah apa yang oleh orang Inggris menyebut "antrian". "Langit -langit dalam barisan" di Inggris berarti berdiri berturut -turut. Dalam ilmu komputer, antrian adalah struktur data, yang sedikit seperti tumpukan, kecuali bahwa item data pertama yang dimasukkan dalam antrian akan dihapus terlebih dahulu, dan di tumpukan, item data terakhir yang dimasukkan dihapus terlebih dahulu. Antrian bekerja seperti barisan orang yang berdiri di depan bioskop: orang pertama yang memasuki afiliasi akan tiba di kepala tim untuk membeli tiket. Orang terakhir yang mengantri dapat membeli tiket.
Antrian juga digunakan sebagai alat untuk programmer, seperti tumpukan. Ini juga dapat digunakan untuk mensimulasikan lingkungan dunia nyata, seperti mensimulasikan orang yang menunggu di bank, pesawat yang menunggu untuk lepas landas, atau paket di internet menunggu untuk ditransmisikan.
Dalam sistem operasi komputer, berbagai antrian bekerja dengan tenang. Pekerjaan cetak sedang menunggu pencetakan dalam antrian cetak. Saat mengetik pada keyboard, ada juga antrian yang menyimpan pengetikan. Demikian pula, jika kunci disadap menggunakan pengolah kata dan komputer harus melakukan sesuatu yang lain sementara, konten yang disadap tidak akan hilang, dan itu akan menunggu dalam antrian sampai pengolah kata punya waktu untuk membacanya. Antrian digunakan untuk memastikan bahwa urutan pengetikan tidak diubah saat diproses.
Operasi Dasar Antrian
Dua operasi dasar dari antrian sedang memasukkan (memasukkan) item data, yaitu, memasukkan satu item data ke dalam ekor antrian, dan yang lainnya menghapus (menghapus) item data, yaitu, menghapus item data di kepala tim. Ini mirip dengan pecinta film yang antri ke ujung garis ketika mereka mengantri untuk membeli tiket, kemudian tiba di ujung garis dan kemudian meninggalkan antrian.
Penamaan metode untuk memasukkan dan menghapus item data dalam tumpukan sangat standar, disebut push dan pop. Metode antrian belum dinamai standar sejauh ini. "Sisipkan" dapat disebut put, tambah, atau enque, sementara "hapus" dapat disebut hapus, dapatkan, atau deque. Akhir dari item data penyisipan juga dapat dipanggil kembali, ekor atau akhir. Kepala tim yang menghapus item data juga dapat disebut kepala. Masukkan, lepas, depan dan belakang akan digunakan di bawah ini.
Masukkan Nilai ke dalam ekor antrian, dan ekor panah antrian ditambahkan untuk menunjuk ke item data baru.
Setelah item data dihapus, kepala tim ditambahkan oleh satu. Biasanya ketika menerapkan antrian, item data yang dihapus akan disimpan dalam memori, tetapi tidak dapat diakses karena kepala antrian telah dipindahkan ke posisi berikutnya.
Berbeda dengan kasus di tumpukan, item data dalam antrian tidak selalu dimulai pada subskrip 0 array. Setelah menghapus beberapa item data, pointer header menunjuk ke posisi subskrip yang lebih tinggi.
Operasi tampilan mengembalikan nilai item data header, tetapi tidak menghapus item data dari tim.
Jika Anda ingin menghapus item data dari antrian kosong atau memasukkan item data ke antrian penuh, aplikasi akan meminta pesan kesalahan.
Antrian Loop
Ketika item data baru dimasukkan ke dalam antrian, panah belakang di kepala tim bergerak ke atas menuju posisi besar subskrip array. Saat menghapus item data, ekor penunjuk depan antrian juga bergerak ke atas. Desain ini mungkin bertentangan dengan pengamatan langsung orang, karena ketika orang mengantri untuk tiket film, antrian selalu bergerak maju, dan setelah orang di depan mereka membeli tiket dan meninggalkan antrian, yang lain bergerak maju. Setelah menghapus item data dalam antrian di komputer, Anda juga dapat memajukan semua item data lainnya, tetapi ini sangat efisien. Sebaliknya, kami menyimpan semua item data dalam posisi yang sama melalui pergerakan pointer kepala dan ekor antrian.
Masalah dengan desain ini adalah bahwa penunjuk ekor akan dengan cepat bergerak ke ujung array. Meskipun ada unit item data kosong di awal array, yang merupakan lokasi item data yang dihapus, tetapi karena pointer ekor tidak dapat lagi bergerak mundur, item data baru tidak dapat dimasukkan. Apa yang harus saya lakukan?
Perawatan bungkus
Untuk menghindari masalah antrian yang tidak puas tetapi tidak dapat memasukkan item data baru, pointer kepala dan ekor dapat dibungkus kembali ke awal array. Ini adalah antrian loop (kadang -kadang juga disebut "cincin buffer").
Proses pembungkus pointer: Masukkan item data yang cukup ke dalam antrian untuk membuat titik pointer ekor ke ujung akhir array. Hapus beberapa item data lagi di ujung depan array. Sekarang masukkan item data baru. Anda akan melihat bahwa penunjuk ekor akan dibalik dari ujung ke posisi awal. Item data baru akan dimasukkan ke lokasi ini.
Masukkan lebih banyak item data. Pointer ekor bergerak ke atas seperti yang diharapkan. Perhatikan bahwa setelah pointer ekor kembali, sekarang berada di bawah pointer kepala, yang membalikkan posisi awal. Ini dapat disebut "urutan rusak": Item data dalam antrian hadir dalam dua urutan berbeda dalam array.
Setelah menghapus item data yang cukup, kepala tim juga berkeliling. Pada saat ini, penunjuk antrian kembali ke status posisi pada runtime awal, dan pointer kepala berada di bawah pointer ekor. Item data juga dikembalikan ke urutan kontinu tunggal.
Kode java untuk antrian
Program Queue.java menciptakan kelas antrian, yang memiliki metode insert (), remove (), peek (), isEmpty () dan size ().
tumpukan paket dan antrian;
antrian kelas {private int maxsize; long [] private long; Private Int Front; private int belakang; nitem pribadi; antrian publik (int s) {maxSize = s; Quearray = baru Long [MaxSize]; depan = 0; belakang = -1; nitem = 0; } public void insert (long j) {if (belakang == maxSize-1) belakang = -1; Quearray [++ belakang] = j; nitem ++; } public long rapE () {long temp = Quearray [front ++]; if (front == maxSize) depan = 0; nitem--; kembalikan suhu; } publik peekfront () {return queearray [depan]; } public boolean isEmpty () {return (nitems == 0); } public boolean iffull () {return (nitems == maxSize); } public int size () {return nitems; }}Kelas antrian yang diimplementasikan oleh program tidak hanya memiliki bidang depan (kepala) dan belakang (kepala tim), tetapi juga jumlah item data saat ini dalam antrian: nitem.
Prasyarat untuk pengoperasian metode insert () adalah bahwa antrian tidak puas. Metode ini tidak ditampilkan di Main (), tetapi metode insert () biasanya harus dipanggil terlebih dahulu dan kemudian metode isfull () harus dipanggil setelah mengembalikan false. (Pendekatan yang lebih umum adalah menambahkan penilaian ke metode insert () untuk memeriksa apakah antrian penuh. Jika item data dimasukkan ke dalam antrian penuh, pengecualian akan dilemparkan.)
Secara umum, operasi penyisipan adalah untuk menambahkan bagian belakang (penunjuk ekor tim) dan memasukkan data baru pada posisi yang ditunjuk oleh pointer ekor. Namun, ketika pointer belakang menunjuk ke bagian atas array, yaitu, posisi MaxSize-1, itu harus dilukai kembali ke bagian bawah array sebelum memasukkan item data. Operasi belitan menetapkan bagian belakang ke -1, jadi ketika belakang ditambahkan 1, sama dengan 0, yang merupakan nilai subskrip di bagian bawah array, dan akhirnya nitem ditambahkan satu.
Prasyarat untuk pengoperasian metode lepas () adalah bahwa antrian tidak kosong. Sebelum memanggil metode ini, Anda harus memanggil metode ISEmpty () untuk memastikan bahwa antrian tidak kosong, atau menambahkan mekanisme pemeriksaan kesalahan ini ke metode lepas ().
Operasi hapus selalu mendapatkan nilai item data header dari penunjuk depan, dan kemudian menambahkan yang depan. Namun, jika Anda melakukannya bahwa nilai depan melebihi bagian atas array, depan harus kembali ke posisi di mana subskrip array adalah 0. Saat melakukan tes ini, nilai pengembalian disimpan sementara. Akhirnya Nitem dikurangi satu.
Metode Peek () sederhana dan mudah dimengerti: Mengembalikan nilai item data yang ditunjuk oleh penunjuk depan. Beberapa implementasi antrian juga memungkinkan melihat nilai item data antrian-end; Misalnya, metode ini dapat disebut peekfront (), peekrear (), atau hanya depan () dan belakang ().
Implementasi metode isEmpty (), isfull () dan size () semuanya bergantung pada bidang NITEMS, yang mengembalikan apakah nitem sama dengan 0, apakah itu sama dengan maksimal, atau mengembalikan nilainya sendiri.
Termasuk bidang penghitungan item data nitem di kelas antrian akan menambahkan sedikit operasi tambahan ke metode insert () dan lepas (), karena metode insert () dan hapus () harus menambah dan mengurangi nilai variabel ini masing -masing. Ini mungkin bukan overhead tambahan, tetapi jika Anda berurusan dengan banyak insert dan menghapus operasi, ini dapat memengaruhi kinerja.
Karena, beberapa implementasi antrian tidak menggunakan bidang penghitungan item data, tetapi gunakan depan dan belakang untuk menghitung apakah antriannya kosong atau penuh dan jumlah item data. Jika Anda melakukan ini, rutinitas ISEempty (), iffull (), dan size () akan cukup rumit karena seperti yang disebutkan sebelumnya, urutan item data baik runtuh menjadi dua segmen, atau segmen kontinu.
Dan, masalah aneh muncul. Ketika antrian penuh, pointer depan dan belakang mengambil posisi tertentu, tetapi ketika antrian kosong, hubungan posisi yang sama juga dapat muncul. Jadi pada saat yang sama, antrian mungkin tampak penuh atau kosong. Solusi untuk masalah ini adalah: Jadikan kapasitas array menjadi satu lebih dari jumlah maksimum item data antrian.
Terima kasih telah membaca, saya harap ini dapat membantu Anda. Terima kasih atas dukungan Anda untuk situs ini!