Di mana saya biasanya menggunakan Deque dalam perangkat lunak produksi?

Saya cukup akrab dengan tempat menggunakan Stacks, Antrian, dan Pohon dalam aplikasi perangkat lunak tapi saya belum pernah menggunakan Deque (Double Berakhir Antrian) sebelumnya. Di mana saya biasanya bertemu mereka di alam liar? Apakah akan berada di tempat yang sama dengan Antrian tetapi dengan gribbilies ekstra?

data-structures Insinyur Dunia
sumber

en.wikipedia.org/wiki/Double-ended_queue#Applications

Arseni Mourzenko

tampaknya ada beberapa kebingungan di utas ini. Di internet "deque" adalah antrian dengan ujung ganda (wikipedia menyebutkan implementasi daftar tertaut). Namun dalam C ++ STL, "std :: deque" adalah struktur mirip array yang diimplementasikan sebagai larik blok data. Ia menawarkan akses acak, mirip dengan std :: vector, tetapi kemampuannya mengubah ukuran lebih dekat dengan std :: list karena ketika data ditambahkan, ia menambah blok dan tidak merealokasi dan memindahkan data yang ada.

DXM

@DXM: deque STL masih merupakan antrian dengan ujung ganda dan menyediakan operasi yang lebih cepat di ujungnya (tergantung pada implementasinya). Bahwa ia menawarkan akses ke tengah juga tidak membuat operasi utamanya kurang seperti antrian.

gbjbaanb

@ gbjbaanb: Yang saya katakan adalah jika Anda melihat antarmuka publik dari 3 kelas: std :: vector, std :: list (atau std :: queue) dan std :: deque, Anda akan melihat std :: vector dan std :: deque memiliki antarmuka publik yang identik dan kemampuan yang identik (std :: deque sedikit lebih fleksibel dengan mengorbankan jejak memori yang lebih besar). std :: daftar dan std :: antrian berperilaku lebih seperti bagian-counter CS mereka, masing-masing terkait-daftar dan antrian. CS deque! = Std :: deque

DXM

Saya menemukan jawaban ini lebih praktis oleh shiv.mymail - stackoverflow.com/questions/3880254/…

roottraveller

Jawaban:

Salah satu cara deque digunakan adalah untuk "umur" item. Biasanya digunakan sebagai fitur undo atau history. Tindakan baru dimasukkan ke dalam deque. Item tertua ada di depan. Batas pada ukuran deque memaksa barang-barang di bagian depan dihilangkan pada beberapa titik ketika barang-barang baru dimasukkan (menua barang tertua). Kemudian memberikan cara cepat untuk mengakses kedua ujung struktur karena Anda langsung tahu item tertua dan terbaru untuk menghapus bagian depan dan melakukan tindakan tertua di O (1) atau membatalkan dalam waktu O (1).

jmq
sumber

Saya tidak berpikir deques digunakan / dibutuhkan di sini. Tumpukan sederhana (mungkin ukuran terbatas) sudah cukup.

Konrad Rudolph

@ Konrad Bagaimana cara Anda menambahkan item dalam tumpukan sederhana? (yaitu, bagaimana Anda menghapus perintah yang "terlalu tua"?)

Andres F.

@AndresF. Apakah usia tidak tergantung pada ukuran tumpukan? Jika demikian, maka saya belum pernah mendengar tentang struktur data ini. Kalau tidak, itu hanya tumpukan dengan ukuran tetap yang dapat diimplementasikan dalam hal deque, atau hanya dengan mendalilkan struktur data yang lebih sederhana yang disebut tumpukan berukuran tetap.

Konrad Rudolph

Jadi deques yang berguna setelah semua;) Pernah mendengar dari tumpukan berukuran tetap (dalam arti yang Anda maksud, menghapus item tertua). Masuk akal, tetapi bukan itu yang biasanya dimaksud dengan "tumpukan", dan apakah itu sebenarnya lebih sederhana tetap harus dilihat :)

Andres F.

Ini diposting dalam komentar dari pertanyaan asli: en.wikipedia.org/wiki/Double-ended_queue Ini hanya antrian dengan ujung ganda. Saya telah menggunakannya dalam praktik dengan cara yang telah saya uraikan di atas (itulah sebabnya saya mempostingnya). Dalam tumpukan yang sebenarnya, satu-satunya operasi yang harus Anda miliki adalah push, pop, top, dan mengintip (kita bisa berdebat dengan orang lain, tetapi ini umumnya itu). Anda seharusnya tidak memiliki pengetahuan tentang apa yang ada di bagian bawah tumpukan atau bahkan bagaimana mengakses bagian bawah. Dalam "tumpukan berukuran tetap" Anda hanya akan menghasilkan tumpukan berlebih alih-alih menua item lama saat Anda mengisinya.

jmq

Pertanyaan yang sangat bagus Saya tidak ingat kursus CS 102 kami menyebutkan satu aplikasi untuk antrian berujung ganda.

Sampai hari ini, satu-satunya aplikasi yang saya tahu adalah penjadwal mencuri pekerjaan yang disebutkan dalam artikel Wikipedia .

Ini pada dasarnya berfungsi sebagai berikut:

Dalam model prosedural berulir tunggal normal, setiap panggilan fungsi mendorong catatan aktivasi pada apa yang disebut tumpukan panggilan . Catatan aktivasi berisi variabel dan parameter lokal panggilan itu. Setelah panggilan ke metode selesai ("kembali"), catatan aktivasi terakhir muncul dari tumpukan panggilan.

Ini sangat penting karena begitulah cara rekursi diimplementasikan: struktur rekursi diwakili dalam keadaan saat ini dari tumpukan panggilan.

Saat memparalelkan algoritma rekursif, kita dapat mengeksploitasi properti ini dengan mengganti tumpukan panggilan dengan antrian panggilan. Setiap utas dalam perhitungan mendapatkan antrian panggilannya sendiri dan mendorong serta memunculkan catatan aktivasi seperti dalam eksekusi berurutan.

Tetapi begitu sebuah utas telah menyelesaikan pekerjaannya (= antrian panggilannya kosong), itu mencuri pekerjaan dari utas lainnya dengan menghapus catatan aktivasi dari antrian panggilan utas itu dengan menghapus dari ujung yang “salah”.

Pada dasarnya, antrian panggilan bertindak sebagai dua tumpukan panggilan yang sekarang melayani dua utas.

Konrad Rudolph
sumber

Apakah Anda punya sumber untuk ini? Kedengarannya menarik.

kyjelly90210

@ Richard1987 Artikel Wikipedia mengutip makalah aslinya. Ada beberapa implementasi, misalnya dalam GNU c ++ stdlib implementasi ekstensi paralel kerja mencuri (tetapi kode ini mengerikan untuk dibaca) atau implementasi paralel dari pembagian umum & taklukkan oleh Anda benar-benar (tetapi yang terakhir menggunakan gaya pemrograman yang sangat idiomatis khusus ke perpustakaan dan karenanya sulit dibaca)

Konrad Rudolph