🌱 Cấu trúc dữ liệu: Queue - Circular Queue
Ở bài trước mình đã giới thiệu với các bạn về Cấu trúc dữ liệu Queue, các định nghĩa cơ bản và các triển khai một Queue đơn giản bằng ngôn ngữ lập trình C. Một Queue như ở bài trước, chúng ta có thể push data vào rear, hoặc pop data từ front của queue.
Khai triển Queue như bài trước gọi là một Regular Queue, hoặc Linear Queue. Đối với cách triển khai này có một số vấn đề: Không thể thêm elements vì Size cố định, đặc biệt là khi Rear tăng đến giá trị lớn nhất.
Ở bài trước mình có xử lý việc này bằng cách sau khi Pop một phần tử ra khỏi Queue, mình sẽ dịch chuyển toàn bộ Queue về vị trí phần tử 0 của mảng. Điều này có tác dụng là Rear sẽ giảm xuống và Queue có thể lưu được thêm nhiều phần tử. Tuy nhiên nhược điểm là việc dịch chuyển như vậy gây mất thêm thời gian khi Pop, làm giảm hiệu suất chương trình.
⇒ Vì vậy, chúng ta cần một dạng Queue khác có phần nhiều ưu điểm hơn, đó là Circular Queue.
👉 Circular Queue
Circular Queue thực chất là một biến thể của Regular Queue, với phần tử đầu và cuối của mảng được kết nốt với nhau, tạo thành một hình tròn, nhằm mục tiêu tối ưu hóa không gian hoạt động của Queue.
⇒ Các bạn có thể xem hoạt động của Circular Queue trong hình dưới đây:
⇒ Có thể thấy khi mà Queue đầy (rear đến phần tử cuối) và chúng ta pop data, phần trống mà data pop ra bỏ lại có thể được dùng làm phần tử tiếp theo của Queue. Như vậy, chúng ta vừa không mất thời gian để dịch chuyển mảng như cách trên của mình, vừa có thể dễ dàng add thêm phần tử vào Queue.
👉 Triển khai Circular Queue
Hoạt động của Circular Queue cũng tương tự như Regular Queue, chỉ khác phần tử đầu và cuối của mảng nối với nhau. Các bạn xem thuật toán sau để tính toán lại giá trị của REAR khi vượt quá index lớn nhất của mảng:
if (REAR + 1) == SIZE (overflow!), REAR = (REAR + 1) % SIZE = 0 (start of queue)- Circular Queue sẽ đầy khi nó chứa full data.
>>>= Follow ngay =<<<
Để nhận được những bài học miễn phí mới nhất nhé 😊
Chúc các bạn học tập tốt 😊
0 Nhận xét