Tiếp tục series hướng dẫntoàn tập. Bài viết này mình sẽ giúp bạn học về. Đây là một dạng cấu trúc dữ liệu mà lập trình viên Java nào cũng cần phải nắm được.
Tất tần tật về Queue trong Java
Bài viết này bao gồm các phần sau đây:
-
Queue Interface
-
Deque Interface
-
LinkedList
-
ArrayDeque
-
BlockingQueue Interface
-
ArrayBlockingQueue Interface
-
LinkedBlockingQueue
Ok, chúng ta sẽ bắt đầu tìm hiểu phần đầu tiên.
Tóm Tắt
PHẦN 1: QUEUE INTERFACE TRONG JAVA
Queue interface của Java Collection Framework cung cấp chức năng của cấu trúc dữ liệu hàng đợi.
Nếu bạn chưa hiểu về Java Collection Framework thì vui lòng đọc lại bài viết này: List trong Java
Queue mở rộng (kế thừa) Collection interface.
1.1. CÁC CLASS TRIỂN KHAI QUEUE INTERFACE
Vì Queue là một interface, nên chúng ta không thể triển khai trực tiếp interface đó.
Để sử dụng các tính năng của cấu trúc dữ liệu Queue, chúng ta cần sử dụng các class triển khai nó:
-
ArrayDeque
-
LinkedList
-
PriorityQueue
Các class triển khai Queue interface trong Java
1.2. CÁC INTERFACE KẾ THỪA QUEUE
Trong Java, Queue interface cũng được kế thừa bởi nhiều subinterface khác nhau:
-
Deque
-
BlockingQueue
-
BlockingDeque
Các interface kế thừa Queue interface trong Java
1.3. CÁCH LÀM VIỆC CỦA CẤU TRÚC DỮ LIỆU QUEUE
Queue có nghĩa là “Hàng đợi” (bạn có thể liên tưởng đến việc xếp hàng vậy)
Trong hàng đợi (trong Queue), các phần tử được lưu trữ và truy cập theo cách nhập trước, xuất trước.
Có nghĩa là:
-
Khi thêm phần tử thì sẽ xếp vào phía sau
-
Khi loại bỏ phần tử thì sẽ loại bỏ từ phía trước
Cách làm việc của cấu trúc dữ liệu Queue
6 Cấu trúc dữ liệu cần phải biết
> Đọc thêm:
1.4. CÁCH SỬ DỤNG QUEUE TRONG JAVA.
Trong Java, chúng ta phải import package java.util.Queue để sử dụng Queue.
// LinkedList triển khai Queue
Queue
<
String
>
animal1
=
new
LinkedList
<>();
// Array triển khai Queue
Queue
<
String
>
animal2
=
new
ArrayDeque
<>();
// Priority Queue triển khai Queue
Queue
<
String
>
animal3
=
new
PriorityQueue
<>();
Ở đây, chúng ta đã tạo các đối tượng animal1, animal2 và animal3 của các class LinkedList, ArrayDeque và PriorityQueue tương ứng.
Các đối tượng này có thể sử dụng các tính năng của Queue interface.
1.5. CÁC PHƯƠNG THỨC CỦA QUEUE TRONG JAVA
Queue interface có tất cả các phương thức của Collection interface. Đó là bởi vì Collection là interface cha của Queue.
Một số phương thức thường được sử dụng của Queue interface là:
-
add()– Chèn phần tử đã chỉ định vào hàng đợi. Nếu tác vụ thành công,add()trả vềtrue, nếu không nó sẽ ném ra một ngoại lệ. -
offer()– Chèn phần tử đã chỉ định vào hàng đợi. Nếu tác vụ thành công,offer()trả vềtrue, nếu không nó sẽ trả vềfalse. -
element()– Trả về phần đầu của hàng đợi. Ném một ngoại lệ nếu hàng đợi trống. -
peek()– Trả về đầu của hàng đợi. Trả vềnullnếu hàng đợi trống. -
remove()– Trả về và xóa phần đầu của hàng đợi. Ném một ngoại lệ nếu hàng đợi trống. -
poll()– Trả về và loại bỏ phần đầu của hàng đợi. Trả vềnullnếu hàng đợi trống.
1.6. VÍ DỤ TRIỂN KHAI QUEUE INTERFACE TRONG JAVA
Để hiểu thêm về Queue và cách làm việc với cấu trúc dữ liệu Queue, chúng ta cùng làm ví dụ sau:
TRIỂN KHAI CLASS LINKEDLIST
Chúng ta sẽ thử làm ví dụ triển khai class LinkedList.
// import package cần thiết
import
java.util.Queue;
import
java.util.LinkedList;
class
Main
{
public
static
void
main
(
String
[]
args
) {
// Tạo Queue sử dụng class LinkedList
Queue
<
Integer
>
numbers
=
new
LinkedList
<>();
// Chèn phần tử chỉ định vào Queue bằng phương thức offer
numbers
.
offer
(
1
);
numbers
.
offer
(
2
);
numbers
.
offer
(
3
);
System
.
out
.
println
(
“Queue: “
+ numbers);
// Truy cập các phần tử trong Queue
int
accessedNumber
=
numbers
.
peek
();
System
.
out
.
println
(
“Truy cập phần tử: “
+ accessedNumber);
// Loại bỏ các phần tử tron Queue
int
removedNumber
=
numbers
.
poll
();
System
.
out
.
println
(
“Loại bỏ phần tử: “
+ removedNumber);
System
.
out
.
println
(
“Cập nhật Queue: “
+ numbers);
}
}
Khi chạy chương trình, kết quả là:
Queue: [1, 2, 3]
Truy cập phần tử: 1
Loại bỏ phần tử: 1
Cập nhật Queue: [2, 3]
Hãy để ý cách loại bỏ phần tử trong cấu trúc dữ liệu Queue. Bạn thấy có gì đặc biệt không? 😀
TRIỂN KHAI CLASS PRIORITYQUEUE
Đây là một ví dụ khác về Queue mà sử dụng class PriorityQueue
// import package cần thiết
import
java.util.Queue;
import
java.util.PriorityQueue;
class
Main
{
public
static
void
main
(
String
[]
args
) {
// Tạo Queue sử dụng class PriorityQueue
Queue
<
Integer
>
numbers
=
new
PriorityQueue
<>();
// Chèn phần tử vào Queue bằng phương thức offer
numbers
.
offer
(
5
);
numbers
.
offer
(
1
);
numbers
.
offer
(
2
);
numbers
.
offer
(
4
);
System
.
out
.
println
(
“Queue: “
+ numbers);
// Truy cập phần tử trong Queue
int
accessedNumber
=
numbers
.
peek
();
System
.
out
.
println
(
“Truy cập phần tử: “
+ accessedNumber);
// Loại bỏ phần tử trong Queue
int
removedNumber
=
numbers
.
poll
();
System
.
out
.
println
(
“Loại bỏ phần tử: “
+ removedNumber);
System
.
out
.
println
(
“Cập nhật Queue: “
+ numbers);
}
}
Khi chạy chương trình, kết quả nhận được là:
Queue: [1, 4, 2, 5]
Truy cập phần tử: 1
Loại bỏ phần tử: 1
Cập nhật Queue: [2, 4, 5]
Kiểu cấu trúc dữ liệu dạng First in, Firt out mà trông không giống lắm nhỉ?
Lẽ ra là “Chèn vào từ phía sau” thì kết quả phải là: [5, 1, 2, 4] chứ đúng không? 😀
Đó là vì cách hoạt động của PriorityQueue hơi khác một tý.
Trong các phần tiếp theo, chúng ta sẽ tìm hiểu về kỹ hơn về các subinterface khác nhau của Queue để bạn hiểu rõ vấn đề này.
Còn tiếp…
—
HỌC VIỆN ĐÀO TẠO CNTT NIIT – ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học thực tế + Tuyển dụng ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 – 0383.180086
Email: [email protected]
Fanpage: https://facebook.com/NIIT.ICT/
#niit #icthanoi #niithanoi #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp
