Hàng đợi tròn là hàng đợi trong đó tất cả các phần tử được nối với nhau để tạo thành một hình tròn. Hàng đợi tròn có thể được thực hiện với mảng và danh sách được liên kết. Trong triển khai mảng, phía trước và phía sau bao quanh [hoạt động modulo] đến đầu mảng. Trong thực hiện danh sách được liên kết, nút cuối cùng liên kết trở lại nút phía trước. Trong bài đăng này, triển khai hàng đợi vòng tròn đang sử dụng mảng
Mục lục
Bản đồ triển khai hàng đợi
Phần 1 – Triển khai hàng đợi với danh sách liên kết
Phần 2 – Triển khai hàng đợi vòng với mảng
Phần 3 – Danh sách liên kết vòng [Circular queue]
Phần 4 – Danh sách liên kết kép [Deque]
Enqueue trong việc thực hiện hàng đợi vòng tròn
Đầu tiên chúng ta khai báo một mảng. Trong Java, nếu bạn sử dụng mảng [không phải ArrayList], bạn phải chỉ định maxSize. Nếu mảng đạt đến kích thước tối đa, bạn không thể thêm phần tử nữa. front Index và rear Index là chỉ số của phần tử phía trước và phần tử phía sau. Khi hàng đợi trống, chúng là -1. Độ dài là để theo dõi số lượng phần tử trong hàng đợi
Để enqueue là thêm phần tử ở phía sau. rearIndex được tăng thêm 1. Nếu rearIndex vượt quá maxSize, chúng tôi sử dụng thao tác modulo [hoặc “mod”, “%”] để có được rearIndex mới với phạm vi maxSize
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
lớp công khai CircularQueueArray {
riêng tư T[] queueArray;
private int maxSize; // Kích thước của Thông tư
riêng tư int frontIndex, rearIndex;
riêng tư int độ dài = 0;
// hàm tạo, Thời gian O[1], Không gian O[1]
@SuppressWarnings["unchecked"]