Queue trong C/C++ là gì? Các thao tác trên Queue trong C/C++ thường dùng

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 tìm hiểu xem cấu trúc này là gì và ứng dụng của nó trong lập trình cũng như trong cuộc sống nhé!

Queue là gì? Các thao tác trên Queue thường dùng

I. 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.

Queue hoạt động theo nguyên tắc FIFO

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.

Ví dụ về hàng đợi

II. Các hàm và thao tác cơ bản của Queue

1. Khai báo thư viện Queue

#include

2. 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.

3. Thao tác Peek()

Thap tác peek

Code minh họa:

kiểu dữ liệu peak()

{

return queue[front];

{

4. Phương thức IsFull()

Phương thức IsFull

Code minh họa:

bool isFull()

{

if (count == max)

return true;

return false;

}

5. Phương thức IsEmpty()

Phương thức IsEmpty

Code minh họa:

bool isEmpty()

{

if (count == max)

return true;

return false;

}

III. Các giải thuật hàng đợi queue

1. Giải thuật Enqueue

Giải thuật Enqueue

Code minh họa:

void enqueue(int data)

{

if(!isFull())

{

rear++;

count ++;

queue[rear] = data;

}

else cout << Queue is full";

}

2. Giải thuật Dequeue

Giải thuật Dequeue

Code minh họa:

void dequeue()

{

if(!isEmpty())

{

count--;

front++;

}

else

cout << "Queue is empty";}

IV. 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.

Ứng dụng của queue trong in ấn

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.

Ứng dụng của queue vào giải thuật Breadth-First search

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!

Nguồn tham khảo: Wikipedia, Lập Trình Không Khó, Viettuts