Dalam antrian, ujung mana yang merupakan "kepala"?

Saya selalu berpikir bahwa "kepala" antrian sebagai elemen berikutnya untuk dibaca, dan tidak pernah benar-benar mempertanyakan penggunaan itu. Jadi pustaka tertaut-daftar yang saya tulis, yang digunakan untuk memelihara antrian, mengodifikasi terminologi itu: kami memiliki list1_headmakro yang mengambil elemen pertama; saat menggunakan perpustakaan ini dalam antrian, ini akan menjadi elemen pertama yang akan dihapus.

Tetapi pengembang baru di tim terbiasa menerapkan antrian sebaliknya. Dia menggambarkan antrian berperilaku seperti anjing: Anda memasukkan di kepala, dan menghapus di bagian ekor. Ini adalah deskripsi yang cukup cerdik sehingga saya merasa penggunaannya harus lebih luas, dan saya tidak memiliki deskripsi menggugah yang sama tentang penggunaan yang saya sukai.

Jadi, saya kira, ada dua pertanyaan terkait: 1, apa arti "kepala" antrian bagi Anda? dan 2, mengapa kita menggunakan kata "kepala" untuk menggambarkan konsep itu?

terminology Aidan Cully
sumber

"Dia menggambarkan antrian berperilaku seperti anjing" ... Kedengarannya seperti orang yang menyenangkan untuk diajak bekerja sama - Jangan biarkan dia dekat dengan pelanggan.

NoChance

Saya tidak tahu, tapi saya sudah bisa menebak implementasi Anda, bukan yang anjing.

Izkata

Penjelasan bagus lainnya tentang perbedaan antara QUEUE dan STACK: http://pages.cs.wisc.edu/~mcw/cs367/lectures/stacks.html

Ythalo Rossy

Juga, dalam buku teks, daftar tertaut (tunggal) sering diperkenalkan sebelum struktur data lain seperti tumpukan dan antrian, dan kemudian ini dibangun di atas struktur daftar tertaut (yang belum tentu cara yang disukai untuk membangun struktur data ini hari ini karena cache salah). Daftar tertaut akan sering memiliki penunjuk kepala (mengacu pada elemen pertama), dan penunjuk ekor (ke yang terakhir); dalam pengaturan ini, mudah untuk memasukkan di ujung ekor menghapus dari kepala - jadi, dalam antrian FIFO, Anda menghapus dari depan. Tetapi perhatikan bahwa ini benar-benar detail implementasi internal.

Filip Milovanović

BTW, jangan berpikir itu sebagian hal yang berhubungan dengan bahasa, tetapi juga tentang bagaimana kita mengkonseptualisasikan apa yang dilakukan antrian. Bagi kebanyakan orang yang tahu arti kata "antrian", atau diperkenalkan dengan konsep dengan metafora itu (antri), bagian keluarnya ada di depan / kepala; Saya menduga teman Anda mengonseptualisasikannya lebih seperti semacam pipa, di mana Anda mendorong benda di satu ujung (awal, atau dalam arti tertentu, "kepala") pipa, dan mereka keluar di ujung lainnya.

Filip Milovanović

Jawaban:

Anda masuk di bagian belakang antrian, dan pergi dari depan. Di sebagian besar masyarakat, itu akan menyiratkan kepala adalah bagian depan, dan barang-barang dikeluarkan dari kepala.

The Javadoc untuk Antrian tampaknya setuju dengan definisi klasik (yaitu satu asli Anda):

Apa pun pemesanan yang digunakan, kepala antrian adalah elemen yang akan dihapus oleh panggilan untuk menghapus () atau polling (). Dalam antrian FIFO, semua elemen baru dimasukkan di ujung antrian.

Spencer Kormos
sumber

C ++ STL juga setuju.

Fabio Ceconello

Juga terminologi umum untuk FIFO / LIFO adalah untuk menghapus dari bagian atas Antrian / Stack. Bagian atas anjing adalah kepala, bukan ekor. :-D

Spencer Kormos

Tampaknya Anda telah menjawab pertanyaan pertama, biasanya penggunaan yang saya pahami adalah tradisional ... Terima kasih atas rujukannya. Tetapi bagi saya tidak seperti pakaian besi mengapa bagian depan antrian disebut "kepala" ...

Aidan Cully

... jadi di lubang anjing manakah kita menyediakan barang? ;)

ell

Ekor anjing adalah kepala antrian.

Caleb

Yang biasa disebut orang-orang di Amerika Serikat sebagai antrean, seperti pada tempat Anda berdiri di kantor pos, orang-orang di negara-negara berbahasa Inggris lainnya memanggil antrian. Jadi, lebih mudah bagi orang Amerika untuk menjaga terminologi tetap jika Anda mengganti "baris" untuk "antrian." Dengan kata lain, ketika Anda berada di kepala, atau depan, dari garis, Anda adalah yang selanjutnya dipanggil.

Karl Bielefeldt
sumber

Mungkin ini lebih merupakan pertanyaan tentang bahasa Inggris, karena masalah yang tampaknya muncul adalah "mengapa kita menyebut bagian depan sebagai kepala?"

Aidan Cully

@AidanCully: karena kepala pada tubuh (berkaki empat dan hewan lainnya berorientasi horizontal) menghadap ke depan, atau bagian depan.

outis

Itu penjelasan terbaik bagi kita orang Amerika.

andDevW

Kedua konvensi tersebut biasa digunakan. Dalam pengalaman saya, ketika berbicara tentang antrian secara umum, elemen kepala adalah yang berikutnya untuk keluar dari antrian, dan ekor adalah tempat elemen memasuki antrian. Ini konsisten dengan penggunaan bahasa Inggris sehari-hari — kami antre di belakang, dan yang akan dilayani berikutnya adalah di depan, atau di depan. (Dan jika Anda memotong, itu ke belakang untuk Anda!)

Namun, ketika antrian (alias FIFO) diimplementasikan sebagai penyangga cincin , istilah ini biasanya terbalik, karena bagian yang digunakan dari penyangga cincin menyerupai ular yang berputar-putar. Dengan asumsi ular bergerak maju, kepala secara alami adalah ujung yang memimpin gerakan, yang juga merupakan akhir di mana benda yang masuk dimasukkan.

IJ Kennedy
sumber

Layak disebutkan buffer bundar di kernel Linux , yang menggunakan konvensi bahwa item ditambahkan di kepala, dan dihapus di bagian ekor.

Craig McQueen