I. Tổng quan về Stack Queue trong cấu trúc dữ liệu và thuật toán
Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và thuật toán là nền tảng cốt lõi để xây dựng các phần mềm hiệu quả. Trong số các cấu trúc dữ liệu tuyến tính, Stack và Queue là hai cấu trúc bị giới hạn về thao tác, nhưng lại có ứng dụng vô cùng rộng rãi. Không giống như danh sách thông thường cho phép chèn và xóa ở bất kỳ vị trí nào, Stack và Queue chỉ cho phép các thao tác này diễn ra ở hai đầu. Cụ thể, Stack là một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last In - First Out), nghĩa là phần tử được thêm vào cuối cùng sẽ là phần tử được lấy ra đầu tiên. Hãy tưởng tượng một chồng đĩa, bạn chỉ có thể đặt thêm một chiếc đĩa lên trên cùng và chỉ có thể lấy chiếc đĩa trên cùng ra. Nguyên tắc này làm cho Stack trở nên lý tưởng cho các bài toán yêu cầu xử lý theo thứ tự ngược lại, chẳng hạn như quản lý lời gọi hàm (call stack) trong lập trình hoặc tính năng hoàn tác (undo). Ngược lại, Queue (hàng đợi) hoạt động theo nguyên tắc FIFO (First In - First Out), tương tự như một hàng người xếp hàng mua vé. Người đến trước sẽ được phục vụ trước. Việc nắm vững khái niệm, các thao tác cơ bản và phương pháp cài đặt của Stack và Queue là yêu cầu bắt buộc để giải quyết nhiều vấn-đề phức tạp trong lập trình thi đấu và phát triển ứng dụng thực tế.
1.1. Khái niệm cơ bản về danh sách tuyến tính Linear List
Danh sách tuyến tính là một tập hợp hữu hạn các phần tử có cùng kiểu dữ liệu, được sắp xếp theo một thứ tự tuần tự. Mỗi phần tử trong danh sách (trừ phần tử đầu tiên) có một phần tử đứng ngay trước nó, và mỗi phần tử (trừ phần tử cuối cùng) có một phần tử đứng ngay sau nó. Tài liệu "Data Structure and Algorithms [CO2003]" phân biệt hai loại danh sách tuyến tính: danh sách chung (General list) và danh sách bị giới hạn (Restricted list). Danh sách chung không có bất kỳ hạn chế nào về các thao tác, cho phép chèn hoặc xóa dữ liệu tại bất kỳ vị trí nào. Trong khi đó, Stack và Queue thuộc loại danh sách bị giới hạn, nơi dữ liệu chỉ có thể được chèn hoặc xóa ở các đầu của danh sách. Sự giới hạn này không phải là một điểm yếu, mà chính là đặc tính tạo nên sức mạnh và tính ứng dụng chuyên biệt của chúng trong các bài toán cụ thể.
1.2. Định nghĩa Stack và nguyên tắc LIFO Last In First Out
Theo định nghĩa từ tài liệu gốc, Stack (ngăn xếp) là một dãy hữu hạn các phần tử cùng kiểu, trong đó mọi thao tác chèn và xóa đều bị giới hạn ở một đầu, được gọi là đỉnh (top) của stack. Đặc tính quan trọng nhất của Stack là nguyên tắc LIFO (Last In - First Out), có nghĩa là "Vào sau - Ra trước". Phần tử được đưa vào Stack gần nhất sẽ là phần tử đầu tiên được lấy ra khỏi Stack. Ví dụ, khi bạn sử dụng trình duyệt web, các trang bạn đã truy cập được lưu vào một Stack. Khi bạn nhấn nút "Back", trang cuối cùng bạn truy cập (phần tử trên cùng của Stack) sẽ được lấy ra và hiển thị. Nguyên tắc LIFO này là chìa khóa cho nhiều thuật toán và cơ chế hệ thống quan trọng.
1.3. Các phép toán cơ bản và mở rộng trên cấu trúc Stack
Một Stack được định nghĩa bởi các phép toán cơ bản. Phép toán Push dùng để thêm một phần tử mới vào đỉnh Stack. Phép toán Pop dùng để loại bỏ phần tử ở đỉnh Stack. Phép toán Top (hoặc Peek) cho phép truy xuất giá trị của phần tử ở đỉnh mà không xóa nó. Ngoài ra, còn có các phép toán mở rộng hữu ích như: isEmpty() để kiểm tra xem Stack có rỗng hay không, isFull() để kiểm tra Stack có đầy không (trong trường hợp cài đặt bằng mảng), getSize() để lấy số lượng phần tử hiện có, và clear() để xóa toàn bộ các phần tử, đưa Stack về trạng thái rỗng. Việc hiểu rõ các thao tác này là bước đầu tiên để có thể cài đặt và sử dụng Stack một cách hiệu quả.
II. Hướng dẫn cài đặt Stack bằng danh sách liên kết Linked List
Một trong những phương pháp phổ biến và linh hoạt để hiện thực hóa cấu trúc dữ liệu Stack là sử dụng danh sách liên kết. Cài đặt Stack bằng danh sách liên kết mang lại ưu điểm lớn về quản lý bộ nhớ động. Không giống như cài đặt bằng mảng yêu cầu xác định kích thước tối đa từ trước, danh sách liên kết cho phép Stack phát triển một cách linh hoạt, chỉ bị giới hạn bởi dung lượng bộ nhớ của hệ thống. Trong phương pháp này, mỗi phần tử của Stack được biểu diễn bằng một nút (node) trong danh sách. Mỗi nút chứa hai thành phần chính: dữ liệu (data) và một con trỏ (next) trỏ đến nút tiếp theo. Đỉnh của Stack (top) chính là con trỏ trỏ đến nút đầu tiên của danh sách liên kết. Khi thực hiện thao tác Push, một nút mới sẽ được tạo ra và chèn vào đầu danh sách, con trỏ top sẽ được cập nhật để trỏ đến nút mới này. Ngược lại, thao tác Pop sẽ xóa nút ở đầu danh sách và cập nhật lại con trỏ top để trỏ đến nút kế tiếp. Cách tiếp cận này giúp các thao tác Push và Pop có độ phức tạp thời gian là O(1), tức là thời gian thực thi không phụ thuộc vào số lượng phần tử trong Stack, đảm bảo hiệu suất cao cho các ứng dụng đòi hỏi tốc độ xử lý nhanh.
2.1. Cấu trúc của một Stack cài đặt bằng danh sách liên kết
Để cài đặt Stack bằng danh sách liên kết, chúng ta cần định nghĩa hai cấu trúc chính. Thứ nhất là cấu trúc Node (nút), bao gồm một trường để lưu dữ liệu (data) và một con trỏ (next) để liên kết đến nút kế tiếp trong Stack. Thứ hai là cấu trúc Stack (hoặc lớp Stack trong C++), chứa một con trỏ top luôn trỏ đến nút trên cùng của ngăn xếp và một biến count để theo dõi số lượng phần tử hiện có. Khi Stack rỗng, con trỏ top sẽ có giá trị NULL. Như được mô tả trong tài liệu: stack.top là con trỏ nút và stack.count là một số nguyên. Cách tổ chức này giúp quản lý trạng thái của Stack một cách đơn giản và hiệu quả.
2.2. Chi tiết thuật toán Push và Pop cho Linked Stack
Thao tác Push (thêm phần tử) vào một Linked Stack bao gồm các bước: (1) Cấp phát bộ nhớ cho một nút mới (pNew). (2) Gán dữ liệu cần thêm vào trường data của nút mới. (3) Cho con trỏ next của nút mới trỏ đến nút mà top đang trỏ tới (pNew->next = top). (4) Cập nhật con trỏ top để trỏ đến nút mới (top = pNew). (5) Tăng biến đếm count. Thao tác Pop (lấy phần tử) thực hiện ngược lại: (1) Kiểm tra Stack có rỗng không. Nếu không, (2) Tạo một con trỏ tạm (dltPtr) trỏ đến top. (3) Trả về dữ liệu của nút top. (4) Cập nhật top để trỏ đến nút tiếp theo (top = top->next). (5) Giảm biến đếm count. (6) Giải phóng bộ nhớ của nút đã xóa (delete dltPtr). Cả hai thuật toán này đều có độ phức tạp O(1).
2.3. Các thao tác phụ trợ Top IsEmpty và GetSize
Ngoài Push và Pop, các thao tác phụ trợ cũng rất quan trọng. Thao tác GetStackTop (hay Top) cho phép xem dữ liệu của phần tử trên đỉnh mà không xóa nó. Thuật toán rất đơn giản: kiểm tra Stack có rỗng không, nếu không thì trả về giá trị top->data. Thao tác IsEmpty kiểm tra xem Stack có rỗng không bằng cách so sánh biến count với 0 hoặc kiểm tra top == NULL. Thao tác GetSize chỉ đơn giản là trả về giá trị của biến count. Các hàm này đều có độ phức tạp O(1) và là nền tảng để xây dựng các logic phức tạp hơn sử dụng cấu trúc dữ liệu Stack.
III. Phương pháp cài đặt Stack bằng mảng Array based hiệu quả
Cài đặt Stack bằng mảng là một cách tiếp cận khác, đơn giản và hiệu quả về mặt truy cập bộ nhớ. Thay vì sử dụng các nút và con trỏ, phương pháp này dùng một mảng tĩnh hoặc động để lưu trữ các phần tử của Stack. Một biến số nguyên, thường được đặt tên là top, được sử dụng để theo dõi chỉ số của phần tử trên cùng trong mảng. Khi Stack rỗng, top thường được khởi tạo với giá trị -1. Thao tác Push sẽ tăng top lên 1 rồi gán giá trị mới vào vị trí storage[top]. Thao tác Pop sẽ lấy giá trị tại storage[top] rồi giảm top đi 1. Ưu điểm của phương pháp này là tốc độ truy cập phần tử nhanh do tính chất truy cập tuần tự của bộ nhớ mảng, và việc cài đặt cũng trực quan hơn so với danh sách liên kết. Tuy nhiên, nhược điểm lớn nhất của nó là kích thước cố định. Nếu số lượng phần tử vượt quá sức chứa của mảng, sẽ xảy ra lỗi tràn Stack (Stack Overflow). Ngược lại, nếu khai báo mảng quá lớn mà chỉ sử dụng ít, sẽ gây lãng phí bộ nhớ. Do đó, việc lựa chọn cài đặt Stack bằng mảng hay danh sách liên kết phụ thuộc vào yêu cầu cụ thể của bài toán: liệu kích thước tối đa của Stack có thể được xác định trước hay không.
3.1. Vai trò của biến top và capacity trong Array based Stack
Trong cài đặt Stack bằng mảng, hai biến quan trọng là top và capacity. Biến capacity xác định sức chứa tối đa của Stack, tức là kích thước của mảng được cấp phát. Biến top là một chỉ số (index) trỏ đến phần tử trên cùng của Stack. Theo quy ước trong tài liệu [CO2003], khi Stack rỗng, top có giá trị -1. Mỗi khi một phần tử được Push vào, top sẽ được tăng lên. Khi một phần tử được Pop ra, top sẽ được giảm xuống. Do đó, Stack được coi là đầy khi top == capacity - 1 và rỗng khi top == -1. Việc quản lý chính xác biến top là chìa khóa để đảm bảo các thao tác trên Stack hoạt động đúng đắn.
3.2. Thuật toán Push và Pop với mảng Ưu và nhược điểm
Thuật toán Push trong Array-based Stack kiểm tra xem Stack đã đầy chưa (top == capacity - 1). Nếu chưa, nó tăng top lên 1 và gán giá trị vào storage[top]. Ngược lại, thuật toán Pop kiểm tra xem Stack có rỗng không (top == -1). Nếu không, nó lấy dữ liệu tại storage[top] và giảm top đi 1. Ưu điểm của hai thao tác này là cực kỳ nhanh, với độ phức tạp O(1) và chi phí thấp do truy cập trực tiếp vào bộ nhớ. Nhược điểm chính là rủi ro tràn Stack (Stack Overflow) khi cố gắng Push vào một Stack đã đầy, hoặc lỗi truy cập không hợp lệ (Stack Underflow) khi Pop từ một Stack rỗng. Các lỗi này cần được xử lý cẩn thận trong quá trình lập trình.
IV. Top 3 ứng dụng thực tiễn của cấu trúc dữ liệu Stack phổ biến
Sức mạnh của cấu trúc dữ liệu và thuật toán nằm ở khả năng giải quyết các vấn đề thực tế, và Stack là một minh chứng rõ ràng. Mặc dù có cấu trúc đơn giản với các thao tác bị giới hạn, Stack lại là nền tảng cho nhiều cơ chế quan trọng trong khoa học máy tính. Nguyên tắc LIFO của nó đặc biệt hữu ích cho các tác vụ đòi hỏi phải xử lý hoặc quay lui theo thứ tự ngược lại. Một trong những ứng dụng kinh điển nhất là quản lý lời gọi hàm (Function Call Stack). Mỗi khi một hàm được gọi, thông tin về nó (như địa chỉ trả về, các biến cục bộ) được đẩy vào một Stack. Khi hàm kết thúc, thông tin đó được lấy ra để chương trình có thể tiếp tục thực thi từ nơi nó đã tạm dừng. Một ứng dụng phổ biến khác là trong các thuật toán duyệt đồ thị hoặc cây, chẳng hạn như duyệt theo chiều sâu (Depth-First Search - DFS). DFS sử dụng một Stack để lưu trữ các đỉnh cần được khám phá. Ngoài ra, Stack còn được dùng để kiểm tra tính cân bằng của các dấu ngoặc trong một biểu thức, chuyển đổi biểu thức từ trung tố sang hậu tố (Infix to Postfix) và tính toán giá trị của biểu thức hậu tố. Những ứng dụng này cho thấy tầm quan trọng không thể thiếu của Stack trong lập trình.
4.1. Quản lý lời gọi hàm Function Call Stack trong hệ thống
Đây là một trong những ứng dụng nền tảng nhất của Stack. Mỗi luồng (thread) của một chương trình đều có một vùng nhớ riêng gọi là Call Stack. Khi hàm A gọi hàm B, một "stack frame" chứa các thông tin của hàm A (biến cục bộ, tham số, địa chỉ trả về) được đẩy vào Stack. Sau đó, một stack frame mới cho hàm B lại được đẩy lên trên. Khi hàm B thực thi xong, stack frame của nó sẽ được Pop ra, và chương trình quay trở lại thực thi hàm A dựa trên thông tin được lưu trữ. Cơ chế này cũng giải thích tại sao các hàm đệ quy có thể hoạt động và tại sao việc gọi đệ quy quá sâu có thể gây ra lỗi tràn bộ nhớ Stack (Stack Overflow).
4.2. Đánh giá biểu thức và chuyển đổi trung tố hậu tố
Trong biên dịch và xử lý ngôn ngữ, Stack đóng vai trò trung tâm. Các biểu thức toán học thông thường được viết ở dạng trung tố (ví dụ: (A + B) * C). Để máy tính có thể tính toán hiệu quả, biểu thức này thường được chuyển đổi sang dạng hậu tố (Postfix, ví dụ: A B + C *). Thuật toán chuyển đổi này sử dụng một Stack để tạm thời lưu trữ các toán tử. Sau khi có biểu thức hậu tố, một Stack khác lại được sử dụng để tính toán giá trị cuối cùng. Đây là một ví dụ điển hình về cách cấu trúc dữ liệu và thuật toán phối hợp để giải quyết một bài toán phức tạp.
4.3. Chức năng hoàn tác Undo Redo trong các ứng dụng
Hầu hết các phần mềm hiện đại như trình soạn thảo văn bản hay công cụ thiết kế đồ họa đều có chức năng Undo/Redo. Chức năng này thường được cài đặt bằng cách sử dụng hai Stack. Một Stack undoStack lưu trữ các hành động đã thực hiện. Khi người dùng nhấn Undo, hành động trên cùng của undoStack được Pop ra, đảo ngược và đẩy vào một redoStack. Khi người dùng nhấn Redo, hành động trên cùng của redoStack được Pop ra, thực hiện lại và đẩy ngược trở lại undoStack. Nguyên tắc LIFO của Stack đảm bảo rằng các hành động được hoàn tác và làm lại theo đúng thứ tự thời gian ngược.
V. Kết luận So sánh và lựa chọn phương pháp cài đặt Stack tối ưu
Việc nắm vững cấu trúc dữ liệu Stack là một kỹ năng thiết yếu đối với bất kỳ lập trình viên nào. Qua phân tích, hai phương pháp cài đặt chính là sử dụng mảng và danh sách liên kết đều có những ưu và nhược điểm riêng. Cài đặt Stack bằng mảng nổi bật với sự đơn giản, hiệu suất truy cập bộ nhớ cao và chi phí thấp cho mỗi thao tác. Tuy nhiên, nó đòi hỏi phải biết trước kích thước tối đa và có nguy cơ bị tràn nếu không quản lý tốt. Ngược lại, cài đặt Stack bằng danh sách liên kết cung cấp sự linh hoạt tuyệt vời về kích thước, loại bỏ hoàn toàn nguy cơ tràn Stack do giới hạn dung lượng. Mặc dù vậy, nó có chi phí bộ nhớ cao hơn một chút do phải lưu trữ thêm con trỏ và có thể chậm hơn một chút do cấp phát bộ nhớ động. Sự lựa chọn giữa hai phương pháp này không có câu trả lời tuyệt đối mà phụ thuộc vào bối cảnh của bài toán. Nếu kích thước tối đa của Stack có thể dự đoán được và hiệu suất là ưu tiên hàng đầu, cài đặt bằng mảng là lựa chọn tốt. Nếu kích thước Stack không thể xác định trước và sự linh hoạt là quan trọng hơn, danh sách liên kết sẽ là phương án phù hợp. Hiểu rõ bản chất của cấu trúc dữ liệu và thuật toán giúp chúng ta đưa ra quyết định thiết kế sáng suốt, xây dựng các hệ thống mạnh mẽ và hiệu quả.
5.1. Phân tích độ phức tạp thuật toán của các phương pháp
Về mặt độ phức tạp thời gian (Big-O notation), cả hai phương pháp cài đặt Stack bằng mảng và danh sách liên kết đều cho hiệu suất xuất sắc. Các thao tác cốt lõi như Push, Pop, và Top đều có độ phức tạp là O(1) trong trường hợp trung bình và tốt nhất. Điều này có nghĩa là thời gian thực thi các thao tác này không đổi và không phụ thuộc vào số lượng phần tử hiện có trong Stack. Đây là một đặc tính hiệu suất quan trọng làm cho Stack trở thành một lựa chọn hấp dẫn cho nhiều ứng dụng thời gian thực. Sự khác biệt về hiệu suất trong thực tế thường đến từ các yếu tố cấp thấp hơn như cache locality (mảng tốt hơn) và chi phí cấp phát bộ nhớ (danh sách liên kết tốn kém hơn).
5.2. Khi nào nên dùng Array based và khi nào dùng Linked list
Lựa chọn phương pháp cài đặt Stack tối ưu phụ thuộc vào yêu cầu của bài toán. Nên sử dụng cài đặt bằng mảng khi: (1) Kích thước tối đa của Stack là cố định và có thể biết trước. (2) Hiệu suất và việc sử dụng bộ nhớ hiệu quả là ưu tiên hàng đầu (ví dụ trong lập trình nhúng hoặc các hệ thống có tài nguyên hạn chế). (3) Tính đơn giản trong cài đặt được đề cao. Ngược lại, nên sử dụng cài đặt bằng danh sách liên kết khi: (1) Kích thước của Stack thay đổi liên tục và không thể dự đoán trước. (2) Cần tránh hoàn toàn nguy cơ Stack Overflow do giới hạn kích thước. (3) Bài toán yêu cầu sự linh hoạt tối đa trong quản lý bộ nhớ.
