Queue hay còn gọi là hàng đợi là một cấu trúc giải thuật thường gặp trong lập trình. Cùng VHĐS tìm hiểu xem cấu trúc Queue trong C++ là gì và ứng dụng của nó trong lập trình cũng như trong cuộc sống nhé!
Cấu trúc dữ liệu hàng đợi (Queue) là gì?
Queue (hàng đợi) là một vật chứa các đối tượng làm việc. Queue luôn mở ở cả hai đầu. Một đầu dùng để thêm một đối tượng vào hàng, đầu kia dùng để lấy một đối tượng ra khỏi hàng.
Việc thêm hoặc bớt đối tượng tuân thủ theo nguyên tắc FIFO (First In First Out – vào trước xếp trước), nghĩa là đối tượng nào được thêm vào đầu tiên sẽ được truy xuất đầu tiên.
Trong thực tế, hàng đợi không hề xa lạ mà luôn hiện diện xung quanh chúng ta. Ví dụ phổ biến nhất về hàng đợi là xếp hàng cho các mục đích khác nhau (xếp hàng qua cổng soát vé, xếp hàng mua vé xem phim,….), trong đó đối tượng nào xếp hàng trước sẽ được phục vụ trước và thoát ra khỏi hàng trước.
Các hàm và thao tác cơ bản của Queue
Khai báo thư viện Queue
#include <queue>
Khai báo biến
- queue[…]: hàng đợi, là mảng một chiều chứa các biến đợi.
- rear: chỉ số phần tử ở cuối hàng đợi queue. Khởi tạo rear = -1.
- front: chỉ số phần tử ở đầu hàng đợi queue. Khởi tạo front = 0.
- count: đếm số lượng phần tử trong hàng đợi queue. Khởi tạo count = 0.
Thao tác Peek()
Peek() là thao tác giúp lấy phần tử ở đầu hàng mà không xóa phần tử ấy đi.
Code minh họa:
kiểu dữ liệu peak()
{
return queue[front];
{
Phương thức IsFull()
IsFull giúp kiểm tra hàng đợi đã đầy hay chưa?
Code minh họa:
bool isFull()
{
if (count == max)
return true;
return false;
}
Phương thức IsEmpty()
IsFull giúp kiểm tra hàng đợi có trống hay không?
Code minh họa:
bool isEmpty()
{
if (count == max)
return true;
return false;
}
Các giải thuật hàng đợi queue
Giải thuật Enqueue
Enqueue() là thao tác thêm phần tử vào cuối hàng đợi.
Quy trình:
- Bước 1: Kiểm tra queue có đầy hay không.
- Bước 2: Nếu queue đầy, thoát khỏi queue.
- Bước 3: Nếu queue chưa đầy, tăng rear tới vị trí trống tiếp theo (rear + 1).
- Bước 4: Gán dữ liệu vào vị trí rear trong hàng đợi.
Code minh họa:
void enqueue(int data)
{
if(!isFull())
{
rear++;
count ++;
queue[rear] = data;
}
else cout << Queue is full”;
}
Giải thuật Dequeue
Dequeue() Xóa phần tử ra khỏi hàng đợi
Quy trình:
- Bước 1: Kiểm tra queue có trống hay không?
- Bước 2: Nếu queue trống, thoát khỏi queue.
- Bước 3: Nếu queue không trống, tăng front tới vị trí chứa đối tượng tiếp theo (front + 1).
Code minh họa:
void dequeue()
{
if(!isEmpty())
{
count–;
front++;
}
else
cout << “Queue is empty”;}
Một số ứng dụng của hàng đợi Queue
Trong in ấn, các tài nguyên khi in ấn sẽ được lưu trữ trong một bộ nhớ đệm sau đó được đẩy ra bộ đệm riêng của máy in. Cơ chế này cho phép đặt nhiều lệnh in vào hàng đợi. Nhờ cơ chế này mà người dùng không phải chờ kết thúc từng lệnh để bắt đầu lệnh tiếp theo.
Giải thuật tìm kiếm theo chiều rộng (Breadth-First search) là thuật toán xét duyệt, tìm kiếm trên cây hoặc đồ thị theo chiều rộng. Giải thuật này sử dụng hàng đợi queue để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào.
Xem thêm:
- Queue trong C/C++ là gì? Các thao tác trên Queue trong C/C++ thường dùng
- Câu điều kiện if else là gì? Cấu trúc câu lệnh if else trong C/C++
- Mảng 1 chiều trong C/C++ | Cách khai báo mảng trong C/C++
Trên đây là toàn bộ kiến thức cơ bản về Queue trong C/C++ và các thao tác cơ bản thường dùng. Hi vọng bạn đã có những kiến thức cơ bản về Queue và có thể thực hành về Queue qua một vài ví dụ cụ thể. Cảm ơn các bạn đã theo dõi bài viết này!
