Kiểu cấu trúc dữ liệu Circular Queue và ứng dụng

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về cấu tr&uacute;c dữ liệu Circular Queue hay kiểu cấu tr&uacute;c h&agrave;ng đợi v&ograve;ng, c&aacute;ch thực hiện triển khai Circular Queue bằng ng&ocirc;n ngữ lập tr&igrave;nh C bằng v&iacute; dụ dẫn chứng.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Circular Queue hay h&agrave;ng đợi v&ograve;ng gi&uacute;p tr&aacute;nh l&atilde;ng ph&iacute; kh&ocirc;ng gian trong việc triển khai h&agrave;ng đợi th&ocirc;ng thường bằng c&aacute;ch sử dụng mảng.</p> <h2 style="text-align: justify;">2. C&aacute;ch thức hoạt động của Circular Queue</h2> <p style="text-align: justify;">H&agrave;ng đợi v&ograve;ng hoạt động theo quy tr&igrave;nh tăng gi&aacute; trị theo v&ograve;ng tr&ograve;n, tức l&agrave; khi ch&uacute;ng ta cố gắng tăng con trỏ v&agrave; ch&uacute;ng ta đến cuối h&agrave;ng đợi, ch&uacute;ng ta sẽ bắt đầu từ đầu của h&agrave;ng đợi.</p> <p style="text-align: justify;">Ở đ&acirc;y, việc tăng gi&aacute; trị theo v&ograve;ng tr&ograve;n được thực hiện bằng ph&eacute;p chia modulo với k&iacute;ch thước h&agrave;ng đợi.</p> <p style="text-align: justify;">H&agrave;ng đợi v&ograve;ng c&oacute; c&aacute;ch thức hoạt động như sau:</p> <ol style="text-align: justify;"> <li>Bao gồm 2 con trỏ FRONT v&agrave; REAR.</li> <li>Con trỏ FRONT theo d&otilde;i phần tử đầu ti&ecirc;n của h&agrave;ng đợi.</li> <li>Con trỏ REAR theo d&otilde;i phần tử cuối c&ugrave;ng của h&agrave;ng đợi.</li> <li>Ban đầu, ta thực hiện đặt gi&aacute; trị của FRONT v&agrave; REAR bằng với gi&aacute; trị l&agrave; -1.</li> </ol> <h2 style="text-align: justify;">3. C&aacute;c thao t&aacute;c của Circular Queue</h2> <p style="text-align: justify;"><strong><em>3.1. Thao t&aacute;c th&ecirc;m phần tử</em></strong></p> <ol style="text-align: justify;"> <li>Kiểm tra xem h&agrave;ng đợi đ&atilde; đầy chưa, nếu đầy th&igrave; đưa ra th&ocirc;ng b&aacute;o.</li> <li>Đối với phần tử đầu ti&ecirc;n, đặt gi&aacute; trị của con trỏ FRONT l&agrave; gi&aacute; trị 0.</li> <li>Tăng chỉ số của con trỏ REAR theo v&ograve;ng tr&ograve;n l&ecirc;n 1 đơn vị (tức l&agrave; nếu Rear đạt đến phần tử cuối, n&oacute; sẽ nằm ở đầu h&agrave;ng đợi).</li> <li>Th&ecirc;m phần tử mới v&agrave;o vị tr&iacute; được trỏ tới bởi REAR.</li> </ol> <p style="text-align: justify;"><strong><em>3.2. Thao t&aacute;c x&oacute;a phần tử</em></strong></p> <ol style="text-align: justify;"> <li>Kiểm tra xem h&agrave;ng đợi c&oacute; rỗng hay kh&ocirc;ng, nếu c&oacute; th&igrave; đưa ra th&ocirc;ng b&aacute;o.</li> <li>Trả về gi&aacute; trị được trỏ bởi FRONT.</li> <li>Tăng chỉ số FRONT theo v&ograve;ng tr&ograve;n 1.</li> <li>Đối với phần tử cuối c&ugrave;ng, đặt lại c&aacute;c gi&aacute; trị của FRONT v&agrave; REAR th&agrave;nh -1.</li> </ol> <p style="text-align: justify;">Tuy nhi&ecirc;n, việc kiểm tra h&agrave;ng đợi đầy hay kh&ocirc;ng c&oacute; một trường hợp bổ sung mới như sau:</p> <ul style="text-align: justify;"> <li>Trường hợp 1: FRONT = 0 &amp;&amp; REAR == SIZE - 1</li> <li>Trường hợp 2: FRONT = REAR + 1</li> </ul> <p style="text-align: justify;">Trường hợp thứ hai xảy ra khi REAR bắt đầu từ 0 do việc tăng gi&aacute; trị theo v&ograve;ng tr&ograve;n v&agrave; khi gi&aacute; trị của n&oacute; nhỏ hơn 1 đơn vị so với FRONT, th&igrave; l&uacute;c n&agrave;y h&agrave;ng đợi đầy.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/8fa96e91-ccec-475e-ba7a-88c5ec9b0754" alt="circular-queue" /><img style="width: 100%;" src="../../../public_files/21bf754b-dd6e-438c-b63c-6c444878a327" alt="circular-queue-4" /><img style="width: 100%;" src="../../../public_files/95544be0-4048-4a9a-9edb-f0f6c63cec23" alt="circular-queue-2" /><img style="width: 100%;" src="../../../public_files/e83b9c57-e68f-46e8-8c62-476bb5c87862" alt="circular-queue-5" /><img style="width: 100%;" src="../../../public_files/b64ede01-c623-4561-95c4-11601b2a46e9" alt="circular-queue-3" /><img style="width: 100%;" src="../../../public_files/208149d2-490f-4e1d-ba81-8374f768d211" alt="circular-queue-6" /><img class="aligncenter size-full wp-image-8823" src="../../../wp-content/uploads/2021/02/Capture-227.png" alt="" width="100%" /></p> <p style="text-align: justify;">Việc triển khai h&agrave;ng đợi phổ biến nhất l&agrave; sử dụng kiểu cấu tr&uacute;c dữ liệu mảng, nhưng n&oacute; cũng c&oacute; thể được triển khai bằng c&aacute;ch sử dụng cấu tr&uacute;c danh s&aacute;ch.</p> <p style="text-align: justify;">V&iacute; dụ:</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; #define MAX 5 int data[MAX]; int front = -1, rear = -1; int full() { if ((front == rear + 1) || (front == 0 &amp;&amp; rear == MAX - 1)) return 1; return 0; } int emp() { if (front == -1) return 1; return 0; } void enQueue(int new_data) { if (full()) printf("\nH&agrave;ng đợi đầy\n"); else { if (front == -1) front = 0; rear = (rear + 1) % MAX; data[rear] = new_data; printf("\n %d đ&atilde; được th&ecirc;m", new_data); } } int deQueue() { int a; if (emp()) { printf("\nH&agrave;ng đợi rỗng\n"); return (-1); } else { a = data[front]; if (front == rear) { front = -1; rear = -1; } else { front = (front + 1) % MAX; } printf("\n %d đ&atilde; được x&oacute;a\n", a); return (a); } } void print() { int i; if (emp()) printf("\nH&agrave;ng đợi rỗng\n"); else { printf("\n Front = %d", front); printf("\n Gi&aacute; trị: ("); for (i = front; i != rear; i = (i + 1) % MAX) { printf("%d, ", data[i]); } printf("%d)", data[i]); printf("\n Rear = %d\n", rear); } } int main() { enQueue(34); enQueue(29); enQueue(31); enQueue(38); enQueue(100); print(); deQueue(); print(); enQueue(8); return 0; }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>34 đ&atilde; được th&ecirc;m 29 đ&atilde; được th&ecirc;m 31 đ&atilde; được th&ecirc;m 38 đ&atilde; được th&ecirc;m 100 đ&atilde; được th&ecirc;m Front = 0 Gi&aacute; trị: (34, 29, 31, 38, 100) Rear = 4 34 đ&atilde; được x&oacute;a Front = 1 Gi&aacute; trị: (29, 31, 38, 100) Rear = 4 8 đ&atilde; được th&ecirc;m</code></pre> <h2 style="text-align: justify;">4. Độ phức tạp</h2> <p style="text-align: justify;">Độ phức tạp của c&aacute;c thao t&aacute;c th&ecirc;m phần tử v&agrave; x&oacute;a phần tử trong một h&agrave;ng đợi v&ograve;ng l&agrave; O(1) (đối với việc triển khai bằng kiểu dữ liệu mảng).</p> <h2 style="text-align: justify;">5. Ứng dụng của h&agrave;ng đợi v&ograve;ng</h2> <ul style="text-align: justify;"> <li>Lập lịch CPU</li> <li>Quản l&yacute; bộ nhớ</li> <li>Quản l&yacute; lưu lượng</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về kiểu cấu tr&uacute;c dữ liệu Circular Queue. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n <a href="http://tek4.vn">tek4</a> nh&eacute;!</p>