Queues · Antrian (Queues)
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
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 and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
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 and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
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?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
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.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
Kesalahan umum
- Queue adalah first-in, first-out: gabung di belakang, keluar dari depan.
- Periksa apakah tidak kosong sebelum Anda dequeue.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
Sekarang Anda coba
- Gunakan list sebagai queue Anda (
appenduntuk enqueue,pop(0)untuk dequeue). - Tekan Periksa jawaban untuk menguji kode Anda.
A queue is FIFO · Antrian bersifat FIFO
A queue adds at the back and removes at the front — first in, first out. · Antrian menambah di belakang dan menghapus di depan — pertama masuk, pertama keluar.
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].) · 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"].)
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same order. (result should be [1, 2, 3].) · Masukkan ⟨Enqueue⟩ 1, 2, 3 ke dalam antrean, lalu keluarkan (dequeue) semuanya ke result. Berbeda dengan tumpukan (stack), antrean mempertahankan urutan yang sama. (result seharusnya adalah [1, 2, 3].)
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write serve(queue) that dequeues the front item: remove it from the list and return it. The caller's list should get shorter. · Tulis serve(queue) yang menghapus item dari depan: hapus dari daftar dan kembalikan. Daftar pemanggil harus menjadi lebih pendek.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write front(queue) that returns the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · Tulis front(queue) yang mengembalikan elemen depan tanpa menghapusnya, sehingga antrean tetap tidak berubah. Jika antrean kosong, kembalikan None.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.