Cấu trúc dữ liệu hàng đợi Deque và các thao tác trên Deque

<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ề kiểu cấu tr&uacute;c dữ liệu h&agrave;ng đợi Deque c&ugrave;ng c&aacute;c h&igrave;nh ảnh minh họa. Ngo&agrave;i ra, ta sẽ triển khai Deque 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;">Deque/ Double Ended Queue hay h&agrave;ng đợi hai đầu l&agrave; một loại h&agrave;ng đợi trong đ&oacute; việc ch&egrave;n v&agrave; loại bỏ c&aacute;c phần tử c&oacute; thể được thực hiện từ ph&iacute;a trước hoặc ph&iacute;a sau. Do đ&oacute;, n&oacute; kh&ocirc;ng tu&acirc;n theo quy tắc FIFO (First In First Out - V&agrave;o trước ra trước).</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/67bbdfc9-4780-4c5a-8b23-a2ffc9b6f727" alt="cau-truc-du-lieu-hang-doi-deque" /></p> <h2 style="text-align: justify;">2. C&aacute;c kiểu Deque</h2> <ol style="text-align: justify;"> <li>Deque bị hạn chế đầu v&agrave;o: Trong đ&oacute;, đầu v&agrave;o bị hạn chế ở một đầu nhưng cho ph&eacute;p x&oacute;a ở cả hai đầu.</li> <li>Deque bị hạn chế đầu ra: Trong đ&oacute;, đầu ra bị hạn chế ở một đầu nhưng cho ph&eacute;p ch&egrave;n ở cả hai đầu.</li> </ol> <h2 style="text-align: justify;">3. C&aacute;c thao t&aacute;c tr&ecirc;n h&agrave;ng đợi Deque</h2> <p style="text-align: justify;">Dưới đ&acirc;y l&agrave; c&aacute;ch thức triển khai mảng v&ograve;ng của h&agrave;ng đợi . Trong mảng v&ograve;ng, nếu mảng đầy th&igrave; ta sẽ bắt đầu lại từ đầu. Trong triển khai mảng tuyến t&iacute;nh, nếu mảng đ&atilde; đầy th&igrave; kh&ocirc;ng thể ch&egrave;n th&ecirc;m phần tử n&agrave;o nữa. Trong mỗi thao t&aacute;c b&ecirc;n dưới đ&acirc;y, nếu mảng đầy, một th&ocirc;ng b&aacute;o sẽ được đưa ra.</p> <p style="text-align: justify;">Trước khi thực hiện c&aacute;c thao t&aacute;c, ta sẽ l&agrave;m theo c&aacute;c bước sau.</p> <ul style="text-align: justify;"> <li>Lấy một mảng (Deque) c&oacute; k&iacute;ch thước n.</li> <li>Đặt hai con trỏ ở vị tr&iacute; đầu ti&ecirc;n v&agrave; đặt Front = -1 v&agrave; Rear = 0.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/6b3a17d8-9e69-4948-bb8a-9a0453e36208" alt="cau-truc-du-lieu-hang-doi-deque-2" /></p> <h3 style="text-align: justify;">3.1. Ch&egrave;n phần tử ở v&iacute; trị đầu ti&ecirc;n</h3> <p style="text-align: justify;">Thao t&aacute;c n&agrave;y th&ecirc;m một phần tử ở vị tr&iacute; đầu ti&ecirc;n được trỏ bởi Front.</p> <ul style="text-align: justify;"> <li>Kiểm tra vị tr&iacute; của Front.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/433071bf-a7a8-400d-bcdf-8bb0b38cfb25" alt="cau-truc-du-lieu-hang-doi-deque-5" /></p> <ul style="text-align: justify;"> <li>Nếu gi&aacute; trị của Front &lt; 1, g&aacute;n lại Front = n-1 (chỉ số cuối c&ugrave;ng).</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/ffad9d9c-8552-4acd-ad29-e6e987a7f906" alt="cau-truc-du-lieu-hang-doi-deque-6" /></p> <ul style="text-align: justify;"> <li>Mặt kh&aacute;c, giảm gi&aacute; trị của Front đi 1 đơn vị.</li> <li>Th&ecirc;m kh&oacute;a 32 mới v&agrave;o mảng c&oacute; chỉ số bằng với gi&aacute; trị của Front.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/ad85784a-6855-464d-8457-3d660b4710e6" alt="cau-truc-du-lieu-hang-doi-deque-7" /></p> <h3 style="text-align: justify;">3.2. Ch&egrave;n phần tử ở ph&iacute;a sau</h3> <p style="text-align: justify;">Thao t&aacute;c n&agrave;y th&ecirc;m một phần tử v&agrave;o ph&iacute;a sau được trỏ bởi Rear.</p> <ul style="text-align: justify;"> <li>Kiểm tra xem mảng đ&atilde; đầy hay chưa</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/63d89959-3b24-46c1-b268-e261de12f2b8" alt="cau-truc-du-lieu-hang-doi-deque-8" /></p> <ul style="text-align: justify;"> <li>Nếu h&agrave;ng đợi Deque đầy, g&aacute;n lại Rear = 0.</li> <li>Nếu kh&ocirc;ng, tăng Rear th&ecirc;m 1 đơn vị.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/b0eea29a-3c5e-4842-99e5-5f820e0a5739" alt="cau-truc-du-lieu-hang-doi-deque-9" /></p> <ul style="text-align: justify;"> <li>Th&ecirc;m phần tử mới v&agrave;o.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/1288fc09-ea5f-4ca2-b173-27d77734dbd1" alt="cau-truc-du-lieu-hang-doi-deque-10" /></p> <h3 style="text-align: justify;">3.3. X&oacute;a phần tử ở vị tr&iacute; đầu ti&ecirc;n</h3> <p style="text-align: justify;">Thao t&aacute;c x&oacute;a một phần tử ở ph&iacute;a trước của h&agrave;ng đợi được trỏ bởi Front.</p> <ul style="text-align: justify;"> <li>Kiểm tra xem h&agrave;ng đợi Deque c&oacute; trống rỗng hay kh&ocirc;ng.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/1ea72749-1556-4538-9660-811f96297281" alt="cau-truc-du-lieu-hang-doi-deque-11" /></p> <ul style="text-align: justify;"> <li>Nếu h&agrave;ng đợi Deque trống (tức l&agrave; front = -1), sẽ kh&ocirc;ng thể thực hiện x&oacute;a phần tử (điều kiện Underflow).</li> <li>Nếu h&agrave;ng đợi Deque chỉ c&oacute; một phần tử (tức l&agrave; Front = Rear), ta sẽ đặt Front = -1 v&agrave; Rear = -1.</li> <li>Ngược lại nếu Front ở cuối (tức l&agrave; Front = n - 1), ta sẽ đặt Front = 0.</li> <li>Mặt kh&aacute;c, Front = Front + 1</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/8b71005a-992f-46bd-b875-087fa858051b" alt="cau-truc-du-lieu-hang-doi-deque-12" /></p> <h3 style="text-align: justify;">3.4. X&oacute;a phần tử ở cuối h&agrave;ng đợi</h3> <p style="text-align: justify;">Thao t&aacute;c n&agrave;y sẽ x&oacute;a một phần tử từ ph&iacute;a sau h&agrave;ng đợi được trỏ bởi Rear.</p> <ul style="text-align: justify;"> <li>Kiểm tra xem h&agrave;ng đợi c&oacute; trống rỗng hay kh&ocirc;ng.</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/c7e3af0e-dbdc-4bf8-baee-3d504fc3dd0c" alt="cau-truc-du-lieu-hang-doi-deque-13" /></p> <ul style="text-align: justify;"> <li>Nếu h&agrave;ng đợi trống rỗng (tức l&agrave; Front = -1), th&igrave; kh&ocirc;ng thể thực hiện x&oacute;a (điều kiện Underflow).</li> <li>Nếu h&agrave;ng đợi chỉ c&oacute; một phần tử (tức l&agrave; Front = Rear), ta sẽ đặt Front = -1 v&agrave; Rear = -1, mặt kh&aacute;c ta sẽ l&agrave;m theo c&aacute;c bước b&ecirc;n dưới.</li> <li>Nếu Rear ở ph&iacute;a trước (tức l&agrave; Rear = 0), ta sẽ đặt Rear = n - 1.</li> <li>Mặt kh&aacute;c, Rear = Rear &ndash; 1</li> </ul> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/f62b1fc1-31ad-44d4-a2ed-d9b8d3ff5587" alt="cau-truc-du-lieu-hang-doi-deque-14" /></p> <h3 style="text-align: justify;">3.5. Kiểm tra h&agrave;ng đợi c&oacute; rỗng hay kh&ocirc;ng</h3> <p style="text-align: justify;">Thao t&aacute;c n&agrave;y kiểm tra xem h&agrave;ng đợi Deque c&oacute; rỗng hay kh&ocirc;ng. Nếu front = -1, th&igrave; h&agrave;ng đợi Deque l&agrave; rỗng.</p> <h3 style="text-align: justify;">3.6. Kiểm tra h&agrave;ng đợi đ&atilde; đầy hay chưa</h3> <p style="text-align: justify;">Thao t&aacute;c n&agrave;y kiểm tra xem Deque đ&atilde; đầy hay chưa. Nếu Front = 0 v&agrave; Rear = n - 1 hoặc Front = Rear + 1, th&igrave; h&agrave;ng đợi Deque đ&atilde; đầy.</p> <h2 style="text-align: justify;">4. Triển khai cấu tr&uacute;c dữ liệu Deque</h2> <p style="text-align: justify;">V&iacute; dụ: Triển khai h&agrave;ng đợi Deque bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; #define SIZE 8 void insert_front(int *, int, int *, int *); void insert_rear(int *, int, int *, int *); int remove_front(int *, int *, int *); int remove_rear(int *, int *, int *); void print(int *); int count_element(int *); int main() { int a[SIZE]; int front, rear, i, number; front = rear = -1; for (i = 0; i &lt; SIZE; i++) a[i] = 0; insert_rear(a, 14, &amp;front, &amp;rear); insert_front(a, 32, &amp;front, &amp;rear); insert_rear(a, 44, &amp;front, &amp;rear); insert_front(a, 13, &amp;front, &amp;rear); insert_rear(a, 12, &amp;front, &amp;rear); printf("Phần tử trong h&agrave;ng đợi: "); print(a); printf("\nX&oacute;a ở ph&iacute;a trước:"); i = remove_front(a, &amp;front, &amp;rear); printf("\n %d đ&atilde; được x&oacute;a", i); print(a); printf("\nX&oacute;a ở ph&iacute;a sau:"); i = remove_rear(a, &amp;front, &amp;rear); printf("\n %d đ&atilde; được x&oacute;a", i); print(a); number = count_element(a); printf("\nSố phần tử trong h&agrave;ng đợi: %d\n", number); } void insert_front(int *a, int data, int *front, int *rear) { int i, k, c; if (*front == 0 &amp;&amp; *rear == SIZE - 1) { printf("\nĐ&atilde; đầy\n"); return; } if (*front == -1) { *front = *rear = 0; a[*front] = data; return; } if (*rear != SIZE - 1) { c = count_element(a); k = *rear + 1; for (i = 1; i &lt;= c; i++) { a[k] = a[k - 1]; k--; } a[k] = data; *front = k; (*rear)++; } else { (*front)--; a[*front] = data; } } void insert_rear(int *a, int data, int *front, int *rear) { int i, k; if (*front == 0 &amp;&amp; *rear == SIZE - 1) { printf("\nĐ&atilde; đầy\n"); return; } if (*front == -1) { *rear = *front = 0; a[*rear] = data; return; } if (*rear == SIZE - 1) { k = *front - 1; for (i = *front - 1; i &lt; *rear; i++) { k = i; if (k == SIZE - 1) a[k] = 0; else a[k] = a[i + 1]; } (*rear)--; (*front)--; } (*rear)++; a[*rear] = data; } int remove_front(int *a, int *front, int *rear) { int data; if (*front == -1) { printf("\nH&agrave;ng đợi rỗng\n"); return 0; } data = a[*front]; a[*front] = 0; if (*front == *rear) *front = *rear = -1; else (*front)++; return data; } int remove_rear(int *a, int *front, int *rear) { int data; if (*front == -1) { printf("\n H&agrave;ng đợi rỗng\n"); return 0; } data = a[*rear]; a[*rear] = 0; (*rear)--; if (*rear == -1) *front = -1; return data; } void print(int *a) { for (int i = 0; i &lt; SIZE; i++) printf(" %d", a[i]); } int count_element(int *a) { int k = 0; for (int i = 0; i &lt; SIZE; i++) { if (a[i] != 0) k++; } return k; }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>Phần tử trong h&agrave;ng đợi: 13 32 14 44 12 0 0 0 X&oacute;a ở ph&iacute;a trước: 13 đ&atilde; được x&oacute;a 0 32 14 44 12 0 0 0 X&oacute;a ở ph&iacute;a sau: 12 đ&atilde; được x&oacute;a 0 32 14 44 0 0 0 0 Số phần tử trong h&agrave;ng đợi: 3</code></pre> <h2 style="text-align: justify;">5. C&aacute;c ứng dụng của cấu tr&uacute;c dữ liệu Deque</h2> <ul style="text-align: justify;"> <li>Sử dụng cho c&aacute;c thao t&aacute;c ho&agrave;n t&aacute;c (Undo) tr&ecirc;n phần mềm.</li> <li>Để lưu trữ lịch sử trong tr&igrave;nh duyệt.</li> <li>Để triển khai cả ngăn xếp v&agrave; h&agrave;ng đợi.</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ề h&agrave;ng đợi Deque. 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>