Giao diện Deque Java

Java Deque là một cấu trúc dữ liệu kết hợp Queue và Stack thông thường. Bạn có thể thêm và bớt các phần tử ở cả phần đầu và phần đuôi của Deque. Trong hàng đợi “truyền thống”, bạn thêm các phần tử vào cuối dòng (sau phần tử cuối cùng) và xóa các phần tử khỏi phần đầu của hàng đợi. Nguyên tắc này được gọi là First In First Out (FIFO) và nó hoạt động giống như bất kỳ dòng khách hàng thông thường nào trong đời thực. Trong Hàng đợi Java là một Giao diện, một phần của Khung bộ sưu tập. Ngoài ra còn có một cấu trúc dữ liệu quan trọng được gọi là Stack, một danh sách hoạt động với các phần tử theo nguyên tắc hoàn toàn ngược lại, LIFO — vào sau, ra trước. Nó cũng giống như một chồng đĩa, việc thêm bớt chỉ có thể thực hiện ở trên cùng.

Xếp hàng vs Deque

Deque là một loại Hàng đợi khá kỳ lạ: bạn có thể thêm các phần tử mới vào cả phần đuôi và phần đầu của dòng. Câu chuyện tương tự với việc xóa: bạn có thể xóa phần tử cuối cùng hoặc phần tử đầu tiên khỏi cấu trúc này. Do đó, nó dường như là sự kết hợp giữa Stack và Queue. Cái tên “Deque” có nghĩa là “Hàng đợi kết thúc kép”. “Deque” được phát âm giống như một "bộ bài" và bạn biết gì không? Nó hơi giống với một cỗ bài thật: bạn có thể lấy một quân bài từ dưới cùng hoặc trên cùng của bộ bài đó. Bạn muốn thêm hoặc bớt các phần tử từ cả hai phía của một số cấu trúc tuyến tính? Sử dụng Deque. Java 8 hoặc hầu hết mọi phiên bản khác đều hỗ trợ nó. Hãy tưởng tượng một viên gạch lego điển hình và “tháp” một cột làm bằng gạch. Bạn có thể thêm một viên gạch mới vào đỉnh tháp hoặc xuống đáy. Bạn cũng có thể loại bỏ một viên gạch từ cả hai bên. Ở đây chúng tôi có một ví dụ: chúng tôi thêm tất cả các viên gạch màu vàng lên trên cùng và tất cả các viên gạch màu đỏ vào dưới cùng. Chúng tôi sẽ sớm chứng minh ví dụ này bằng mã Java. Vì vậy, bạn có thể enqueue và dequeue từ cả hai đầu của Deque Java, điều đó có nghĩa là bạn có thể sử dụng Deque làm cả hàng đợi và ngăn xếp. Đọc về Ngăn xếp trong Java: Ngăn xếp Java 101: Tìm hiểu sâu về Lớp ngăn xếp Đọc về Hàng đợi trong Java: Giao diện hàng đợi Java và các triển khai của nó

Các tính năng của Deque

• Deque trong Java là một Giao diện, mà việc triển khai cung cấp sự hỗ trợ của một mảng có thể thay đổi kích thước. Vì vậy, bạn có một mảng dung lượng không hạn chế và bạn có thể thêm các yếu tố mới theo nhu cầu của mình.
• Deque không hỗ trợ truy cập đồng thời theo nhiều luồng
• Deque không an toàn cho luồng trong trường hợp không có đồng bộ hóa bên ngoài.
• Không cho phép phần tử Null trong mảng deque.

Deque Khai báo giao diện Java

public interface Deque<E> extends Queue<E>

Các phương thức Deque Java

java.util.Deque là một Giao diện mở rộng Giao diện Hàng đợi Java và đại diện cho một hàng đợi hai đầu. Vì vậy, bạn có thể sử dụng tất cả các phương thức Java Queue khi làm việc với Deque. Mặc dù Deque không mở rộng giao diện Stack, nhưng giao diện Deque xác định các phương thức cho phép bạn thực hiện các thao tác ngăn xếp điển hình như push , peek và pop .

• boolean add(element) thêm một phần tử vào đuôi của Deque. Trả về true nếu thành công, ném IllegalStateException nếu hiện không có chỗ trống.
• addFirst(element) thêm một phần tử vào phần đầu của Deque.
• addLast(element) thêm một phần tử vào đuôi của Deque.
• offer(element) thêm một phần tử vào đuôi và trả về một giá trị boolean để giải thích liệu việc chèn có thành công hay không.
• offerFirst(element) thêm một phần tử vào phần đầu và trả về một giá trị boolean để giải thích liệu việc chèn có thành công hay không.
• offerLast(element) thêm một phần tử vào phần đuôi và trả về một giá trị boolean để giải thích liệu việc chèn có thành công hay không.
• iterator() trả về một iterator cho deque.
• giảm dầnIterator() trả về một trình vòng lặp có thứ tự ngược lại cho deque này.
• push(element) thêm một phần tử vào phần đầu.
• pop(element) xóa phần tử khỏi phần đầu và trả về phần tử đó.
• removeFirst() xóa phần tử ở đầu.
• removeLast() loại bỏ phần tử ở đuôi.
• poll() truy xuất và xóa phần đầu của hàng đợi được đại diện bởi deque này (nói cách khác, phần tử đầu tiên của deque này) hoặc trả về null nếu deque này trống.
• pollFirst() truy xuất và loại bỏ phần tử đầu tiên của deque này hoặc trả về null nếu deque này trống.
• pollLast() truy xuất và loại bỏ phần tử cuối cùng của deque này hoặc trả về null nếu deque này trống.
• peek() truy xuất, nhưng không xóa, phần đầu của hàng đợi được đại diện bởi deque này (nói cách khác, phần tử đầu tiên của deque này) hoặc trả về null nếu deque này trống.
• peekFirst() truy xuất, nhưng không xóa, phần tử đầu tiên của deque này hoặc trả về null nếu deque này trống.
• peekLast() truy xuất, nhưng không xóa, phần tử cuối cùng của deque này hoặc trả về null nếu deque này trống.

Ở đây trong bảng dưới đây, tất cả các phương pháp được chia theo nhóm. Như bạn có thể thấy, có nhiều phương pháp khác nhau để thêm và xóa một phần tử. Ví dụ: cả removeFirst() và pop() đều xóa phần tử đầu tiên khỏi deque. Cái thứ hai "đến" từ ngăn xếp. Điều đó có nghĩa là nếu bạn chỉ sử dụng ArrayDeque của mình làm ngăn xếp, hãy sử dụng pop() để xóa, push() để thêm và peek() để kiểm tra. Điều này làm cho mã của bạn hợp lý hơn đối với các nhà phát triển khác.

Triển khai Deque

Java Deque là một giao diện và có các triển khai trong API Bộ sưu tập Java:

• java.util.LinkedList // Triển khai danh sách và Deque
• java.util.ArrayDeque //Triển khai Deque, thư viện Java

Lớp LinkedList sử dụng danh sách liên kết kép bên trong để mô hình hóa hàng đợi hoặc deque. Lớp ArrayDeque lưu trữ các phần tử bên trong một mảng. Nếu số lượng phần tử vượt quá dung lượng của mảng, một mảng mới sẽ được phân bổ và tất cả các phần tử được di chuyển qua. Điều đó có nghĩa là ArrayDeque phát triển theo nhu cầu.

lớp ArrayDeque

Lớp ArrayDeque <E> là một hàng đợi hai chiều chung, kế thừa chức năng từ lớp AbstractCollection và sử dụng giao diện Deque. ArrayDeque cung cấp phương tiện sử dụng deque và mảng có thể thay đổi kích thước. Ban đầu, mảng được khởi tạo với kích thước 16. Nó được thực hiện như một hàng đợi hai chiều, nơi nó hỗ trợ hai con trỏ, cụ thể là đầu và đuôi. Nó kế thừa lớp AbstractCollection và triển khai giao diện Deque . Những điểm quan trọng về lớp ArrayDeque là:

• Bạn có thể thêm bớt các phần tử ở phần đuôi và phần đầu của ArrayDeque
• Các phần tử null không được phép
• ArrayDeque không phải là luồng an toàn, trong trường hợp không có đồng bộ hóa bên ngoài.
• ArrayDeque không có hạn chế về dung lượng.

Trình xây dựng lớp ArrayDeque

• ArrayDeque() tạo một hàng đợi trống.
• ArrayDeque(Collection <? Extends E> collection) tạo một hàng đợi chứa đầy các phần tử của bộ sưu tập Collection.
• ArrayDeque(int capacity) tạo hàng đợi với dung lượng dung lượng ban đầu . Nếu bạn không chỉ định dung lượng ban đầu, dung lượng mặc định là 16.

Ví dụ Java Deque — ArrayDeque

Bạn còn nhớ ví dụ Tháp Lego ở đầu bài viết không? Hãy tạo một lớp học Xây tháp một cột bằng Lego Bricks. Gạch có thể có màu đỏ, vàng hoặc xanh. Quy tắc xây dựng Tháp của chúng tôi: chúng tôi đặt những viên gạch màu đỏ ở dưới cùng và những viên gạch màu vàng ở trên cùng. Ví dụ về Deque Java lớn

//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 +
              '}';
   }
}

Đây là lớp Tower của chúng tôi. Chúng tôi bắt đầu một tòa tháp. Tháp bắt đầu phụ thuộc vào số lượng màu đỏ và vàng. Chúng ta có thể thêm gạch vào tháp hoặc loại bỏ nó. Chúng tôi thêm gạch lên trên nếu nó có màu vàng và thêm nó vào dưới cùng nếu nó có màu đỏ.

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();

   }

}

Kết quả chạy chương trình này:

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

Đợi đã, cái gì?? Tại sao màu đỏ ở trên cùng? Không, họ không. Họ chỉ in ra bảng điều khiển bắt đầu từ cái đầu tiên (dưới cùng) đến cái cuối cùng (trên cùng). Vì vậy, nếu bạn muốn xem một cái gì đó giống như trong hình với những viên gạch ở trên, bạn có thể thay đổi phương thức drawTower của lớp LegoTower. Đó là một nhiệm vụ rất dễ dàng!

LinkedList

Giao diện Danh sách giữ nguyên trình tự thêm mục và cho phép truy cập mục theo chỉ mục. Deque là hàng đợi hai chiều và nó hỗ trợ thêm và xóa các phần tử từ cả hai phía. LinkedList chủ yếu được biết đến như một triển khai Danh sách, nhưng lớp này cũng triển khai Deque và nó cho phép chúng ta tạo một hàng đợi hai chiều bao gồm bất kỳ đối tượng nào kể cả null. LinkedList là một tập hợp các phần tử. Chúng ta có thể thấy nó trong mã nguồn của lớp, lần này hãy chú ý đến các trường: Ở đây chúng tôi thêm một ví dụ, nhưng nếu bạn muốn tìm hiểu thêm về LinkedList, chào mừng bạn đến với bài viết CodeGym này .

Triển khai danh sách liên kết trong Java, thêm và xóa các phần tử. Ví dụ

Hãy thử các hoạt động này trong thực tế. Đầu tiên, triển khai Java LinkedList: tạo LinkedList gồm các chuỗi, thêm vào đó 3 phần tử. Sau đó loại bỏ một, sau đó thêm một ở giữa.

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);
   }

Kết quả chạy chương trình này:

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]