Hàng đợi (queue) là một cấu trúc dữ liệu rất quan trọng và phổ biến, là một trong những cấu trúc dữ liệu nền tảng của công nghệ thông tin. Thực tế là hàng ngày bạn đều tiếp xúc với nó, dù là gián tiếp, như in ấn, sử dụng hệ điều hành, hay trực tiếp, như xếp hàng ở siêu thị, bệnh viện.
Tuy vậy không nhiều người học lập trình ý thức được vai trò của cấu trúc dữ liệu này cũng như ứng dụng của nó.
Bài học này sẽ giúp bạn nắm được vai trò của hàng đợi, cách cài đặt nó bằng C#, cách sử dụng lớp Queue<T> của .NET framework, và ứng dụng của hàng đợi.
Cấu trúc dữ liệu hàng đợi (Queue)
Hãy tưởng tượng bạn đi rút tiền ở cây ATM. Nếu lúc bạn đến không có ai thì may rồi! Nhưng nếu đã có ai đó đang rút tiền, bạn phải chờ người ta xong mới đến lượt. Nếu trước bạn còn có vài người nữa, bạn đương nhiên phải đứng vào cuối hàng mà chờ đến lượt. Nếu có nhiều hơn một cây nhưng lượng người cần phục vụ vượt quá số lượng cây thì bạn cũng vẫn phải chờ như vậy.
Cấu trúc dữ liệu hàng đợi được tạo ra để mô phỏng loại hoạt động tương tự.
Khái niệm
Hàng đợi là một loại cấu trúc dữ liệu dạng tập hợp (collection) thuộc loại truy xuất giới hạn (tương tự stack) và có các đặc điểm: (1) phần tử được lấy ra để xử lý luôn là phần tử ở đầu hàng (front); (2) phần tử mới luôn được đặt vào cuối hàng (rear); (3) không thể tự tiện lấy phần tử ở giữa hàng.
Thao tác đặt phần tử vào cuối hàng gọi là enqueue; Thao tác lấy phần tử từ đầu hàng gọi là dequeue.
Hàng đợi tuân thủ nguyên tắc vào trước – ra trước, thường gọi tắt là FIFO (First-in, First-out): Ai (phần tử, dữ liệu) đến trước sẽ được xử lý trước, ai đến sau đứng vào cuối hàng để đợi đến lượt. Đôi khi nguyên tắc này cũng được mô tả là LILO (Last-in, Last-out) – vào sau ra sau.
Hàng đợi cũng là một cấu trúc dữ liệu đệ quy (recursive structure). Có nghĩa là một hàng đợi, nếu nó không rỗng, có thể xem nó bao gồm phần tử đầu hàng và một hàng đợi con chứa tất cả các phần tử còn lại. Mỗi hàng đợi con lại có thể tiếp tục được biểu diễn như vậy. Do đó, hàng đợi cũng thường được sử dụng cùng kỹ thuật đệ quy.
Các phương thức trên hàng đợi
Hàng đợi có các phương thức chính sau đây:
- Enqueue – thêm phần tử vào cuối hàng (đôi khi chúng ta sẽ dùng từ rear cho gọn)
- Dequeue – bỏ phần tử ra khỏi đầu hàng (front)
- Peek – đọc giá trị của phần tử front nhưng không bỏ nó ra khỏi hàng.
Tùy thuộc từng cài đặt có thể gặp một số phương thức khác:
- Clear – xóa hết các phần tử
- Contains – kiểm tra xem hàng đợi có chứa một giá trị nào đó không
- Count – đếm số phần tử đang có
Enqueue, Dequeue, Peek đều có độ phức tạp hằng số O(1).
Một số ứng dụng của hàng đợi
Hàng đợi được sử dụng rất phổ biến trong hệ thống cũng như trong phát triển ứng dụng. Dưới đây là một số ứng dụng rất thường gặp. Dĩ nhiên, danh sách các ứng dụng của hàng đợi rất rất dài, kể không hết.
Hàng đợi được sử dụng khi lập lịch CPU. Khi có nhiều tiến trình cùng yêu cầu CPU, một số thuật toán lập lịch phức tạp được sử dụng cùng với hàng đợi để phân phối thời gian xử lý của CPU cho các tiến trình. Khi dữ liệu được truyền bất đồng bộ giữa các tiến trình, hàng đợi cũng được dùng để đồng bộ hóa dữ liệu này.
Khi in ấn, các tài liệu cần in được tải vào một bộ nhớ đệm. Sau đó lần lượt đẩy ra bộ đệm riêng của máy in. Cơ chế này được gọi là spooling. Spooling cho phép đặt nhiều lệnh in vào một hàng đợi, giúp người dùng không phải chờ kết thúc từng lệnh để bắt đầu lệnh in tiếp theo.
Cài đặt hàng đợi trên C#
Tương tự stack, hàng đợi có thể được cài đặt dễ dàng trên C# sử dụng List hoặc LinkedList để chứa dữ liệu. Chúng ta sẽ cùng thực hiện cả hai cách này để hiểu rõ hơn về hàng đợi.
Cài đặt queue bằng List
using System;
using System.Collections.Generic;
namespace P01_CustomQueue
{
class Program
{
static void Main(string[] args)
{
Console.Title = "Custom Queue";
var queue = new MyQueue<string>();
queue.Enqueue("Hello");
queue.Enqueue("world");
queue.Enqueue("from");
queue.Enqueue("my");
queue.Enqueue("super");
queue.Enqueue("queue");
queue.Enqueue("class");
while (queue.Count > 0)
{
Console.Write($"{queue.Dequeue()} ");
}
Console.ReadKey();
}
}
class MyQueue<T>
{
private readonly List<T> _items;
public MyQueue() => _items = new List<T>();
public void Enqueue(T item) => _items.Add(item);
public T Dequeue()
{
var temp = _items[0];
_items.Remove(temp);
return temp;
}
public T Peek() => _items[0];
public void Clear() => _items.Clear();
public int Count => _items.Count;
}
}
Có thể thấy, việc cài đặt hàng đợi trên C# sử dụng List rất đơn giản. Nó không khác biệt gì nhiều so với việc cài đặt stack ở bài trước. Trong bản cài đặt này chúng ta cũng sử dụng kỹ thuật lập trình generic.
Các phương thức của class MyQueue được viết theo kiểu expression body cho gọn vì chúng đều chỉ chứa 1 lệnh duy nhất.
Cài đặt queue bằng LinkedList
using System;
using System.Collections.Generic;
namespace P02_CustomQueue
{
class Program
{
static void Main(string[] args)
{
Console.Title = "Custom Queue with LinkedList";
var queue = new MyQueue<string>();
queue.Enqueue("Hello");
queue.Enqueue("world");
queue.Enqueue("from");
queue.Enqueue("my");
queue.Enqueue("super");
queue.Enqueue("queue");
queue.Enqueue("class");
while (queue.Count > 0)
{
Console.Write($"Before: {queue.Count} items, ");
Console.Write($"Dequeued item: {queue.Dequeue()}, ");
Console.WriteLine($"After: {queue.Count} items");
}
Console.ReadKey();
}
}
class MyQueue<T>
{
private readonly LinkedList<T> _items;
public MyQueue() => _items = new LinkedList<T>();
public void Enqueue(T item) => _items.AddLast(item);
public T Dequeue()
{
var temp = _items.First.Value;
_items.RemoveFirst();
return temp;
}
public T Peek() => _items.First.Value;
public void Clear() => _items.Clear();
public int Count => _items.Count;
}
}Dịch và chạy chương trình sẽ thu được cùng kết quả như ở mục trên.
Có thể thấy việc cài đặt hàng đợi trên C# sử dụng LinkedList cũng đơn giản không kém.
Dĩ nhiên, tùy thuộc vào kiểu dữ liệu của C# dùng để lưu các phần tử, bản cài đặt của hàng đợi sẽ có ưu nhược điểm của kiểu đó.
Lớp Queue của .NET
.NET framework cũng cung cấp sẵn lớp Queue<T> để sử dụng. Lớp Queue<T> nằm trong không gian tên System.Collections.Generic.
using System;
using System.Collections.Generic;
namespace P03_Queue
{
class Program
{
static void Main(string[] args)
{
Console.Title = "Standard .NET Queue";
var queue = new Queue<string>();
queue.Enqueue("Hello");
queue.Enqueue("world");
queue.Enqueue("from");
queue.Enqueue("my");
queue.Enqueue("super");
queue.Enqueue("queue");
queue.Enqueue("class");
while (queue.Count > 0)
{
Console.Write($"Before: {queue.Count} items, ");
Console.Write($"Dequeued item: {queue.Dequeue()}, ");
Console.WriteLine($"After: {queue.Count} items");
}
Console.ReadKey();
}
}
}Có thể thấy, việc dùng lớp Queue<T> “xịn” của .NET không có gì khác biệt với các lớp chúng ta tự xây dựng.
Hàng đợi ưu tiên (Priority Queue)
Khái niệm
Loại hàng đợi mà chúng ta xem xét ở trên hoạt động dựa trên một giả định rằng tất cả các phần tử đều bình đẳng. Nó không phản ảnh được một thực tế: các phần tử chưa chắc đã bình đẳng, tức là chúng có thể có độ ưu tiên khác nhau.
Ngoài đời cũng đúng như vậy. Ví dụ, khi xếp hàng khám bệnh, người cao tuổi, trẻ em, phụ nữ có thai thông thường đường ưu tiên. Bản thân các đối tượng được ưu tiên đó cũng chia mức độ, ví dụ trẻ em có thể được ưu tiên hơn người cao tuổi. Khi đến làm việc với ngân hàng, khách hàng VIP luôn được ưu tiên hơn.
Một biến thể của hàng đợi được xây dựng để mô phòng thực tế trên: hàng đợi ưu tiên (priority queue). Loại hàng đợi này có tầm quan trọng rất lớn.
Hàng đợi ưu tiên là dạng mở rộng của hàng đợi (thông thường), trong đó mỗi phần tử được gán thêm một chỉ số gọi là độ (mức) ưu tiên (priority). Độ ưu tiên có thể là bất kỳ loại giá trị nào có thể so sánh được. Ví dụ, độ ưu tiên đơn giản nhất có thể chỉ là một số nguyên.
Ví dụ minh họa
Hãy cùng xem một ví dụ đơn giản về hàng đợi ưu tiên.
Giả sử chúng ta cần xếp hàng cho khách đến làm việc ở ngân hàng. Chúng ta giả sử phân chia khách theo 3 cấp độ ưu tiên (chỉ là giả sử thôi nhé!): khách hàng thường, khách bạc, khách vàng. Có thể dùng một số nguyên để biểu diễn mức ưu tiên này. Chúng ta lựa chọn: khách hàng thường là cấp độ 2 (ít quan trọng nhất), khách bạc là cấp độ 1 (quan trọng hơn), khách vàng là cấp độ 0 (đặc biệt quan trọng).
Hình dưới đây minh họa quá trình đưa khách vào hàng đợi theo mức độ ưu tiên.
Như vậy có thể thấy, hàng đợi ưu tiên khác biệt với hàng đợi thông thường là ở giai đoạn đưa phần tử vào hàng đợi (enqueue). Mỗi phần tử được được xếp hàng theo (1) độ ưu tiên và (2) thứ tự của nó so với các phần tử cùng mức độ ưu tiên. Giai đoạn dequeue không có gì khác: chúng ta chỉ đơn giản là lấy từng phần từ từ đầu hàng ra.
Kết luận
Trong bài học này chúng ta đã tìm hiểu cấu trúc dữ liệu hàng đợi, cách cài đặt trên C#, cách sử dụng lớp Queue<T> của .NET.
Có thể thấy, hàng đợi là một cấu trúc dữ liệu rất dễ hiểu và quen thuộc trong cuộc sống. Trong công nghệ thông tin, hàng đợi cũng là cấu trúc dữ liệu được sử dụng rất rộng rãi. Bạn hãy hỏi Google về các ứng dụng của hàng đợi để hiểu thêm về cấu trúc dữ liệu này.
Chúc bạn học tốt!
[wpdm_package id=’10387′]
+ Nếu bạn thấy site hữu ích, trước khi rời đi hãy giúp đỡ site bằng một hành động nhỏ để site có thể phát triển và phục vụ bạn tốt hơn.
+ Nếu bạn thấy bài viết hữu ích, hãy giúp chia sẻ tới mọi người.
+ Nếu có thắc mắc hoặc cần trao đổi thêm, mời bạn viết trong phần thảo luận cuối trang.
Cảm ơn bạn!
