🌱 Cấu trúc dữ liệu: Queue
Nhiều bạn thắc mắc là học lập trình Nhúng có cần học và sử dụng cấu trúc dữ liệu hay không, thì câu trả lời là Có! Tuy nhiên, việc sử dụng các cấu trúc dữ liệu nâng cao còn phụ thuộc vào yêu cầu của bài toán cũng như cách thiết kế chương trình. Một lí do các khiến các cấu trúc dữ liệu không được sử dụng thường xuyên là do chúng thường gây chiếm nhiều bộ nhớ, trong khi bộ nhớ Vi điều khiển là khá hạn chế.
Trong quá trình học tập, làm việc, mình được tiếp cận với Queue, một cấu trúc dữ liệu khá hữu ích và thường được sử dụng trong các Bài toán ứng dụng Nhúng.
👉 Bài toán
Mình đã từng gặp một ưng dụng như sau:
- Thiết kế chương trình cho node thu thập dữ liệu từ các node cảm biến giao tiếp mạng CAN. Với bài toán này mình sử dụng ngắt ADC để khi các cảm biến chuyển đổi xong, mình sẽ đọc dữ liệu, xử lý và truyền đi qua UART.
- Đối với đề bài này, chúng ta không thể làm tất cả mọi việc (Đọc dữ liệu/Xử lý dữ liệu/Truyền dữ liệu) trong ngắt, bởi vì việc này khiến cho Ngắt chiếm dụng thời gian làm việc của chương trình và các tác vụ khác. Vì vậy, trong ngắt mình sẽ chỉ đọc dữ liệu cảm biến và lưu nó vào "đâu đó". Sau đó, dữ liệu này sẽ được xử lý trên tầng App, có thể là hàm main.
👉 Queue là gì? Ứng dụng của Queue?
Queue - Hàng đợi là một cấu trúc dữ liệu tuyến tính - Linear Data Structure, để lưu trữ và thao tác với dữ liệu. Nó hoạt động theo cơ chế FIFO - First In First Out, tức là dữ liệu được đẩy vào Queue trước sẽ được lấy ra trước.
Ví dụ, đối với bài toán ở trên thì dữ liệu đọc được từ ADC sẽ được đẩy vào 1 Queue, và dữ liệu này sẽ được xử lý trước.
⇒ Có thể nói Queue là một cơ chế 2 đầu mở, giống như 1 đường ống, 1 đầu dùng để đưa dữ liệu vào, đầu còn lại để lấy dữ liệu ra 😂😂
💬 Một số ứng dụng của Queue:
- CPU Scheduling: Đối với hoạt động lập lịch của OS, khi có nhiều hoạt động muốn thực hiện cùng lúc, OS sẽ rất khó trong việc lập lịch hoạt động cho các task. Vì vậy, để quản lý hiệu quả các Task, Event, người ta sử dụng một Queue để lưu trữ các Task muốn thực thi theo thứ tự xảy ra và thứ tự ưu tiên nếu có.
- Breadth-First Search Algorith (BFS) - Cái này mình chưa dùng bao giờ 😆
- Lưu trữ dữ liệu và giao tiếp dữ liệu giữa các tầng, giống như ứng dụng ở trên của mình.
👉 Các khái niệm và hoạt động của Queue
Queue cung cấp cho người dùng một số khái niệm và Operations như sau (Đây là khái niệm chung mà các bạn có thể tìm thấy trên mạng và các thư viện viết sẵn, thực chất khi tự triển khai Queue chúng ta có thể tự định nghĩa lại tên):
- Front / Rear: Là đại diện cho con trỏ trỏ đến phần tử đầu và cuối của Queue. Để khởi tạo 1 Queue, chúng ta đặt Front = Rear = -1.
- push / pop: Là 2 hành động quan trọng nhất của Queue.
- Push - Enqueue sẽ đẩy 1 phần tử mới vào Queue và tăng dung lượng của queue cũng như Rear lên 1. Trước khi push, cần đảm bảo Queue đang không đầy, bằng hàm isFull().
- Pop - Dequeue sẽ lấy 1 phần tử ra khởi Queue, và giảm dung lượng của Queue. Trước khi pop cần đảm bảo Queue đang không trống bằng hàm isEmpty().
- isEmpty(): Là một hàm mình có thể tự viết, dùng để kiểm tra xem Queue có đang trống hay không (trước khi pop một phần tử ra từ Queue).
- isFull(): Là một hàm mình có thể tự viết, dùng để kiểm tra xem Queue có đang đầy hay không (trước khi push một phần tử ra từ Queue).
👉 Triển khai Queue trong C
Dưới đây là cách triển khai Queue của riêng mình, các bạn có thể tham khảo thêm trên mạng, hoặc tự triển khai nhé!
Về cơ bản thì người ta thường sử dụng mảng để đại diện cho Queue, có thể là mảng tĩnh với việc khai báo trước một mảng trên RAM, hoặc dùng malloc để người dùng tự khởi tạo kích thước của Queue. Tuy nhiên, do bộ nhớ Vi điều khiển thường có hạn, mình sẽ triển khai trên mảng tĩnh trước.
💬 Tạo một Struct type cho Queue:
Struct này sẽ chứa các thông số:
- Front / Rear / Capacity ban đầu,
- Size của Queue,
- Mảng đại diện chứa các phần tử của Queue.
💬 Triển khai hàm isFull(), isEmpty()
isEmpty():
isFull():
💬 Triển khai hàm PushData(), PeekData(), Pop()
PushData() - Hàm này dùng để push data mới vào Queue, tăng Rear và Capacity lên 1.
PeekData() - Hàm này dùng để lấy data từ Front của queue, tăng Front lên 1, tuy nhiên, chưa thực hiện việc pop. Chỗ này để tiết kiệm thời gian khi muốn pop nhiều data cùng lúc, các bạn có thể tùy ý triển khai 1 hàm pop chung thôi cũng được.
Pop() - Hàm này dùng để pop data khỏi queue sau khi peek. Mình dùng nó để đẩy Front về vị trị 0 của mảng, và các phần tử của Queue về phía đầu mảng để dễ quản lý hơn.
👉 Chi tiết full source code và video hướng dẫn xây dựng, sử dụng các API, các bạn có thể tham khảo tại video Bài học về Queue.
>>>= Follow ngay =<<<