Pengantar Java ArrayDeque

1. Ikhtisar

Dalam tutorial ini, kami akan menunjukkan cara menggunakan kelas ArrayDeque Java - yang merupakan implementasi antarmuka Deque .

Sebuah ArrayDeque (juga dikenal sebagai “Array Double Ended Antrian”, diucapkan sebagai “ArrayDeck”) adalah jenis khusus dari array growable yang memungkinkan kita untuk menambah atau menghapus sebuah elemen dari kedua belah pihak.

Sebuah ArrayDeque implementasi dapat digunakan sebagai Stack (terakhir-In-First-Out) atau Queue (First-In-First-Out).

2. Sekilas tentang API

Untuk setiap operasi, pada dasarnya kami memiliki dua opsi.

Grup pertama terdiri dari metode yang mengeluarkan pengecualian jika operasi gagal. Grup lain mengembalikan status atau nilai:

Operasi metode Metode melempar Exception
Penyisipan dari Head offerFirst (e) addFirst (e)
Penghapusan dari Kepala pollFirst () removeFirst ()
Pengambilan dari Head peekFirst () getFirst ()
Penyisipan dari Tail offerLast (e) addLast (e)
Penghapusan dari Tail pollLast () removeLast ()
Pengambilan dari Tail peekLast () getLast ()

3. Menggunakan Metode

Mari kita lihat beberapa contoh sederhana tentang bagaimana kita dapat menggunakan ArrayDeque .

3.1. Menggunakan ArrayDeque sebagai Stack

Kita akan mulai dengan contoh bagaimana kita dapat memperlakukan kelas sebagai Stack - dan mendorong sebuah elemen:

@Test public void whenPush_addsAtFirst() { Deque stack = new ArrayDeque(); stack.push("first"); stack.push("second"); assertEquals("second", stack.getFirst()); } 

Mari kita lihat juga bagaimana kita dapat memunculkan elemen dari ArrayDeque - saat digunakan sebagai Stack:

@Test public void whenPop_removesLast() { Deque stack = new ArrayDeque(); stack.push("first"); stack.push("second"); assertEquals("second", stack.pop()); } 

The pop metode melempar NoSuchElementException ketika tumpukan kosong.

3.2. Menggunakan ArrayDeque sebagai Antrian

Sekarang mari kita mulai dengan contoh sederhana yang menunjukkan bagaimana kita dapat menawarkan elemen dalam ArrayDeque - bila digunakan sebagai Antrian sederhana :

@Test public void whenOffer_addsAtLast() { Deque queue = new ArrayDeque(); queue.offer("first"); queue.offer("second"); assertEquals("second", queue.getLast()); } 

Dan mari kita lihat bagaimana kita bisa mengumpulkan elemen dari ArrayDeque , juga saat digunakan sebagai Queue :

@Test public void whenPoll_removesFirst() { Deque queue = new ArrayDeque(); queue.offer("first"); queue.offer("second"); assertEquals("first", queue.poll()); } 

The jajak pendapat Metode mengembalikan nol nilai jika antrian kosong.

4. Bagaimana ArrayDeque Diterapkan

Di bawah tenda, ArrayDeque didukung oleh sebuah array yang menggandakan ukurannya saat diisi.

Awalnya, array diinisialisasi dengan ukuran 16. Ini diimplementasikan sebagai antrian berujung ganda di mana ia mempertahankan dua penunjuk yaitu kepala dan ekor.

Mari kita lihat logika ini beraksi - pada level tinggi.

4.1. ArrayDeque sebagai Stack

Seperti yang bisa dilihat, saat pengguna menambahkan elemen menggunakan metode push , ia menggerakkan penunjuk kepala satu per satu.

Saat kita meletuskan sebuah elemen, itu menetapkan elemen di posisi kepala sebagai null sehingga elemen tersebut dapat dikumpulkan sampah, dan kemudian memindahkan kembali penunjuk kepala satu per satu.

4.2. ArrayDeque sebagai Antrian

Saat kita menambahkan elemen menggunakan metode penawaran , itu menggerakkan penunjuk ekor satu per satu.

Sementara saat pengguna melakukan polling sebuah elemen, ia menyetel elemen di posisi kepala ke nol sehingga elemen tersebut bisa dikumpulkan sampahnya, dan kemudian memindahkan penunjuk kepala.

4.3. Catatan tentang ArrayDeque

Terakhir, beberapa catatan yang perlu dipahami dan diingat tentang implementasi khusus ini:

  • Ini tidak aman untuk benang
  • Elemen nol tidak diterima
  • Bekerja secara signifikan lebih cepat daripada Stack yang disinkronkan
  • Merupakan antrian yang lebih cepat daripada LinkedList karena lokalitas referensi yang lebih baik
  • Kebanyakan operasi diamortisasi kompleksitas waktu yang konstan
  • Sebuah Iterator kembali oleh ArrayDeque adalah gagal-cepat
  • ArrayDeque secara otomatis menggandakan ukuran array ketika penunjuk kepala dan ekor bertemu satu sama lain saat menambahkan elemen

5. Kesimpulan

Dalam artikel singkat ini, kami mengilustrasikan penggunaan metode di ArrayDeque .

Implementasi dari semua contoh ini dapat ditemukan di proyek GitHub; ini adalah proyek berbasis Maven, jadi semestinya mudah untuk mengimpor dan menjalankan apa adanya.