Antrian (Queues)
Queue adalah FIFO
- Queue adalah First In, First Out (FIFO).
- Item pertama yang Anda tambahkan adalah item pertama yang keluar.
- Pikirkan antrian orang: orang di depan dilayani terlebih dahulu.
enqueue dan dequeue dengan list
- Kita dapat membangun queue dari list Python.
- enqueue =
queue.append(x)— tambahkan ke belakang. - dequeue =
queue.pop(0)— hapus dan kembalikan depan.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front dan empty
- Lihat depan tanpa mengeluarkannya:
queue[0]. - Queue kosong ketika
len(queue) == 0. - Periksa apakah tidak kosong sebelum Anda dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
Catatan tentang kecepatan
pop(0)harus menggeser setiap item lain maju satu tempat.- Untuk queue besar ini lambat, sehingga memakan lebih banyak waktu.
- Sistem nyata menggunakan circular buffer dengan pointer depan dan belakang sebagai gantinya.
Dalam pseudocode Cambridge
- Ujian membangun queue dari array dengan pointer
frontdan pointerrear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
Kesalahan umum
- Queue adalah first-in, first-out: gabung di belakang, keluar dari depan.
- Periksa apakah tidak kosong sebelum Anda dequeue.
Sekarang Anda coba
- Gunakan list sebagai queue Anda (
appenduntuk enqueue,pop(0)untuk dequeue). - Tekan Periksa jawaban untuk menguji kode Anda.
Antrian bersifat FIFO
Antrian menambah di belakang dan menghapus di depan — pertama masuk, pertama keluar.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Mulailah dengan antrian kosong. Masukkan (enqueue) "a", kemudian "b", lalu "c". Kemudian Keluarkan (dequeue) sekali, simpan nilai yang dihapus di first. (first seharusnya berisi "a" dan antrian seharusnya berisi ["b", "c"].)
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Enqueue 1, 2, 3 ke dalam antrean, lalu dequeue semuanya ke result. Berbeda dengan tumpukan, antrean mempertahankan urutan yang sama. (result seharusnya [1, 2, 3].)
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis serve(queue) yang menghapus item dari depan: hapus dari daftar dan kembalikan. Daftar pemanggil harus menjadi lebih pendek.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis front(queue) yang mengembalikan elemen depan tanpa menghapusnya, sehingga antrean tetap tidak berubah. Jika antrean kosong, kembalikan None.
Klik Jalankan untuk melihat output di sini.