Hàng đợi (queue) trong C#: cài đặt, ứng dụng, lớp Queue

Hàng đợi ( queue ) là một cấu trúc tài liệu rất quan trọng và phổ cập, là một trong những cấu trúc tài 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ệ quản lý, hay trực tiếp, như xếp hàng ở ẩm thực ăn uống, 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 tài 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 của .NET framework, và ứng dụng của hàng đợi.

Cấu trúc tài 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 Giao hàng 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 tài liệu hàng đợi được tạo ra để mô phỏng loại hoạt động giải trí tựa như .

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 và hai phép toán Enqueue - DequeueHàng đợi và hai phép toán Enqueue – 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 pháp trên hàng đợi

Hàng đợi có những phương pháp 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 setup hoàn toàn có thể gặp 1 số ít phương pháp 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 thông dụng trong mạng lưới hệ thống cũng như trong tăng trưởng ứng dụng. Dưới đây là 1 số ít ứng dụng rất thường gặp. Dĩ nhiên, list những ứ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 nhu yếu CPU, một số ít 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 hạn giải quyết và xử lý của CPU cho những tiến trình. Khi tài liệu được truyền bất đồng bộ giữa những tiến trình, hàng đợi cũng được dùng để đồng nhất hóa dữ liệu này .Khi in ấn, những 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 được 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 để mở màn lệnh in tiếp theo .

Cài đặt hàng đợi trên C #

Tương tự stack, hàng đợi hoàn toàn có thể được thiết lập thuận tiện trên C # sử dụng List hoặc LinkedList để chứa tài liệu. Chúng ta sẽ cùng triển khai 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();
            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
    {
        private readonly List _items;
        public MyQueue() => _items = new List();
        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;
    }
}

Chương trình cài đặt hàng đợi bằng List C#Có thể thấy, việc cài đặt hàng đợi trên C # sử dụng List rất đơn thuần. Nó không độc lạ gì nhiều so với việc setup stack ở bài trước. Trong bản thiết lập này tất cả 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();
            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
    {
        private readonly LinkedList _items;
        public MyQueue() => _items = new LinkedList();
        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 hiệu 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 thuần không kém .Dĩ nhiên, tùy thuộc vào kiểu tài liệu của C # dùng để lưu những thành phần, bản thiết lập của hàng đợi sẽ có ưu điểm yếu kém của kiểu đó .

Lớp Queue của. NET

.NET framework cũng cung cấp sẵn lớp Queue để sử dụng. Lớp Queue 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();

            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 “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à tất cả chúng ta xem xét ở trên hoạt động giải trí dựa trên một giả định rằng toàn bộ những thành phần đều bình đẳng. Nó không phản ảnh được một thực tế : những thành phần chưa chắc đã bình đẳng, tức là chúng hoàn toàn 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ẻ nhỏ, phụ nữ có thai thường thì đường ưu tiên. Bản thân những đối tượng người dùng được ưu tiên đó cũng chia mức độ, ví dụ trẻ nhỏ hoàn toàn có thể được ưu tiên hơn người cao tuổi. Khi đến thao tác với ngân hàng nhà nước, người mua 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 lan rộng ra của hàng đợi ( thường thì ), trong đó mỗi thành phần được gán thêm một chỉ số gọi là độ ( mức ) ưu tiên ( priority ). Độ ưu tiên hoàn toàn có thể là bất kể loại giá trị nào hoàn toàn có thể so sánh được. Ví dụ, độ ưu tiên đơn thuần nhất hoàn toàn có thể chỉ là một số nguyên .

Ví dụ minh họa

Hãy cùng xem một ví dụ đơn thuần về hàng đợi ưu tiên .Giả sử tất cả chúng ta cần xếp hàng cho khách đến thao tác ở ngân hàng nhà nước. Chúng ta giả sử phân loại khách theo 3 Lever ưu tiên ( chỉ là giả sử thôi nhé ! ) : người mua thường, khách bạc, khách vàng. Có thể dùng một số ít nguyên để trình diễn mức ưu tiên này. Chúng ta lựa chọn : người mua thường là Lever 2 ( ít quan trọng nhất ), khách bạc là Lever 1 ( quan trọng hơn ), khách vàng là Lever 0 ( đặc biệt quan trọng quan trọng ) .Hình dưới đây minh họa quy trình đưa khách vào hàng đợi theo mức độ ưu tiên .Ví dụ minh họa hoạt động của hàng đợi ưu tiênVí dụ minh họa hoạt động của hàng đợi ưu tiênNhư vậy hoàn toàn có thể thấy, hàng đợi ưu tiên độc lạ với hàng đợi thường thì là ở quy trình tiến độ đưa thành phần vào hàng đợi ( enqueue ). Mỗi thành phần được được xếp hàng theo ( 1 ) độ ưu tiên và ( 2 ) thứ tự của nó so với những thành phần cùng mức độ ưu tiên. Giai đoạn dequeue không có gì khác : tất cả chúng ta chỉ đơn thuầ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 của .NET.

Có thể thấy, hàng đợi là một cấu trúc tài liệu rất dễ hiểu và quen thuộc trong đời sống. Trong công nghệ thông tin, hàng đợi cũng là cấu trúc tài liệu được sử dụng rất thoáng đãng. Bạn hãy hỏi Google về những ứng dụng của hàng đợi để hiểu thêm về cấu trúc tài liệu này .Chúc bạn học tốt !

+ 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!

5/5 - (1 vote)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments