hàng đợi

Đối với hầu hết mọi người, từ "hàng đợi" mang đến rất ít liên tưởng thú vị. Nhưng hôm nay chúng ta đang nói về các hàng đợi khác nhau — hàng đợi Java. Trong Java, hàng đợi là bất kỳ thứ gì kế thừa giao diện Hàng đợi , từ đó mở rộng giao diện Bộ sưu tập . Điều đó có nghĩa là hàng đợi có thể được coi như bộ sưu tập.

Hàng đợi trong Java hỗ trợ hai nguyên tắc hoạt động: FIFO và LIFO .

Nguyên tắc FIFO (Vào trước, Xuất trước) chi phối một hàng đợi thông thường — phần tử đầu tiên được thêm vào hàng đợi là phần tử đầu tiên rời khỏi nó.

Nguyên tắc LIFO (Last In, First Out) mô tả hành vi của ngăn xếp — phần tử cuối cùng được thêm vào hàng đợi là phần tử đầu tiên rời khỏi nó. Ví dụ: đây là cách bạn làm việc với một cỗ bài: bạn lần lượt lấy các quân bài trên cùng cho đến khi chạm đến cuối cỗ bài.

Hệ thống phân cấp hàng đợi trong Java trông như thế này:

Ở đây bạn có thể thấy Queue có 3 lớp triển khai: LinkedList , ArrayDeque và PriorityQueue . LinkedList và ArrayDeque kế thừa trực tiếp không phải Queue mà là Deque .

Deque là một giao diện đã được thêm vào trong Java 6. Nó bao gồm một số phương thức hữu ích cho hàng đợi và cho phép hàng đợi hoạt động như một hàng đợi hai đầu (hoặc hai chiều). Điều đó có nghĩa là nó có thể làFIFOvàLIFO.

Một trong hai hậu duệ của giao diện Deque là ArrayDeque . Nó hỗ trợ hàng đợi hai đầu cho phép bạn chèn và xóa các phần tử ở cả hai đầu. Nó cũng là một mảng động tự động tăng kích thước.

Ngoài ra còn có một lớp PriorityQueue , là lớp kế thừa trực tiếp của Queue : nó hoạt động khác với các lớp triển khai Deque .

PriorityQueue là hàng đợi ưu tiên tổ chức các phần tử theo thứ tự tự nhiên của chúng theo mặc định. Ở đây, việc sắp xếp sử dụng giao diện So sánh và So sánh . Nguyên tắc giống như với TreeSet hoặc TreeMap — các lớp sử dụng giao diện So sánh được và có thứ tự sắp xếp riêng.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Nếu bạn chạy ví dụ này, đây là những gì bạn sẽ thấy trong bảng điều khiển:

Vì chúng tôi đang làm việc với hàng đợi chứ không phải bộ sưu tập thông thường, nên chúng tôi cần xóa các phần tử khỏi danh sách. Để làm điều này, chúng tôi sử dụng cấu trúc này:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Giao diện Deque kế thừa các phương thức Queue và thêm một số phương thức thú vị của riêng nó:

Bây giờ chúng ta hãy xem xét một số phương pháp này trong thực tế.

Đầu tiên, hãy thêm một phần tử vào hàng đợi:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
  
        System.out.println(deque);
    

Bây giờ hãy lấy các giá trị từ hàng đợi:

	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The first element is: "+ deque.getFirst());
                          
        System.out.println("The last element is: " + deque.getLast());
                          
    }
    

Mã này hiển thị phần tử đầu tiên và cuối cùng của hàng đợi.

         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);
    

Chạy mã này, chúng tôi nhận được:

Sự khác biệt giữa pop() và poll() là pop() sẽ đưa ra một NoSuchElementException nếu danh sách là danh sách trống, nhưng poll() sẽ trả về null .

Bây giờ chúng ta sẽ xem xét các phương thức pollFirst() và pollLast() .

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);
    

Cả hai phương thức đều trả về và xóa một giá trị khỏi hàng đợi.

Đây là một ví dụ về việc sử dụng các phương thức peekFirst() và peekLast() :

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);
    

Cả hai phương thức đều trả về phần tử đầu tiên/cuối cùng khỏi hàng đợi và không xóa chúng. Nếu hàng đợi trống, null sẽ được trả về.

Làm tốt! Hôm nay chúng ta đã học cách làm việc với hàng đợi trong Java. Bây giờ bạn đã biết cách sử dụng chúng trong thực tế.