Bài giảng Cấu trúc dữ liệu và giải thuật: Ngăn xếp, hàng đợi - Nguyễn Mạnh Hiển (HK2, năm học 2025–2026)

Trong lĩnh vực khoa học máy tính, việc hiểu rõ các cấu trúc dữ liệu là nền tảng thiết yếu để xây dựng các giải thuật hiệu quả. Trong số đó, ngăn xếp và hàng đợi là hai cấu trúc cơ bản nhưng vô cùng mạnh mẽ, đóng vai trò quan trọng trong việc tổ chức và quản lý dữ liệu. Bài giảng này sẽ giới thiệu tổng quan về tầm quan trọng của chúng trong lập trình và thiết kế hệ thống. Chúng ta sẽ khám phá cách thức hoạt động của ngăn xếp theo nguyên tắc LIFO và xem xét các phương pháp cài đặt cũng như ứng dụng thực tế của chúng, đặt nền móng vững chắc cho việc tiếp cận các vấn đề phức tạp hơn trong cấu trúc dữ liệu.

Sinh viên ngành Công nghệ thông tin, Kỹ thuật phần mềm, hoặc bất kỳ ai đang học môn Cấu trúc dữ liệu và giải thuật.

Bài giảng này cung cấp một cái nhìn chi tiết về ngăn xếp (Stack) và giới thiệu sơ lược về hàng đợi (Queue), hai trong số những cấu trúc dữ liệu cơ bản nhất. Đối với ngăn xếp, chúng ta sẽ đi sâu vào nguyên tắc hoạt động cốt lõi của nó là LIFO (Last-In, First-Out), nơi phần tử được thêm vào cuối cùng sẽ được lấy ra đầu tiên. Các thao tác chính của ngăn xếp, bao gồm push (thêm phần tử vào đỉnh), pop (xóa phần tử từ đỉnh), và top (truy xuất phần tử ở đỉnh), đều được trình bày rõ ràng, nhấn mạnh rằng chúng có độ phức tạp thời gian là O(1) – cực kỳ hiệu quả. Về phương pháp cài đặt, bài giảng đề xuất hai cách tiếp cận phổ biến: sử dụng danh sách liên kết và sử dụng mảng. Mỗi phương pháp đều có ưu và nhược điểm riêng, và việc hiểu rõ chúng giúp lập trình viên lựa chọn giải pháp tối ưu cho từng trường hợp cụ thể. Bên cạnh lý thuyết và cài đặt, phần quan trọng của bài giảng là các ứng dụng của ngăn xếp trong thực tế. Chúng ta sẽ khám phá cách ngăn xếp được sử dụng để cân bằng thẻ HTML, một kỹ thuật then chốt trong việc kiểm tra tính hợp lệ của cú pháp. Ngoài ra, việc định giá biểu thức hậu tố và vai trò của ngăn xếp trong quản lý lời gọi hàm cũng được đề cập, cho thấy tầm quan trọng của cấu trúc này trong nhiều giải thuật và hệ thống phần mềm phức tạp. Mặc dù hàng đợi không được trình bày chi tiết trong tài liệu này, nó được giới thiệu như một đối trọng quan trọng của ngăn xếp, hoạt động theo nguyên tắc FIFO, và cũng có nhiều ứng dụng rộng rãi. Bài giảng giúp sinh viên củng cố kiến thức nền tảng về cấu trúc dữ liệu và chuẩn bị cho việc giải quyết các bài toán phức tạp hơn.