Hướng dẫn và ví dụ Java Queue

Queue
Các phương thức của Queue
Examples

1. Queue

Queue (hàng đợi) là một Interface con của Collection, vì vậy nó có đầy đủ các tính năng của Collection. Nó có các phương thức để bạn truy cập hoặc loại bỏ phần tử đầu tiên, và phương thức để chèn một phần tử vào hàng đợi. Nếu bạn muốn truy cập vào một phần tử nào đó bạn phải loại bỏ tất cả các phần tử đứng trước nó ra khỏi hàng đợi.

Queue là một Collection cho phép phần tử trùng lặp nhưng không cho phép phần tử null.

Một ví dụ thường thấy là một hàng đợi tại một quầy Bar. Tại một thời điểm chỉ người đứng đầu tiên trên hàng đợi được phục vụ, người mới đến sẽ được chèn vào một vị trí nào đó trên hàng đợi, nó có thể không phải là vị trí cuối cùng, điều này phụ thuộc vào kiểu hàng đợi và độ ưu tiên của người mới đến.

public interface Queue<E> extends Collection<E>

Hệ thống phân cấp các interface trong Java Collection Framework:

Hệ thống phân cấp các lớp trong nhóm Queue:

Mối quan hệ giữa các interface và các lớp trong nhóm Queue:

LinkedList
ArrayDeque
PriorityQueue
LinkedBlockingDeque
ConcurrentLinkedQueue
LinkedTransferQueue
ArrayBlockingQueue
ConcurrentLinkedDeque
DelayQueue
LinkedBlockingQueue
PriorityBlockingQueue
SynchronousQueue

LinkedList là một lớp đặc biệt, nó vừa thuộc nhóm List vừa thuộc nhóm Queue:

Hướng dẫn và ví dụ Java LinkedList

2. Các phương thức của Queue

Ngoài các phương thức được thừa kế từ Collection, Queue cũng có thêm các phương thức của riêng nó:

boolean add(E e);
boolean offer(E e);

E remove();
E poll();

E element();
E peek();

	Throws exception	Returns special value
Insert	boolean add(E)	boolean offer(E)
Remove	E remove()	E poll()
Examine	E element()	E peek()

boolean add(E)* / boolean offer(E)

boolean add(E)	Chèn một phần tử vào Queue. Nếu không còn chỗ trống để chèn phương thức này sẽ ném ra ngoại lệ. Phương thức trả về true nếu việc chèn thành công.
boolean offer(E)	Chèn một phần tử vào Queue. Nếu Queue không còn chỗ trống hoặc chèn không thành công phương thức trả về false.

Khi một phần tử được chèn vào Queue, vị trí của nó được quyết định bởi kiểu Queue và độ ưu tiên của phần tử, bạn không thể chỉ định vị trí của nó.

Tuỳ vào kiểu Queue mà bạn đang sử dụng, nó có thể giới hạn số lượng các phần tử, hoặc tự động tăng kích thước.

E remove()* / E poll()

E remove()	Trả về phần tử đầu tiên của Queue đồng thời loại bỏ nó ra khỏi Queue. Phương thức này ném ra ngoại lệ nếu Queue không có phần tử nào.
E poll()	Trả về phần tử đầu tiên của Queue đồng thời loại bỏ nó ra khỏi Queue. Phương thức này trả về null nếu Queue không có phần tử nào.

E element() * / E peek()

E element()	Trả về phần tử đầu tiên của Queue nhưng không loại bỏ nó ra khỏi Queue. Phương thức này ném ra ngoại lệ nếu Queue không có phần tử nào.
E peek()	Trả về phần tử đầu tiên của Queue nhưng không loại bỏ nó ra khỏi Queue. Phương thức này trả về null nếu Queue không có phần tử nào.

3. Examples

LinkedList(Queue)

LinkedList đại diện cho một hàng đợi truyền thống. Phương thức add/offer sẽ thêm một phần tử vào đuôi của hàng đợi này.

LinkedListEx1.java

package org.o7planning.queue.ex;

import java.util.LinkedList;
import java.util.Queue;

public class LinkedListEx1 {

    public static void main(String[] args) {
       // Create Queue     
       Queue<String> queue = new LinkedList<String>();
       
       queue.offer("One");
       queue.offer("Two");
       queue.offer("Three");
       queue.offer("Four");
       queue.offer("Five");
       
       String current;
       
       while((current = queue.poll())!= null) {
           System.out.println(current);
       }
    }
}

Output:

One
Two
Three
Four
Five

PriorityQueue

PriorityQueue là một Queue có khả năng tự động xắp xếp các phần tử theo thứ tự ưu tiên của chúng hoặc theo một Comparator được cung cấp. Điều này có nghĩa là một phần tử được chèn vào PriorityQueue có thể không phải ở vị trí cuối cùng.

Ví dụ, một PriorityQueue<String> sắp xếp thứ tự các phần tử theo alphabet.

PriorityQueueEx1.java

package org.o7planning.queue.ex;

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueEx1 {

    public static void main(String[] args) {
       // Create Queue     
       Queue<String> queue = new PriorityQueue<String>();
       
       queue.offer("One");
       queue.offer("Two");
       queue.offer("Three");
       queue.offer("Four");
       queue.offer("Five");
       
       String current;
       
       while((current = queue.poll())!= null) {
           System.out.println(current);
       }
    }
}