Tiếp tục series về thuật toán chuyên sâu, chúng ta cùng nhau tìm hiểu về một loại cấu trúc dữ liệu rất phổ biến, đó là Hàng đợi (Queue).
Hàng đợi – Queue là kiểu cấu trúc dữ liệu tuyến tính, việc truy xuất dữ liệu của nó theo nguyên tắc FIFO, tức là dữ liệu vào trước thì lấy trước, vào sau lấy sau.
Với Queue, phần tử đầu tiên được đưa vào Queue cũng sẽ là phần tử đầu tiên được xóa nếu có yêu cầu. Tức là, nó không cho phép bạn truy xuất trực tiếp dữ liệu nằm ở giữa queue.
Nội dung chính của bài viết
Lý thuyết Queue
Queue – hàng đợi nó mô phỏng lại văn hóa xếp hàng của con người chúng ta thôi. Khi chúng ta đến một tiệm cắt tóc, hôm nay khá là đông khách nên mọi người phải xếp hàng. Ai đến trước thì được cắt trước, cứ lần lượt từng người một. Ai mà bon chen đến sau mà đòi cắt trước thì chỉ có cắt… cái đầu gối thôi 😊
Nguyên lý hoạt động của Queue là FIFO (First In, First Out), tức là vào trước ra trước.
Về cơ bản, cấu trúc dữ liệu kiểu Queue cung cấp một số thao tác để làm bạn như sau:
- enqueue: Thêm phần tử vào queue, tất nhiên phần tử này sẽ vào cuối của queue
- dequeue: Xóa phần tử đầu trong queue. Nếu queue rỗng thì thông báo lỗi.
- isEmpty: Kiểm tra xem queue có rỗng không?
- isFull: Kiểm tra queue đã đầy hay chưa?
- peek: Lấy giá trị của phần tử đầu trong queue, chỉ lấy giá trị ra chứ kg có xóa phần tử, queue không thay đổi.
Khi nào sử dụng Queue?
Sau khi hiểu được định nghĩa cũng như nguyên lý hoạt động của Queue rồi, chúng ta sẽ đặt ngay câu hỏi, vậy Queue được ứng dụng trong những bài toán nào? Khi nào thì sử dụng Queue mà không phải Stack?
Để trả lời cho câu hỏi này một cách chính xác 100% thì thật là khó? Việc vận dụng một công cụ trong các bài toán thực tế là vô cùng đa dạng. Với những đúc kết kinh nghiệm thực tiễn và qua nghiên cứu, mình thấy Queue thường sử dụng trong các trường hợp sau:
- Sử dụng queue để lưu trữ tạm các dữ liệu, thực hiện tính toán các biểu thức toán học.
- Ứng dụng trong các bài toán về in ấn.
- Quản lý các request trên một tài nguyên được chia sẻ, ví dụ như lập lịch CPU (CPU scheduling)
- Routers và switches trong mạng networking
- Quản lý các bài hát (media playlist) trong các chương trình đa phương tiện (Media players)
- Và còn rất nhiều ứng dụng khác nữa.v.v… (các bạn bổ sung thêm ở phần bình luận nhé)
💦 Đọc thêm về các thuật toán:
- Thuật toán tìm kiếm nhị phân – Binary Search Tree (BTS)
- Thuật toán đảo ngược chuỗi liên kết (Linked List)
- Bài toán tháp Hà Nội – Thuật toán và cách giải
Thực hành Implement một queue bằng C++
Ở phần này, chúng ta sẽ cùng nhau cài đặt các chức năng chính của một queue (như đã đề cập ở phần trên). Có nhiều cách để bạn tạo queue, nhưng sau khi tham khảo rất nhiều ví dụ, mình nghĩ sử dụng mảng để tạo queue là cách đơn giản nhất.
Để đỡ dài dòng lan man, mình sẽ comment thẳng vào trong code để giải thích nhé.
1. Cài đặt Queue
#include <iostream>
#include <cstdlib>
using namespace std;
// Define the default capacity of a queue
#define SIZE 1000
// A class to store a queue
class Queue
{
int *arr; // array to store queue elements
int capacity; // maximum capacity of the queue
int front; // front points to the front element in the queue (if any)
int rear; // rear points to the last element in the queue
int count; // current size of the queue
public:
Queue(int size = SIZE); // constructor
~Queue(); // destructor
int dequeue();
void enqueue(int x);
int peek();
int size();
bool isEmpty();
bool isFull();
};
// Constructor to initialize a queue
Queue::Queue(int size)
{
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}
// Destructor to free memory allocated to the queue
Queue::~Queue() {
delete[] arr;
}
2. Kiểm tra kích thước queue
// Utility function to return the size of the queue
int Queue::size() {
return count;
}
3. isEmpty – Kiểm tra queue có rỗng không?
// Utility function to check if the queue is empty or not
bool Queue::isEmpty() {
return (size() == 0);
}
4. isFull – Kiểm tra xem queue đã đầy hay chưa?
// Utility function to check if the queue is full or not
bool Queue::isFull() {
return (size() == capacity);
}
5. enqueue – Thêm mới phần tử
// Utility function to add an item to the queue
void Queue::enqueue(int item)
{
// check for queue overflow
if (isFull())
{
cout << "Overflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}
cout << "Inserting " << item << endl;
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}
6. dequeue – Xóa phần tử
// Utility function to dequeue the front element
int Queue::dequeue()
{
// check for queue underflow
if (isEmpty())
{
cout << "Underflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}
int x = arr[front];
cout << "Removing " << x << endl;
front = (front + 1) % capacity;
count--;
return x;
}
7. peek– lấy giá trị của phần tử đầu tiên trong queue
int Queue::peek()
{
if (isEmpty())
{
cout << "Underflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}
return arr[front];
}
8. Sử dụng queue
int main()
{
// create a queue of capacity 5
Queue q(5);
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
cout << "The front element is " << q.peek() << endl;
q.dequeue();
q.enqueue(4);
cout << "The queue size is " << q.size() << endl;
q.dequeue();
q.dequeue();
q.dequeue();
if (q.isEmpty()) {
cout << "The queue is empty\n";
}
else {
cout << "The queue is not empty\n";
}
return 0;
}
Toàn bộ code minh họa trong bài viết được để tại đây:
Trên đây là những giaỉ thích lý thuyết và cách để bạn cài đặt một queue. Mình hi vọng, nó sẽ ích cho bạn trong các bài tập thực tế sau này.
Nhận sách Java Advanced Features
Java là ngôn ngữ lập trình phổ biến nhất thế giới, là hình mẫu của tư tưởng OOP. Nếu bạn muốn bắt đầu với Java thì đây là cuốn sách không thể bỏ qua. Với 63 ví dụ thực hành, cùng với cách viết ngắn gọn dễ hiểu sẽ giúp bạn hiểu rõ bản chất của Java.
Hiện Amazon đang bán với giá 16$, nhưng với VNTALKING thì miễn phí cho bạn. Còn chờ gì nữa?
Bình luận. Cùng nhau thảo luận nhé!