Queue - Khái Niệm Cơ Bản - Sử Dụng Thư Viện Chuẩn STL Cho C/C++

• Học lập trình
• |
• Bài viết
• |
• Tin tức
• |
• Tuyển dụng
• |
• Liên hệ
• |

• Đăng ký
• |
• Đăng nhập

PHP

Laravel

Android

Java

HTML5

CSS3

NodeJS

VueJS

Swift

Python

Machine Learning

C/C++

Linux/Server

SQL

Javascript

Game

Phân tích thiết kế hệ thống

Servlet/JSP

AI

1. Trang chủ
2. C/C++
3. Sử dụng thư viện chuẩn STL cho C/C++
4. Queue - Khái niệm cơ bản

• Bài 1: Vector - Khái niệm
• Bài 2: Các hàm thường dùng trong Vector
• Bài 3: List - Khái niệm cơ bản
• Bài 4: Các hàm thông dụng của List
• Bài 5: Set - Khái niệm
• Bài 6: Các hàm thông dụng và bài tập minh họa về set
• Bài 7: Khái niệm về Stack
• Bài 8: Các hàm cơ bản và bài tập minh họa về STACK
• Bài 9: Queue - Khái niệm cơ bản
• Bài 10: Queue - Bài tập cơ bản
• Bài 11: Map - Khái niệm cơ bản
• Bài 12: Map - Bài tập cơ bản
• Bài 13: Bitset - Khái niệm cơ bản

Bài 9: Queue - Khái niệm cơ bản - Sử dụng thư viện chuẩn STL cho C/C++

Đăng bởi: Admin | Lượt xem: 7204 | Chuyên mục: C/C++ Queue - Hàng đợi là một cấu trúc dữ liệu dùng để lưu giữ các đối tượng theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước”. Khác với ngăn xếp, hàng đợi là mở ở cả hai đầu. Một đầu luôn luôn được sử dụng để chèn dữ liệu vào (hay còn gọi là sắp vào hàng) và đầu kia được sử dụng để xóa dữ liệu (rời hàng). Cấu trúc dữ liệu hàng đợi tuân theo phương pháp First-In-First-Out, tức là dữ liệu được nhập vào đầu tiên sẽ được truy cập đầu tiên.Trong cấu trúc hàng đợi(queue), ta chỉ có thể thêm các phần tử vào một đầu của queue(giả sử là cuối), và cũng chỉ có thể xóa phần tử ở đầu còn lại của queue(tạm gọi là đầu). Như vậy, ở một đầu không thể xảy ra hai hành động thêm và xóa đồng thời.Trong đời sống thực chúng ta có rất nhiều ví dụ về hàng đợi, chẳng hạn như hàng xe ô tô trên đường một chiều (đặc biệt là khi tắc xe), trong đó xe nào vào đầu tiên sẽ thoát ra đầu tiên. Một vài ví dụ khác là xếp hàng học sinh, xếp hàng mua vé, …

I . Các hoạt động cơ bản trên cấu trúc dữ liệu hàng đợi :

hoạt động trên cấu trúc dữ liệu hàng đợi có thể liên quan tới việc khởi tạo hàng đợi, sử dụng dữ liệu trên hàng đợi và sau đó là xóa dữ liệu khỏi bộ nhớ.Để cài đặt được Queue, chúng ta sẽ cần sử dụng các biến như sau:

• queue[]: Một mảng một chiều mô phỏng cho hàng đợi
• arraySize: Số lượng phần tử tối đa có thể lưu trữ trong queue[]
• front: Chỉ số của phần tử ở đang đầu queue. Nó sẽ là chỉ số của phần tử sẽ bị xóa ở lần tiếp theo
• rear: Chỉ số của phần tử tiếp theo sẽ được thêm vào cuối của queue

Danh sách dưới đây là một số hoạt động cơ bản có thể thực hiện trên cấu trúc dữ liệu hàng đợi:

1 . Enqueue – Thêm vào cuối hàng đợi :

Nếu hàng đợi chưa đầy, chúng ta sẽ thêm phần tử cần thêm vào cuối(rear) của hàng đợi. Ngược lại, thông báo lỗi.Các bạn lưu ý, rear là chỉ số của phần tử sẽ được thêm ở lần tiếp theo. Do đó, thêm xong rồi ta mới tăng rear lên 1 đơn vị. Giá trị rear cần thay đổi nên được truyền theo tham chiếu.void Enqueue(int queue[], int element, int& rear, int arraySize) { if(rear == arraySize) // Queue is full printf("OverFlow\n"); else{ queue[rear] = element; // Add the element to the back rear++; } }

2. Dequeue – Xóa khỏi đầu hàng đợi :

Nếu hàng đợi có ít nhất 1 phần tử, chúng ta sẽ tiến hành xóa bỏ phần tử ở đầu của hàng đợi bằng cách tăng front lên 1 giá trị.Ở đây, front đang là chỉ số của phần tử sẽ bị xóa rồi. Cho nên chỉ cần tăng là xong, đó cũng là lý do ta cần truyền tham số front sử dụng tham chiếu.void Dequeue(int queue[], int& front, int rear) { if(front == rear) // Queue is empty printf("UnderFlow\n"); else { queue[front] = 0; // Delete the front element front++; } }Tới đây chắc nhiều bạn thắc mắc tại sao lại tăng front mà không phải là giảm. Các bạn xem giải thích ở hình sau nhé:

3. Front – Lấy giá trị ở đầu hàng đợi :

Hàm này sẽ lấy và trả về giá trị của phần tử đang ở đầu hàng đợiint Front(int queue[], int front) { return queue[front]; }

4. Các hàm hỗ trợ khác :

Hàm lấy kích thước của Hàng đợi, nói cách khác là số lượng phần tử đang có trên hàng đợiint Size(int front, int rear) { return (rear - front); }//Hàm kiểm tra queue rỗng bool IsEmpty(int front, int rear) { return (front == rear); }

II . Hoạt động enqueue trong cấu trúc dữ liệu hàng đợi

Bởi vì cấu trúc dữ liệu hàng đợi duy trì hai con trỏ dữ liệu: front và rear, do đó các hoạt động của loại cấu trúc dữ liệu này là khá phức tạp khi so sánh với cấu trúc dữ liệu ngăn xếp.Dưới đây là các bước để enqueue (chèn) dữ liệu vào trong hàng đợi:

• Kiểm tra xem hàng đợi là có đầy không.
• Nếu hàng đợi là đầy, tiến trình bị lỗi và bị thoát.
• Nếu hàng đợi không đầy, tăng con trỏ rear để trỏ tới vị trí bộ nhớ trống tiếp theo.
• Thêm phần tử dữ liệu vào vị trí con trỏ rear đang trỏ tới trong hàng đợi.
• Trả về success.

Bài tiếp theo: Queue - Bài tập cơ bản >>

Theo dõi VnCoder trên Facebook, để cập nhật những bài viết, tin tức và khoá học mới nhất!

Chia sẻ bài viết

• Bài 1: Vector - Khái niệm
• Bài 2: Các hàm thường dùng trong Vector
• Bài 3: List - Khái niệm cơ bản
• Bài 4: Các hàm thông dụng của List
• Bài 5: Set - Khái niệm
• Bài 6: Các hàm thông dụng và bài tập minh họa về set
• Bài 7: Khái niệm về Stack
• Bài 8: Các hàm cơ bản và bài tập minh họa về STACK
• Bài 9: Queue - Khái niệm cơ bản
• Bài 10: Queue - Bài tập cơ bản
• Bài 11: Map - Khái niệm cơ bản
• Bài 12: Map - Bài tập cơ bản
• Bài 13: Bitset - Khái niệm cơ bản