Hàng đợi – Queue trong C++
Trong những bài trước, ta đã tìm hiểu về Stack, trong lập trình C++, còn có một loại cấu trúc dữ liệu trái ngược với Stack đó là Queue – Hàng đợi. Trong bài viết này, chúng ta sẽ cùng tìm hiểu sâu hơn về Queue trong C++, từ cách khởi tạo, sử dụng đến những ứng dụng thực tế của nó trong lập trình C++.
Queue C++ là gì?
Hàng đợi – Queue là một cấu trúc dữ liệu đặc biệt trong C++ được quản lý theo nguyên tắc First In First Out (FIFO), tức là phần tử được thêm vào trước sẽ được lấy ra trước. Cấu trúc này rất hữu ích trong nhiều bài toán liên quan đến quản lý luồng dữ liệu, xử lý các yêu cầu theo thứ tự hoặc trong các hệ thống hàng đợi.
Với sự hỗ trợ mạnh mẽ từ một thư viện chứa những template C++ (STL – Standard Template Library), Queue trở thành một công cụ hữu ích và linh hoạt, giúp lập trình viên dễ dàng xây dựng các giải pháp hiệu quả và tối ưu.
>> Đọc thêm: Ngăn xếp stack trong C++
Các phương thức của Queue trong C++
Trong C++, queue là một lớp cung cấp nhiều phương thức khác nhau để thực hiện các thao tác với hàng đợi. Dưới đây là các phương thức chính:
Phương thức | Mô tả |
---|---|
EnQueue() |
Thêm một phần tử vào cuối hàng đợi |
DeQueue() |
Lấy phần tử đầu tiên ra khỏi hàng đợi (nếu hàng đợi không rỗng). |
front() |
Trả về phần tử đầu tiên trong hàng đợi. |
back() |
Trả về phần tử cuối cùng trong hàng đợi. |
size() |
Trả về số lượng phần tử trong hàng đợi. |
empty() |
Trả về true nếu hàng đợi rỗng, ngược lại trả về false . |
swap() |
Hoán đổi nội dung của hai hàng đợi, miễn là chúng cùng kiểu dữ liệu. |
Cách hàng đợi Queue hoạt động
Trong C++, queue
là một container adapter được xây dựng dựa trên các container khác như deque
hoặc list
. Điều này có nghĩa là queue
sử dụng một đối tượng của các container này làm nền tảng, và cung cấp một tập hợp các hàm thành viên (member functions) để truy cập và quản lý các phần tử.
Queue trong C++ cho phép cấu hình thông qua các tham số mẫu sau:
- Container: Tham số này xác định đối tượng bên trong (internal object) của container nơi tất cả các phần tử của hàng đợi được lưu trữ. Ví dụ, queue thường được cài đặt dựa trên
std::deque
hoặcstd::list
, vì các container này hỗ trợ truy cập đầu và cuối một cách hiệu quả. - T: Tham số này xác định kiểu dữ liệu của các phần tử sẽ được giữ bởi container adapter. Ví dụ, nếu bạn muốn tạo một queue của số nguyên,
T
sẽ làint
.
>> Xem thêm: Phân biệt ngăn xếp và hàng đợi (Stack vs Queue) trong C++
Cài đặt hàng đợi
Bây giờ chúng ta hãy cùng xem cách cài đặt hàng đợi trong C++.
Cấu trúc một phần tử
Hàng đợi cũng dựa trên danh sách liên kết đơn, do đó một phần tử trong hàng đợi có cấu trúc không khác gì một phần tử trong danh sách liên kết đơn.
struct Node
{
int data;
Node *next;
};
Cấp phát động, khởi gán giá trị một node và trả về địa chỉ của node đó tương tự như stack hay linked list:
Node* CreateNode(int init)
{
Node *node = new Node;
node->data = init;
node->next = NULL;
return node;
}
Cấu trúc một hàng đợi
Không giống như ngăn xếp, hàng đợi yêu cầu ta phải quản lý được cả phần tử đầu và cuối, do chúng ta thêm vào hàng đợi là thêm vào cuối và lấy một phần tử là lấy từ đầu hàng đợi. Vậy chúng ta sẽ có cấu trúc Queue như sau:
struct Queue
{
Node *head;
Node *tail;
};
Tương tự, hàng đợi rỗng khi được khởi tạo, ta sẽ gán head và tail bằng NULL:
void CreateQueue(Queue &q)
{
q.head = NULL;
q.tail = NULL;
}
Kiểm tra hàng đợi rỗng
Tương tự như stack, hàng đợi rỗng khi phần tử đầu hàng đợi bằng NULL, chúng ta sẽ kiểm tra như sau
int IsEmpty(Queue q)
{
if (q.head == NULL)
return 1;
return 0;
}
Thêm phần tử vào cuối hàng đợi – Enqueue trong C++
Thêm phần tử vào cuối hàng đợi (EnQueue) thực hiện cũng tương tự như khi ta thêm phần tử vào cuối danh sách liên kết đơn, tức là thêm vào tail. Chúng ta thực hiện như sau:
void EnQueue(Queue &q, Node *node)
{
if (IsEmpty(q))
{
q.head = node;
q.tail = node;
}
else
{
q.tail->next = node;
q.tail = node;
}
}
Lấy phần tử đầu ra khỏi hàng đợi – Dequeue trong C++
Để lấy phần tử đầu ra khỏi hàng đợi (DeQueue), chúng ta sẽ lưu trữ giá trị phần tử đầu hàng đợi, sau đó xóa nó đi như xóa phần tử đầu của danh sách liên kết đơn, tất nhiên là với điều kiện hàng đợi không rỗng. Sau khi lấy phần tử đầu tiên ra, nếu như đó là phần tử duy nhất của hàng đợi thì chúng ta sẽ gán lại tail bằng NULL luôn. Chúng ta sẽ có đoạn code như sau:
int DeQueue(Queue &q)
{
if (IsEmpty(q))
return 0;
Node *node = q.head;
int data = node->data;
q.head = node->next;
delete node;
if (q.head == NULL)
q.tail = NULL;
return data;
}
Lấy giá trị phần tử đầu hàng đợi
Lấy giá trị phần tử đầu hàng đợi cũng tương tự như lấy phần tử đầu ra khỏi hàng đợi, nhưng không xóa phần tử đầu đi. Chúng ta thực hiện như sau:
int Front(Queue q)
{
if (IsEmpty(q))
return 0;
return q.head->data;
}
Tham khảo việc làm C++ Developer hấp dẫn tại TopDev
Độ phức tạp thời gian
Các thao tác trên queue
đều có độ phức tạp thời gian O(1), tức là chúng hoạt động với thời gian hằng số bất kể kích thước của hàng đợi. Điều này làm cho queue
trở thành một cấu trúc dữ liệu rất hiệu quả trong nhiều tình huống xử lý dữ liệu.
- B BenQ RD Series – Dòng Màn Hình Lập Trình 4k+ Đầu Tiên Trên Thế Giới
- F Framework nào tốt nhất cho dự án của bạn? – Checklist chi tiết
- K Kinh nghiệm xử lý responsive table hiệu quả
- S Stackoverflow là gì? Bí kíp tận dụng Stack Overflow hiệu quả
- 7 7 kinh nghiệm hữu ích khi làm việc với GIT trong dự án
- B Bài tập Python từ cơ bản đến nâng cao (có lời giải)
- B Bảo mật API là gì? Một số nguyên tắc và kỹ thuật cần biết
- H Hướng dẫn cài đặt và tự học lập trình Python cơ bản từ A-Z
- C Chinh Phục Phân Tích Dữ Liệu Với Pandas Trong Python: Hướng Dẫn Từng Bước
- D Display CSS là gì? Cách khai báo và sử dụng thuộc tính display trong CSS