Cấu trúc dữ liệu ngăn xếp là gì?

<p style="text-align: justify;">Ngăn xếp (t&ecirc;n tiếng anh l&agrave; Stack) l&agrave; một trong c&aacute;c cấu tr&uacute;c dữ liệu phổ biến. Trong b&agrave;i viết n&agrave;y, ta sẽ t&igrave;m hiểu về kiểu cấu tr&uacute;c dữ liệu n&agrave;y v&agrave; c&aacute;ch triển khai n&oacute; bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm về ngăn xếp</h2> <p style="text-align: justify;">Ngăn xếp hay Stack l&agrave; một cấu tr&uacute;c dữ liệu rất hữu &iacute;ch trong lập tr&igrave;nh. Stack l&agrave; một cấu tr&uacute;c dữ liệu tuyến t&iacute;nh v&agrave; tu&acirc;n theo một thứ tự cụ thể m&agrave; c&aacute;c thao t&aacute;c kh&aacute;c nhau được thực hiện tr&ecirc;n đ&oacute;. Thứ tự thực hiện c&oacute; thể l&agrave; LIFO (Last In First Out - V&agrave;o sau ra trước) hoặc FILO (First In Last out - V&agrave;o trước ra sau). Ta c&oacute; thể coi n&oacute; giống như một chồng đĩa được xếp chồng l&ecirc;n nhau (H&igrave;nh minh họa b&ecirc;n dưới).</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/c378023d-405c-4b51-aebc-6ff953100e94" alt="ngan-xep" /></p> <p style="text-align: justify;">Với một chồng đĩa như vậy, ta c&oacute; thể l&agrave;m c&aacute;c thao t&aacute;c như sau:</p> <ul style="text-align: justify;"> <li>Đặt một đĩa mới l&ecirc;n tr&ecirc;n c&ugrave;ng</li> <li>Loại bỏ một tấm đĩa tr&ecirc;n c&ugrave;ng.</li> </ul> <p style="text-align: justify;">Nếu ta muốn lấy đĩa ở dưới c&ugrave;ng, trước ti&ecirc;n ta phải loại bỏ cả c&aacute;c đĩa ở b&ecirc;n tr&ecirc;n ra ri&ecirc;ng v&agrave; sau đ&oacute; mới lấy chiếc đĩa nằm ở cuối c&ugrave;ng. C&aacute;ch sắp xếp như vậy được gọi l&agrave; LIFO hay Last In First Out &ndash; V&agrave;o sau ra trước.</p> <h2 style="text-align: justify;">2. Nguy&ecirc;n tắc LIFO của ngăn xếp</h2> <p style="text-align: justify;">Theo thuật ngữ lập tr&igrave;nh, khi ta đặt một chiếc đĩa mới l&ecirc;n tr&ecirc;n được gọi l&agrave; <span class="lang:default decode:true crayon-inline">Push</span>(đẩy v&agrave;o) v&agrave; loại bỏ một chiếc đĩa được gọi l&agrave; <span class="lang:default decode:true crayon-inline">Pop</span>(lấy ra).</p> <p style="text-align: justify;">Thao t&aacute;c đẩy một phần tử mới v&agrave;o Stack được minh họa như h&igrave;nh b&ecirc;n dưới đ&acirc;y.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/b102f33f-ce22-41f2-bf78-2975b17051fa" alt="ngan-xep-2" /></p> <p style="text-align: justify;">Thao t&aacute;c lấy ra một phần tử mới v&agrave;o Stack được minh họa như h&igrave;nh b&ecirc;n dưới đ&acirc;y.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/1332f210-6d98-4989-abb4-cd57c03f71ff" alt="ngan-xep-3" /></p> <p style="text-align: justify;">Trong h&igrave;nh tr&ecirc;n, c&aacute;c khối được đẩy v&agrave;o v&agrave; lấy ra theo thứ tự lần lượt, n&oacute; tu&acirc;n theo nguy&ecirc;n tắc v&agrave;o sau ra trước, c&aacute;c phần tử được đẩy v&agrave;o trước sẽ được lấy ra ở lượt cuối c&ugrave;ng.</p> <h2 style="text-align: justify;">3. C&aacute;c thao t&aacute;c cơ bản với ngăn xếp</h2> <p style="text-align: justify;">Stack l&agrave; một đối tượng (kiểu dữ liệu trừu tượng) cho ph&eacute;p c&aacute;c thao t&aacute;c bao gồm như sau:</p> <ol style="text-align: justify;"> <li>Thao t&aacute;c đẩy v&agrave;o (Push): Th&ecirc;m một phần tử mới v&agrave;o đầu ngăn xếp.</li> <li>Thao t&aacute;c lấy ra (Pop): X&oacute;a một phần tử khỏi đầu ngăn xếp.</li> <li>Thao t&aacute;c IsEmpty (Kiểm tra rỗng hay kh&ocirc;ng): Kiểm tra xem Stack c&oacute; trống rỗng hay kh&ocirc;ng.</li> <li>Thao t&aacute;c IsFull (Kiểm tra đầy hay kh&ocirc;ng): Kiểm tra xem Stack đ&atilde; đầy hay chưa.</li> <li>Thao t&aacute;c Peek (Lấy gi&aacute; trị của phần tử tr&ecirc;n c&ugrave;ng): Lấy ra gi&aacute; trị của phần tử tr&ecirc;n c&ugrave;ng m&agrave; kh&ocirc;ng thực hiện x&oacute;a n&oacute;.</li> </ol> <p style="text-align: justify;"><strong>Ch&uacute; &yacute;: Thao t&aacute;c Peek với thao t&aacute;c Pop l&agrave; kh&aacute;c nhau.</strong></p> <h2 style="text-align: justify;">4. C&aacute;ch thức hoạt động của cấu tr&uacute;c dữ liệu Stack</h2> <p style="text-align: justify;">C&aacute;c thức hoạt động hoạt động như sau:</p> <ol style="text-align: justify;"> <li>Một con trỏ, c&oacute; t&ecirc;n gọi l&agrave; TOP, được sử dụng để theo d&otilde;i phần tử tr&ecirc;n c&ugrave;ng trong ngăn xếp.</li> <li>Khi khởi tạo ngăn xếp, ch&uacute;ng ta sẽ đặt gi&aacute; trị của n&oacute; l&agrave; -1 để c&oacute; thể kiểm tra xem ngăn xếp c&oacute; trống rỗng kh&ocirc;ng bằng c&aacute;ch so s&aacute;nh gi&aacute; trị của TOP với gi&aacute; trị l&agrave; -1.</li> <li>Khi đẩy một phần tử v&agrave;o, ch&uacute;ng ta sẽ kiểm tra xem ngăn xếp đ&atilde; đầy hay chưa (đầy hay kh&ocirc;ng t&ugrave;y thuộc v&agrave;o số lượng phần tử m&agrave; Stack c&oacute; thể chứa do người lập tr&igrave;nh định nghĩa), nếu chưa th&igrave; tăng gi&aacute; trị của TOP l&ecirc;n 1 đơn vị v&agrave; đặt phần tử mới v&agrave;o vị tr&iacute; m&agrave; TOP trỏ đến. Nếu đầy th&igrave; đưa ra th&ocirc;ng b&aacute;o l&agrave; kh&ocirc;ng thể th&ecirc;m phần tử nữa.</li> <li>Khi lấy ra một phần tử, ch&uacute;ng ta sẽ kiểm tra xem ngăn xếp c&oacute; rỗng hay kh&ocirc;ng, nếu kh&ocirc;ng th&igrave; trả về phần tử được trỏ đến bởi TOP v&agrave; giảm gi&aacute; trị của n&oacute; đi 1 đơn vị. Nếu c&oacute; th&igrave; đưa ra th&ocirc;ng b&aacute;o l&agrave; ngăn xếp rỗng.</li> <li>Trước khi đẩy phần tử v&agrave;o, ch&uacute;ng ta sẽ kiểm tra xem ngăn xếp đ&atilde; đầy hay chưa</li> <li>Trước khi lấy ra phần tử, ch&uacute;ng ta sẽ kiểm tra xem ngăn xếp rỗng hay kh&ocirc;ng</li> </ol> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/54959e3e-5771-4894-a352-e63c1b8ea189" alt="ngan-xep-4" /></p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/781cb6ae-651a-4c73-8f72-c3a17fb86bd7" alt="ngan-xep-5" /></p> <p style="text-align: justify;">Một Stack c&oacute; thể được triển khai bằng cấu tr&uacute;c dữ liệu dạng mảng, Struct, con trỏ hoặc danh s&aacute;ch li&ecirc;n kết. Stack c&oacute; thể c&oacute; k&iacute;ch thước cố định hoặc c&oacute; thể c&oacute; k&iacute;ch thước động. Ở đ&acirc;y, ch&uacute;ng ta sẽ triển khai bằng c&aacute;ch sử dụng mảng, l&agrave;m cho n&oacute; trở th&agrave;nh một Stack c&oacute; k&iacute;ch thước được cố định.</p> <p style="text-align: justify;">V&iacute; dụ: Triển khai cấu tr&uacute;c dữ liệu Stack bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define MAX 5 int count = 0; struct stack{ int data[MAX]; int top; }; typedef struct stack st; void init_st(st *s) { s-&gt;top = -1; } int isFull(st *s) { if (s-&gt;top == MAX - 1) return 1; else return 0; } int isEmp(st *s) { if (s-&gt;top == -1) return 1; else return 0; } void push(st *s, int new_data) { if (isFull(s)) { printf("\nStack đ&atilde; đầy\n"); } else { s-&gt;top++; s-&gt;data[s-&gt;top] = new_data; } count++; } void pop(st *s) { if (isEmp(s)) { printf("\nStack rỗng\n"); } else { printf("Phần tử lấy ra l&agrave;: %d", s-&gt;data[s-&gt;top]); s-&gt;top--; } count--; printf("\n"); } void printStack(st *s) { for (int i = 0; i &lt; count; i++) { printf("%d ", s-&gt;data[i]); } printf("\n"); } int main() { st *s = (st *)malloc(sizeof(st)); init_st(s); push(s, 32); push(s, 40); push(s, 68); printStack(s); pop(s); printStack(s); }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>32 40 68 Phần tử lấy ra l&agrave;: 68 32 40</code></pre> <h2 style="text-align: justify;">5. Ứng dụng của cấu tr&uacute;c dữ liệu Stack</h2> <p style="text-align: justify;">Mặc d&ugrave; Stack l&agrave; một cấu tr&uacute;c dữ liệu đơn giản, nhưng n&oacute; rất hữu &iacute;ch. C&aacute;c ứng dụng phổ biến nhất bao gồm như sau:</p> <ul style="text-align: justify;"> <li>Đảo ngược từ: Đặt tất cả c&aacute;c chữ c&aacute;i trong một Stack v&agrave; lấy lần lượt c&aacute;c k&yacute; tự ra. V&igrave; nguy&ecirc;n tắc l&agrave; LIFO (V&agrave;o sau ra trước), ta sẽ nhận được c&aacute;c chữ c&aacute;i được sắp xếp theo thứ tự ngược lại. V&iacute; dụ, "Python" sẽ được chuyển th&agrave;nh "nohtyP".</li> <li>Tr&igrave;nh bi&ecirc;n dịch sử dụng ngăn xếp để t&iacute;nh gi&aacute; trị của c&aacute;c biểu thức như 2 + 4/5 * (7 - 9) bằng c&aacute;ch chuyển đổi biểu thức sang dạng tiền tố hoặc hậu tố.</li> <li>Trong tr&igrave;nh duyệt Web: N&uacute;t quay lại trong tr&igrave;nh duyệt lưu tất cả c&aacute;c URL m&agrave; ta đ&atilde; truy cập trước đ&oacute; trong một cấu tr&uacute;c dữ liệu Stack. Mỗi lần ta truy cập một trang mới, n&oacute; sẽ được th&ecirc;m v&agrave;o tr&ecirc;n c&ugrave;ng của cấu tr&uacute;c. Khi ta nhấn n&uacute;t quay lại, URL hiện tại sẽ bị x&oacute;a khỏi ngăn xếp v&agrave; URL trước đ&oacute; sẽ được lấy ra.</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 ngăn xếp. 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>