Antarmuka Java Deque

Java Deque adalah struktur data yang menggabungkan Queue dan Stack biasa. Anda dapat menambah dan menghapus elemen pada kepala dan ekor Deque. Dalam antrian "tradisional" Anda menambahkan elemen ke ujung garis (setelah elemen terakhir) dan menghapus elemen dari kepala antrian. Prinsip ini disebut First In First Out (FIFO) dan berfungsi seperti jalur pelanggan biasa di kehidupan nyata. Di Java Queue adalah Antarmuka, bagian dari Kerangka Koleksi. Ada juga struktur data penting yang disebut Stack, sebuah daftar yang bekerja dengan elemen-elemen dalam prinsip yang benar-benar terbalik, LIFO — last in, first out. Mirip dengan tumpukan piring, menambah atau menghapus hanya mungkin di bagian atas.

Antrian vs Deque

Deque adalah jenis Queue yang agak aneh: Anda dapat menambahkan elemen baru baik ke ekor maupun kepala baris. Cerita yang sama dengan menghapus: Anda dapat menghapus elemen terakhir atau pertama dari struktur ini. Karenanya, ini tampaknya merupakan campuran dari Stack dan Queue. Nama "Deque" berarti "Antrian Berakhir Ganda". "Deque" diucapkan seperti "setumpuk" kartu dan tahukah Anda? Ini agak mirip dengan setumpuk kartu asli: Anda dapat mengambil kartu dari bagian bawah atau atas setumpuk tersebut. Ingin menambah atau menghapus elemen dari kedua sisi struktur linier? Gunakan Deque. Java 8 atau hampir semua versi lainnya mendukungnya. Bayangkan bata lego yang khas dan "menara" satu kolom yang terbuat dari batu bata. Anda dapat menambahkan batu bata baru ke atas menara atau ke bawah. Anda juga bisa melepas bata dari kedua sisi. Di sini kami memiliki contoh: kami menambahkan semua bata kuning ke atas dan semua merah ke bawah. Kami akan mendemonstrasikan contoh ini dengan kode Java segera. Jadi Anda bisa enqueue dan dequeue dari kedua ujung Java Deque, itu artinya Anda bisa menggunakan Deque sebagai antrian dan stack. Baca tentang Stack di Java: Java Stack 101: Mempelajari Kelas Stack Baca tentang Queue di Java: Java Queue Interface dan implementasinya

Fitur Deque

• Deque di Java adalah Antarmuka, yang implementasinya memberikan dukungan dari array yang dapat diubah ukurannya. Jadi, Anda memiliki berbagai kapasitas tanpa batasan dan Anda dapat menambahkan elemen baru sesuai kebutuhan Anda.
• Akses bersamaan oleh banyak utas tidak didukung oleh Deque
• Deque tidak aman untuk thread jika tidak ada sinkronisasi eksternal.
• Tidak ada elemen Null yang diizinkan dalam array deque.

Deque Java Interface deklarasi

public interface Deque<E> extends Queue<E>

Metode Java Deque

java.util.Deque adalah Antarmuka yang memperluas Antarmuka Antrean Java dan mewakili antrean ujung ganda. Jadi Anda bisa menggunakan semua metode Java Queue saat bekerja dengan Deque. Meskipun Deque tidak memperluas antarmuka Stack, antarmuka Deque mendefinisikan metode yang memungkinkan Anda melakukan operasi tumpukan biasa seperti push , peek dan pop .

• boolean add(element) menambahkan elemen ke ekor Deque. Mengembalikan true jika berhasil, melontarkan IllegalStateException jika saat ini tidak ada ruang yang tersedia.
• addFirst(element) menambahkan elemen ke kepala Deque.
• addLast(element) menambahkan elemen ke ekor Deque.
• offer(element) menambahkan elemen ke ekor dan mengembalikan boolean untuk menjelaskan jika penyisipan berhasil.
• offerFirst(element) menambahkan elemen ke kepala dan mengembalikan boolean untuk menjelaskan jika penyisipan berhasil.
• offerLast(element) menambahkan elemen ke ekor dan mengembalikan boolean untuk menjelaskan jika penyisipan berhasil.
• iterator() mengembalikan iterator untuk deque.
• descendingIterator() mengembalikan iterator yang memiliki urutan terbalik untuk deque ini.
• push(element) menambahkan elemen ke kepala.
• pop(element) menghapus elemen dari kepala dan mengembalikannya.
• removeFirst() menghapus elemen di kepala.
• removeLast() menghapus elemen di bagian ekor.
• poll() mengambil dan menghapus kepala antrian yang diwakili oleh deque ini (dengan kata lain, elemen pertama dari deque ini), atau mengembalikan nol jika deque ini kosong.
• pollFirst() mengambil dan menghapus elemen pertama dari deque ini, atau mengembalikan nol jika deque ini kosong.
• pollLast() mengambil dan menghapus elemen terakhir dari deque ini, atau mengembalikan nol jika deque ini kosong.
• peek() mengambil, tetapi tidak menghapus, kepala antrian yang diwakili oleh deque ini (dengan kata lain, elemen pertama dari deque ini), atau mengembalikan nol jika deque ini kosong.
• peekFirst() mengambil, tetapi tidak menghapus, elemen pertama dari deque ini, atau mengembalikan null jika deque ini kosong.
• peekLast() mengambil, tetapi tidak menghapus, elemen terakhir dari deque ini, atau mengembalikan nol jika deque ini kosong.

Di sini, di tabel di bawah ini, semua metode dibagi berdasarkan grup. Seperti yang Anda lihat ada banyak metode berbeda untuk menambah dan menghapus elemen. Misalnya, keduanya removeFirst() dan pop() menghapus elemen pertama dari deque. Yang kedua "datang" dari tumpukan. Itu berarti jika Anda menggunakan ArrayDeque sebagai tumpukan saja, gunakan pop() untuk menghapus, tekan() untuk menambahkan, dan peek() untuk memeriksa. Ini membuat kode Anda lebih masuk akal untuk pengembang lain.

Implementasi Deque

Java Deque adalah antarmuka dan memiliki implementasi di Java Collections API:

• java.util.LinkedList // Implementasi daftar dan Deque
• java.util.ArrayDeque // Implementasi Deque, perpustakaan Java

Kelas LinkedList menggunakan double-linked list secara internal untuk memodelkan antrian atau deque. Kelas ArrayDeque menyimpan elemen secara internal dalam sebuah array. Jika jumlah elemen melebihi volume array, array baru dialokasikan, dan semua elemen dipindahkan. Itu berarti ArrayDeque tumbuh berdasarkan kebutuhan.

kelas ArrayDeque

Kelas ArrayDeque <E> adalah antrian dua arah umum, mewarisi fungsionalitas dari kelas AbstractCollection dan menggunakan antarmuka Deque. ArrayDeque menyediakan fasilitas untuk menggunakan deque dan array yang dapat diubah ukurannya. Awalnya, array diinisialisasi dengan ukuran 16. Ini diimplementasikan sebagai antrian dua arah, di mana ia mendukung dua pointer, yaitu kepala dan ekor. Itu mewarisi kelas AbstractCollection dan mengimplementasikan antarmuka Deque . Poin penting tentang kelas ArrayDeque adalah:

• Anda dapat menambah atau menghapus elemen dari ekor dan kepala ArrayDeque
• Elemen kosong tidak diperbolehkan
• ArrayDeque tidak aman untuk thread, karena tidak adanya sinkronisasi eksternal.
• ArrayDeque tidak memiliki batasan kapasitas.

Konstruktor kelas ArrayDeque

• ArrayDeque() membuat antrian kosong.
• ArrayDeque (Collection <? Extends E> collection) membuat antrian yang diisi dengan elemen koleksi Collection.
• ArrayDeque (kapasitas int) membuat antrian dengan kapasitas kapasitas awal . Jika Anda tidak menentukan kapasitas awal, kapasitas default adalah 16.

Contoh Java Deque — ArrayDeque

Ingat Contoh Menara Lego dari awal artikel? Mari buat kelas untuk Membangun Menara satu kolom yang terbuat dari Batu Bata Lego. Batu bata bisa berwarna merah, kuning atau biru. Aturan membangun Menara kami: kami meletakkan bata merah di bawah dan bata kuning di atas. Contoh Big Java Deque

//enum with colors
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Inilah kelas Menara kami. Kami memulai menara. Menara yang dimulai tergantung pada jumlah merah dan kuning. Kita bisa menambahkan batu bata ke menara atau menghilangkannya. Kami menambahkan bata di atas jika berwarna kuning dan menambahkannya ke bawah jika berwarna merah.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

Hasil menjalankan program ini:

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements:
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

Tunggu apa?? Mengapa merah di atas? Tidak, mereka tidak. Mereka hanya mencetak ke konsol mulai dari yang pertama (bawah) hingga yang terakhir (atas). Jadi jika Anda ingin melihat seperti pada gambar dengan batu bata di atas, Anda dapat mengubah metode drawTower dari kelas LegoTower. Ini adalah tugas yang sangat mudah!

LinkedList

Antarmuka Daftar menyimpan urutan penambahan item dan memungkinkan akses ke item berdasarkan indeks. Deque adalah antrian dua arah, dan mendukung penambahan dan penghapusan elemen dari kedua sisi. LinkedList terutama dikenal sebagai implementasi Daftar, tetapi kelas ini juga mengimplementasikan Deque, dan ini memungkinkan kita membuat antrean dua arah yang terdiri dari objek apa pun termasuk null. LinkedList adalah kumpulan elemen. Kita bisa melihatnya di sumber kode kelas, kali ini perhatikan bidangnya: Di sini kami menambahkan satu contoh, tetapi jika Anda ingin mempelajari lebih lanjut tentang LinkedList, selamat datang di artikel CodeGym ini .

Implementasi daftar tertaut di Jawa, menambah dan menghapus elemen. Contoh

Mari kita coba operasi ini dalam praktik. Pertama, implementasi Java LinkedList: membuat LinkedList of Strings, menambahkan 3 elemen di sana. Kemudian hapus satu, lalu tambahkan satu di tengah.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Hasil menjalankan program ini:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]