Khái niệm và các thao tác của hàng đợi

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ t&igrave;m hiểu về cấu tr&uacute;c dữ liệu h&agrave;ng đợi. Ngo&agrave;i ra, ta sẽ thực hiện triển khai kiểu cấu tr&uacute;c dữ liệu n&agrave;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">H&agrave;ng đợi l&agrave; một cấu tr&uacute;c dữ liệu hữu &iacute;ch trong lập tr&igrave;nh, hơi giống với kiểu cấu tr&uacute;c ngăn xếp. Tuy nhi&ecirc;n, n&oacute; kh&aacute;c với ngăn xếp ở chỗ l&agrave; h&agrave;ng đợi được mở ở cả hai đầu của n&oacute;. Một đầu lu&ocirc;n d&ugrave;ng để th&ecirc;m phần tử (enqueue) v&agrave; đầu kia d&ugrave;ng để lấy ra phần tử (dequeue). N&oacute; giống như khi ta xếp h&agrave;ng mua v&eacute; b&ecirc;n ngo&agrave;i rạp chiếu phim, người đầu ti&ecirc;n v&agrave;o h&agrave;ng trước l&agrave; người đầu ti&ecirc;n nhận được v&eacute;.</p> <p style="text-align: justify;">H&agrave;ng đợi tu&acirc;n theo quy tắc V&agrave;o trước ra trước (FIFO), trong đ&oacute;, phần tử đi v&agrave;o trước l&agrave; phần tử đi ra trước.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/6ebd63a1-d58c-41f4-8803-e400d3e2fa6b" alt="hang-doi" /></p> <p style="text-align: justify;">Trong h&igrave;nh tr&ecirc;n, khối n&agrave;o v&agrave;o trước sẽ được đi ra trước. N&oacute; tu&acirc;n theo quy tắc FIFO. Theo thuật ngữ lập tr&igrave;nh, việc đưa c&aacute;c phần tử v&agrave;o h&agrave;ng đợi được gọi l&agrave; enqueue v&agrave; việc x&oacute;a c&aacute;c mục khỏi h&agrave;ng đợi được gọi l&agrave; dequeue.</p> <p style="text-align: justify;">Ch&uacute;ng ta c&oacute; thể triển khai h&agrave;ng đợi bằng bất kỳ ng&ocirc;n ngữ lập tr&igrave;nh n&agrave;o như C, C ++, Java, Python hoặc C #, nhưng đặc điểm về kỹ thuật l&agrave; tương đối giống nhau.</p> <h2 style="text-align: justify;">2. Khởi tạo h&agrave;ng đợi</h2> <p style="text-align: justify;">C&aacute;ch thức khởi tạo h&agrave;ng đợi bao gồm như sau:</p> <ol style="text-align: justify;"> <li>Tạo 2 con trỏ với t&ecirc;n gọi l&agrave; FRONT v&agrave; REAR.</li> <li>Con trỏ FRONT trỏ tới phần tử đầu ti&ecirc;n của h&agrave;ng đợi.</li> <li>Con trỏ REAR trỏ tới phần tử cuối c&ugrave;ng của h&agrave;ng đợi.</li> <li>Ch&uacute;ng ta đặt gi&aacute; trị của FRONT v&agrave; REAR c&oacute; gi&aacute; trị l&agrave; -1 l&uacute;c ban đầu (Khi h&agrave;ng đợi rỗng).</li> </ol> <h2 style="text-align: justify;">3. C&aacute;c thao t&aacute;c cơ bản của cấu tr&uacute;c dữ liệu h&agrave;ng đợi</h2> <p style="text-align: justify;">H&agrave;ng đợi l&agrave; một đối tượng (cấu tr&uacute;c dữ liệu trừu tượng - ADT) cho ph&eacute;p c&aacute;c thao t&aacute;c sau:</p> <ul style="text-align: justify;"> <li>Enqueue: Th&ecirc;m một phần tử v&agrave;o cuối h&agrave;ng đợi.</li> <li>Dequeue: X&oacute;a một phần tử khỏi đầu h&agrave;ng đợi.</li> <li>IsEmpty: Kiểm tra xem h&agrave;ng đợi c&oacute; trống rỗng hay kh&ocirc;ng.</li> <li>IsFull: Kiểm tra xem h&agrave;ng đợi đ&atilde; đầy hay chưa.</li> <li>Peek: Nhận gi&aacute; trị ph&iacute;a trước của h&agrave;ng đợi m&agrave; kh&ocirc;ng cần x&oacute;a n&oacute;.</li> </ul> <h3 style="text-align: justify;">3.1. Thao t&aacute;c th&ecirc;m phần tử v&agrave;o h&agrave;ng đợi</h3> <p style="text-align: justify;">C&aacute;c thao t&aacute;c khi th&ecirc;m một phần tử v&agrave;o h&agrave;ng đợi như sau:</p> <ol style="text-align: justify;"> <li>Kiểm tra xem h&agrave;ng đợi đ&atilde; đầy hay 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, ta sẽ đặt gi&aacute; trị của FRONT th&agrave;nh 0.</li> <li>Tăng chỉ số REAR l&ecirc;n 1 đơn vị.</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;"><img style="width: 100%;" src="../../../public_files/cdb5fac7-0488-4f77-9f16-10a711780ed9" alt="hang-doi-2" /></p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/d8b84fd4-264a-46cd-9e73-fbf070b7202d" alt="hang-doi-4" /><img style="width: 100%;" src="../../../public_files/45d570ea-7ab9-475d-b4bd-30c049efb775" alt="hang-doi-3" /></p> <h3 style="text-align: justify;">3.2. Thao t&aacute;c lấy ra phần tử khỏi h&agrave;ng đợi</h3> <ol style="text-align: justify;"> <li>Kiểm tra xem h&agrave;ng đợi c&oacute; trống rỗng hay kh&ocirc;ng, nếu rỗng th&igrave; đưa ra th&ocirc;ng b&aacute;o l&agrave; kh&ocirc;ng thể lấy ra phần tử.</li> <li>Trả về gi&aacute; trị được trỏ bởi FRONT.</li> <li>Tăng chỉ số FRONT l&ecirc;n 1 đơn vị.</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;"><img style="width: 100%;" src="../../../public_files/bbe4845e-e375-4a0d-b8e9-66afaf3e8f0d" alt="hang-doi-7" /><img style="width: 100%;" src="../../../public_files/dcdd68ec-ddcb-467b-9716-68c346a158a3" alt="hang-doi-6" /><img style="width: 100%;" src="../../../public_files/c5cf19fd-75b4-4972-94a9-fbee4312984d" alt="hang-doi-5" /></p> <p style="text-align: justify;">Giống như trong ngăn xếp, h&agrave;ng đợi cũng c&oacute; thể được triển khai bằng kiểu cấu tr&uacute;c mảng, danh s&aacute;ch li&ecirc;n kết, con trỏ v&agrave; cấu tr&uacute;c struct. Trong v&iacute; dụ b&ecirc;n dưới đ&acirc;y, ch&uacute;ng ta sẽ triển khai h&agrave;ng đợi bằng c&aacute;ch sử dụng mảng một chiều.</p> <p style="text-align: justify;">V&iacute; dụ: Sử dụng mảng một chiều cho h&agrave;ng đợi với số lượng tối đa l&agrave; 5.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; #define MAX 5 int data[MAX], front = -1, rear = -1; void enQueue(int new_data) { if (rear == MAX - 1) printf("\nH&agrave;ng đợi đ&atilde; đầy\n"); else { if (front == -1) front = 0; rear++; data[rear] = new_data; printf("\n %d đ&atilde; được th&ecirc;m", new_data); printf("\n"); } } void deQueue() { if (front == -1) printf("\nH&agrave;ng đợi rỗng\n"); else { printf("\n %d đ&atilde; được lấy ra\n", data[front]); front++; if (front &gt; rear) front = rear = -1; } } void print() { printf("\n"); if (rear == -1) printf("H&agrave;ng đợi rỗng\n"); else { printf("C&aacute;c phần tử l&agrave;: "); for (int i = front; i &lt;= rear; i++) printf("%d ", data[i]); } printf("\n"); } int main() { deQueue(); enQueue(32); enQueue(42); enQueue(33); enQueue(28); print(); deQueue(); print(); return 0; }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>H&agrave;ng đợi rỗng 32 đ&atilde; được th&ecirc;m 42 đ&atilde; được th&ecirc;m 33 đ&atilde; được th&ecirc;m 28 đ&atilde; được th&ecirc;m C&aacute;c phần tử l&agrave;: 32 42 33 28 32 đ&atilde; được lấy ra C&aacute;c phần tử l&agrave;: 42 33 28</code></pre> <h2 style="text-align: justify;">4. Mặt hạn chế của h&agrave;ng đợi</h2> <p style="text-align: justify;">Sau khi th&ecirc;m v&agrave; lấy ra c&aacute;c phần tử, k&iacute;ch thước của h&agrave;ng đợi sẽ giảm xuống. V&agrave; ch&uacute;ng ta chỉ c&oacute; thể th&ecirc;m chỉ số 0 v&agrave; 1 khi h&agrave;ng đợi được đặt lại (khi tất cả c&aacute;c phần tử đ&atilde; được lấy ra).</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/c42d1b57-546b-44de-a7a4-fd2cd861f7b2" alt="hang-doi-8" /></p> <p style="text-align: justify;">Sau khi REAR đạt đến chỉ số cuối c&ugrave;ng, nếu ch&uacute;ng ta c&oacute; thể lưu trữ th&ecirc;m c&aacute;c phần tử trong c&aacute;c kh&ocirc;ng gian trống (0 v&agrave; 1), ch&uacute;ng ta c&oacute; thể tận dụng c&aacute;c kh&ocirc;ng gian trống n&agrave;y. Điều n&agrave;y được thực hiện bởi một h&agrave;ng đợi được gọi l&agrave; h&agrave;ng đợi v&ograve;ng.</p> <h2 style="text-align: justify;">5. Ứng dụng của h&agrave;ng đợi</h2> <ul style="text-align: justify;"> <li>Lập lịch CPU, lập lịch cho đĩa.</li> <li>Khi dữ liệu được truyền th&ocirc;ng đồng bộ giữa hai tiến tr&igrave;nh, h&agrave;ng đợi được sử dụng để đồng bộ h&oacute;a. V&iacute; dụ: Bộ đệm IO, , tệp IO,...</li> <li>Xử l&yacute; c&aacute;c ngắt đứt đoạn trong hệ thống thời gian thực.</li> <li>Hệ thống điện thoại Call Center sử dụng h&agrave;ng đợi để lưu trữ những người đang gọi theo thứ tự.</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ề cấu tr&uacute;c dữ liệu h&agrave;ng đợi. 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>