images
29/09/2022 09:10 am

Java Queue - Tại sao phải dùng kiểu cấu trúc dữ liệu này?

Giả sử bạn là người bán hàng, bạn muốn bán được càng nhiều hàng càng tốt. Hôm nay cửa hàng có dịp khuyến mãi lớn giảm giá 50% nên có quá đông khách hàng đến mua. Bạn chưa kịp thu tiền của người này thì người khác đã hỏi món đồ kia giá bao nhiêu.

Giả sử bạn là người bán hàng, bạn muốn bán được càng nhiều hàng càng tốt. Hôm nay cửa hàng có dịp khuyến mãi lớn giảm giá 50% nên có quá đông khách hàng đến mua. Bạn chưa kịp thu tiền của người này thì người khác đã hỏi món đồ kia giá bao nhiêu. Bạn bị quay như chong chóng và có thể dẫn tới nhầm lẫn trong việc thu và trả tiền cho khách. Chỉ một buổi sáng bạn đã quá tải và đành đóng cửa hàng để kiểm tra lại tiền và hàng hoá dù khách vẫn đang nườm nượp kéo đến.

Quá đau đầu trong việc bán hàng, bạn lên mạng tìm kiếm giải pháp....

Ngày hôm sau, bạn quyết định căng dây thành hàng dài và yêu cầu khách xếp hàng, lần lượt đi vào mới được phục vụ. Ai chen lấn sẽ được mời ra ngoài để phục vụ sau cùng.

Queue hay hàng đợi cũng vậy đó. Đó là cấu trúc dữ liệu mô phỏng việc xếp hàng để thực hiện xử lý. Ai đứng đầu hàng sẽ được xử lý trước, ai đứng sau sẽ được xử lý sau. Đây được gọi là nguyên tắc FIFO - First In First Out. 

Ưu điểm của việc ứng dụng Queue sẽ là: mọi người sẽ được công bằng trong xử lý và hệ thống không bị quá tải. Mô hình sử dụng cấu trúc dữ liệu Queue được áp dụng rộng rãi trong các hệ thống xử lý về Order, từ mua hàng tới đặt vé, từ ecommerce tới các lĩnh vực fintech như chứng khoán. 

📌1. Khai báo queue trong Java:

Có nhiều kiểu dữ liệu cho queue trong Java, bài này tôi sử dụng LinkedBlockingQueue.

BlockingQueue<Integer> queue = new LinkedBlockingQueue(); 

📌2. Thêm một phần tử vào queue:

queue.put(1);

queue.put(2);

Trong trường hợp này hàng đợi sẽ có các phần tử lần lượt là: 1,2. 

📌3. Lấy số phần tử trong queue:

queue.size(): sẽ trả về tổng số item trong queue, trường hợp này số lượng phần tử là 2. 

📌4. Lấy một phần tử khỏi queue: Luôn luôn lấy phần tử đầu tiên của hàng đợi nếu có và bỏ đi phần tử này khỏi queue.

int item = queue.take(); 

🌱Đặc điểm của LinkedBlockingQueue với method take() là chương trình sẽ treo lại cho tới khi có 1 item tồn tại trong queue, và khi đó giá trị trong queue mới được gán cho item. Điều này giúp chúng ta thuận tiện trong việc xử lý vòng lặp để lấy phần tử ra khỏi queue và chỉ xử lý nếu queue chứa giá trị. 

🌱Giả sử queue có giá trị là: 1,2

Sau câu lệnh queue.take() thì queue còn giá trị là: 2. Do phần tử đầu tiên đã được đưa ra khỏi queue. 

🌱Giả sử bạn gọi lệnh: queue.take() 3 lần. Thì 2 lần đầu sẽ có dữ liệu trả về. Tới lần thứ 3 do queue rỗng nên dòng code sẽ dừng lại ở hàm queue.take() tới khi dữ liệu mới được thêm vào queue. 

queue.take(); // trả về 1

queue.take(); // trả về 2

queue.take(); // dòng code sẽ dừng đợi ở đây tới khi có 1 item mới được thêm vào queue. 

📌5. Các bài toán sử dụng queue thông thường là bài toán đa luồng, trong đó có nhiều luồng thực hiện việc thêm dữ liệu vào queue, và có 1 luồng thực hiện việc lấy dữ liệu trong queue ra (dequeue) để xử lý. 


final BlockingQueue<Integer> queue = new LinkedBlockingQueue<>();

// Thread 1,2 xử lý thêm dữ liệu vào queue

// Thread 1

new Thread(() -> {

   try {

       for (int i = 0; i < 1000000; i++) {

           queue.put(i);

       }

   } catch (InterruptedException e) {

       e.printStackTrace();

   }

}).start();


// Thread 2

new Thread(() -> {

   try {

       for (int i = 1000000; i < 2000000; i++) {

           queue.put(i);

       }

   } catch (InterruptedException e) {

       e.printStackTrace();

   }

}).start();


// Thread lấy dữ liệu trong queue và xử lý tuần tự:

new Thread(() -> {

   while (true) {

       try {

           int i = queue.take();

           // process item i

           System.out.println(i);

       } catch (InterruptedException e) {

           e.printStackTrace();

       }


   }

}).start();


Ưu điểm của việc dùng 1 luồng xử lý là bạn sẽ tránh việc phải sử dụng kĩ thuật đồng bộ dữ liệu (lock hoặc synchronized) để đảm bảo dữ liệu không bị xung đột. Hệ thống sẽ giảm thiểu rủi ro quá tải trong việc xử lý và đảm bảo sự công bằng khi những yêu cầu đến trước luôn được thực thi trước.

- Tech Zone -

Thư giãn chút nào!!!

Bài viết liên quan