Tổng quan về giáo trình

Giáo trình bài giảng "Stacks and Queues" (Chương 6) là học liệu chuyên môn thuộc học phần Cấu trúc Dữ liệu và Giải thuật (Data Structures and Algorithms - DSA), do TS. Nguyễn Hồ Mẫn Răng biên soạn và giảng dạy tại Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách khoa – Đại học Quốc gia TP.HCM (Faculty of Computer Science and Engineering, University of Technology, VNU-HCM). Trong chương trình đào tạo kỹ sư và cử nhân ngành Khoa học Máy tính, Kỹ thuật Máy tính và Công nghệ Thông tin, học phần này giữ vai trò là khối kiến thức cơ sở ngành bắt buộc, định hình nền tảng tư duy cấu trúc hóa dữ liệu và kỹ năng tối ưu hóa giải thuật trước khi sinh viên tiếp cận các môn học chuyên sâu về hệ thống phần mềm, cơ sở dữ liệu và trí tuệ nhân tạo.

Nội dung bài giảng được thiết kế bám sát hệ thống chuẩn đầu ra môn học (Learning Outcomes), bao gồm sáu mục tiêu chính:

  • L.1: Mô tả và phân biệt các khái niệm cấu trúc dữ liệu tuyến tính, bao gồm danh sách mảng (array list), danh sách liên kết đơn, đôi, đa liên kết (single, double, multiple links), ngăn xếp (stack), hàng đợi (queue) và hàng đợi vòng (circular queue).
  • L.2: Đặc tả các cấu trúc lưu trữ và giải thuật bằng mã giả (pseudocode); phân tích độ phức tạp tính toán thông qua ký hiệu toán học Big-O đối với các cấu trúc điều khiển cơ bản (tuần tự, rẽ nhánh, lặp).
  • L.3: Liệt kê và đặc tả chi tiết các phương thức thao tác cần thiết trên danh sách, stack và queue bằng mã giả có kèm tiền điều kiện (Pre) và hậu điều kiện (Post).
  • L.4: Cài đặt hoàn chỉnh các cấu trúc dữ liệu và giải thuật bằng ngôn ngữ lập trình C/C++; xây dựng các giải thuật đệ quy cho danh sách, cây, heap, tìm kiếm và đồ thị.
  • L.5: Vận dụng stack và queue để giải quyết các bài toán kỹ thuật thực tế; đưa ra quyết định lựa chọn mô hình cài đặt tối ưu (danh sách liên kết so với mảng tĩnh/động).
  • L.6: Phân tích độ phức tạp thời gian và không gian; phát triển chương trình thực nghiệm nhằm đo lường và đánh giá hiệu năng thực tế của từng phương thức.

Cấu trúc bài giảng triển khai theo tiến trình sư phạm chặt chẽ: bắt đầu từ việc phân loại các cấu trúc danh sách tuyến tính tổng quát và hạn chế, định nghĩa mô hình toán học của cấu trúc dữ liệu trừu tượng (ADT), phân tích trực quan luồng biến đổi dữ liệu, quy chuẩn hóa thao tác dưới dạng mã giả, và hoàn thiện bằng mã nguồn C++ hướng đối tượng sử dụng mẫu khuôn hình (Template). Điểm đặc sắc của tài liệu là tính chuẩn xác về mặt học thuật, cân bằng giữa lý thuyết giải thuật và kỹ thuật lập trình bộ nhớ cấp thấp trong C++.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Tài liệu Chương 6 tập trung vào các chủ đề then chốt với cấu trúc tiến trình logic:

[Khái niệm Danh sách Tuyến tính: General List vs. Restricted List]
                              │
       ┌──────────────────────┴──────────────────────┐
       ▼                                             ▼
[Ngăn xếp - Stacks]                         [Hàng đợi - Queues]
 ├─ Định nghĩa & Cơ chế LIFO                  ├─ Định nghĩa & Cơ chế FIFO
 ├─ Thao tác cơ bản & mở rộng                 ├─ Thao tác cơ bản & mở rộng
 ├─ Cài đặt bằng Danh sách liên kết            ├─ Cài đặt bằng Danh sách liên kết
 ├─ Cài đặt bằng Mảng (ArrayStack)            ├─ Cài đặt bằng Mảng & Hàng đợi vòng
 └─ Ứng dụng thực tế                          └─ Ứng dụng thực tế
  1. Khái niệm danh sách tuyến tính (Linear List Concepts - Mục 6.5 & 6.6):
    • Danh sách tổng quát (General list): Cấu trúc không có ràng buộc về vị trí thêm, xóa hoặc truy cập dữ liệu.
    • Danh sách hạn chế (Restricted list): Cấu trúc giới hạn các thao tác cho phép; việc chèn và xóa dữ liệu chỉ được thực hiện tại các đầu mút xác định của danh sách.
  2. Ngăn xếp và cơ chế hoạt động (Stack Definition - Mục 6.7):
    • Ngăn xếp chứa các phần tử kiểu dữ liệu $T$ là một chuỗi có thứ tự hữu hạn, trong đó mọi thao tác chèn và xóa đều bị giới hạn tại một đầu duy nhất gọi là đỉnh (top).
    • Cơ chế hoạt động: Vào sau – Ra trước (Last In – First Out, LIFO). Phần tử được đưa vào ngăn xếp cuối cùng sẽ là phần tử đầu tiên được lấy ra.
  3. Các thao tác trên Stack (Basic & Extended Operations - Mục 6.8 & 6.9):
    • Nhóm thao tác cơ bản: Khởi tạo ngăn xếp rỗng (createStack), thêm phần tử vào đỉnh (Push), loại bỏ phần tử ở đỉnh (Pop), truy xuất giá trị phần tử ở đỉnh mà không xóa (Top / GetStackTop).
    • Nhóm thao tác mở rộng: Kiểm tra trạng thái rỗng (IsEmpty), kiểm tra trạng thái đầy (IsFull), xác định kích thước hiện tại (GetSize), giải phóng toàn bộ dữ liệu (Clear / destroyStack), in nội dung (Print2Console), sao chép ngăn xếp (Clone).
  4. Cài đặt Stack bằng danh sách liên kết đơn (Linked-List Implementation - Mục 6.17 – 6.44):
    • Xây dựng cấu trúc nút động Node<ItemType> gồm trường dữ liệu data và con trỏ liên kết next.
    • Lớp generic Stack<List_ItemType> quản lý qua con trỏ đỉnh top và biến nguyên count.
    • Thuật toán Push: Cấp phát nút mới pNew, gán pNew->next = top, cập nhật top = pNew và tăng count. Thuật toán áp dụng thống nhất cho cả ngăn xếp đang có phần tử lẫn ngăn xếp rỗng.
    • Thuật toán Pop: Kiểm tra điều kiện rỗng; trỏ con trỏ tạm dltPtr = top, lấy giá trị dataOut, cập nhật top = top->next, giảm count và thu hồi bộ nhớ qua delete dltPtr.
    • Thuật toán Clear: Duyệt vòng lặp while (top != NULL), tuần tự xóa từng nút trên heap và đặt lại count = 0.
  5. Cài đặt Stack bằng mảng động (Array-based Implementation - Mục 6.45 – 6.50):
    • Lớp ArrayStack quản lý qua ba thuộc tính: mảng con trỏ động int *storage, sức chứa capacity và chỉ số đỉnh top (khởi tạo giá trị -1 khi ngăn xếp rỗng).
    • Thao tác push(int value): Kiểm tra điều kiện tràn (top == capacity - 1), nếu tràn ném ngoại lệ chuỗi "Stack is overflow"; ngược lại tăng top++ và gán storage[top] = value.
    • Thao tác pop(int &dataOut): Kiểm tra điều kiện rỗng (top == -1), nếu rỗng ném ngoại lệ "Stack is empty"; ngược lại trích xuất giá trị storage[top] và giảm top--.
    • Các phương thức phụ trợ: getTop() kiểm tra rỗng và trả về storage[top]; isEmpty() trả về top == -1; isFull() trả về top == capacity - 1; getSize() trả về top + 1.
  6. Hàng đợi và mô hình cài đặt (Queues Implementation & Circular Queue):
    • Cơ chế Vào trước – Ra trước (First In – First Out, FIFO). Thao tác chèn tại đuôi (rear) và xóa tại đầu (front).
    • Cài đặt bằng danh sách liên kết và mảng động, mở rộng sang giải thuật hàng đợi vòng (Circular Queue) để khắc phục hiện tượng tràn ảo của mảng tuyến tính.
  7. Ứng dụng thực tế của Stack và Queue (Applications - Mục 6.3):
    • Ứng dụng của Stack: Đảo ngược chuỗi dữ liệu, kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức, chuyển đổi biểu thức trung tố (infix) sang hậu tố (postfix), tính toán giá trị biểu thức hậu tố, quản lý ngăn xếp hàm gọi (call stack) và khử đệ quy.
    • Ứng dụng của Queue: Điều phối hàng đợi tác vụ trong hệ điều hành, lập lịch CPU, đệm dữ liệu truyền thông (buffering), và giải thuật duyệt đồ thị theo chiều rộng (Breadth-First Search - BFS).

Kiến thức nền tảng được xây dựng

  • Lý thuyết Cấu trúc dữ liệu trừu tượng (ADT): Phân tách ranh giới giữa giao diện chức năng bên ngoài (public interface) và cơ chế lưu trữ thực thi bên trong (private implementation details).
  • Nguyên lý quản lý bộ nhớ trong C++: Phân biệt cơ chế cấp phát bộ nhớ liên tục (mảng động) và bộ nhớ phân tán theo nút (con trỏ trên heap); nhận thức về chi phí quản lý overhead của con trỏ và nguy cơ rò rỉ bộ nhớ (memory leak).
  • Phân tích tiệm cận (Asymptotic Analysis): Xác định chi phí tính toán $O(1)$ cho các thao tác Push, Pop, Top, Enqueue, Dequeue trong điều kiện tối ưu và $O(n)$ cho các thao tác hủy toàn bộ hoặc duyệt in dữ liệu.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt thành thạo kỹ thuật Template trong C++ (template <class ItemType>), làm chủ thao tác con trỏ (pointer manipulation), cấp phát và giải phóng vùng nhớ động (new/delete), xây dựng cấu trúc lớp bao đóng (encapsulation), và xử lý biệt lệ ngoại lệ (try-catch-throw).
  • Kỹ năng phân tích (Analytical skills): Khả năng so sánh đối chiếu ưu - nhược điểm giữa hai phương án cài đặt: mảng (tốc độ truy cập nhanh, không tốn chi phí con trỏ nhưng giới hạn kích thước cố định hoặc tốn chi phí tái cấp phát) và danh sách liên kết (kích thước linh hoạt không giới hạn nhưng tiêu tốn thêm bộ nhớ cho trường liên kết next).
  • Kỹ năng ứng dụng (Practical competencies): Khả năng chuyển đổi từ mô tả hình học hoặc mã giả logic sang mã nguồn C++ có thể biên dịch, xử lý chính xác các trường hợp biên (edge cases) như stack rỗng, stack đầy hoặc bộ nhớ hệ thống bị tràn.

Phương pháp giảng dạy và học tập

Giáo trình triển khai phương pháp tiếp cận sư phạm bốn bước chuẩn hóa:

[1. Khái niệm & Mô hình ADT]
            │
            ▼
[2. Minh họa Trạng thái (Visual Diagrams)]
            │
            ▼
[3. Đặc tả Mã giả (Pseudocode Pre/Post)]
            │
            ▼
[4. Hiện thực Mã nguồn C++ (OOP & Template)]
  • Tiếp cận trực quan hóa (Visual Diagrams): Tài liệu cung cấp các hình vẽ mô tả rõ trạng thái ngăn xếp trước và sau khi thực hiện thao tác (Hình 6.10: Successful Push; Hình 6.11: Unsuccessful Push; Hình 6.12: Successful Pop; Hình 6.13: Unsuccessful Pop; Hình 6.14: Successful Top). Cách biểu diễn này giúp sinh viên quan sát được sự dịch chuyển của con trỏ top và việc thay đổi số lượng phần tử count.
  • Đặc tả thuật toán chuẩn mực: Mọi giải thuật đều được mô tả bằng khối mã giả có cấu trúc rõ ràng, quy định cụ thể tham chiếu (ref stack <metadata>), tham trị (val data), tiền điều kiện (Pre) và hậu điều kiện (Post), giúp rèn luyện tư duy thiết kế giải thuật độc lập với ngôn ngữ lập trình.
  • Thực hành lập trình mã nguồn mở rộng: Cung cấp mã nguồn hoàn chỉnh có thể biên dịch trực tiếp, bao gồm hàm kiểm thử main() (Slide 6.44) minh họa quy trình khởi tạo đối tượng Stack<int>, nạp các giá trị số nguyên (7, 9, 10, 8), xuất kết quả ra màn hình thông qua Print2Console(), rút phần tử bằng Pop(val) và giải phóng bộ nhớ.
  • Phương pháp đánh giá năng lực:
    • Đánh giá lý thuyết: Khả năng viết mã giả và giải thích hoạt động của con trỏ.
    • Đánh giá giải thuật: Phân tích độ phức tạp thời gian/không gian bằng ký hiệu Big-O theo chuẩn đầu ra L.2 và L.6.
    • Đánh giá thực hành: Cài đặt bài tập lớn, xử lý bài toán ứng dụng thực tế (L.5) và đo lường hiệu năng thực nghiệm giữa các giải pháp cài đặt.
  • Hướng dẫn tự học: Sinh viên được khuyến nghị vẽ lại sơ đồ biến đổi liên kết con trỏ trên giấy trước khi viết mã; tự cài đặt các phương thức mở rộng như Clone(), IsFull(), và chuyển đổi cấu trúc ngăn xếp sang cấu trúc hàng đợi vòng (Circular Queue).

Điểm nổi bật và cập nhật

  • Thiết kế theo chuẩn kiểm định quốc tế: Bài giảng được cấu trúc chặt chẽ theo các chuẩn đầu ra (Learning Outcomes) rõ ràng, đáp ứng các tiêu chuẩn kiểm định chất lượng giáo dục kỹ thuật (như ABET hoặc AUN-QA) của Trường Đại học Bách khoa – ĐHQG TP.HCM.
  • Tích hợp kỹ thuật lập trình C++ hiện đại: Sử dụng mô hình mẫu biểu mẫu (Generic Template Class), cho phép cấu trúc ngăn xếp có thể lưu trữ dữ liệu của bất kỳ kiểu nào (int, float, string, hoặc cấu trúc do người dùng tự định nghĩa) thay vì chỉ cố định một kiểu dữ liệu đơn lẻ.
  • Kỹ thuật quản lý bộ nhớ an toàn:
    • Đối với mô hình danh sách liên kết: Hiện thực hàm IsFull() (Slide 6.42) bằng cách thử nghiệm cấp phát bộ nhớ động (new Node), sau đó lập tức giải phóng (delete) và trả về kết quả kiểm tra, phản ánh chính xác tình trạng tài nguyên hệ thống.
    • Đối với mô hình mảng: Ứng dụng cơ chế xử lý ngoại lệ bằng throw string (Slide 6.47, 6.48), giúp chương trình phát hiện và xử lý an toàn các lỗi tràn bộ đệm (overflow) hoặc truy cập dữ liệu không hợp lệ (underflow).
  • Tính liên kết hệ thống: Cấu trúc kiến thức của Chương 6 đóng vai trò cầu nối, chuẩn bị các khối kiến thức nền tảng để sinh viên tiếp cận các chương tiếp theo trong chương trình môn học DSA như cây nhị phân (Binary Tree), đống (Heap), giải thuật tìm kiếm, và cấu trúc đồ thị (Graph) thông qua chuẩn đầu ra L.4.

Đối tượng sử dụng giáo trình

  • Sinh viên mục tiêu:
    • Sinh viên năm thứ nhất và năm thứ hai thuộc các ngành Khoa học Máy tính, Kỹ thuật Máy tính, Kỹ thuật Phần mềm, Hệ thống Thông tin và Công nghệ Thông tin.
    • Học viên các chương trình chuyển đổi văn bằng hoặc sau đại học cần củng cố kiến thức nền tảng về cấu trúc dữ liệu và giải thuật.
  • Kiến thức tiên quyết (Prerequisites):
    • Sinh viên cần hoàn thành các học phần Nhập môn Lập trình và Kỹ thuật Lập trình (C/C++).
    • Nắm vững kiến thức về cú pháp C/C++, con trỏ, cấp phát bộ nhớ động (new/delete), cấu trúc struct và các khái niệm cơ bản của lập trình hướng đối tượng (class, phương thức khởi tạo, phương thức hủy).
    • Kiến thức toán rời rạc cơ bản về tập hợp, chuỗi và logic mệnh đề.
  • Đối với giảng viên: Tài liệu cung cấp khung bài giảng chuẩn, hệ thống mã giả định dạng chuẩn mực và mã nguồn C++ mẫu, thuận tiện cho việc thiết kế slide giảng dạy, đề thi lý thuyết và các bài thực hành phòng lab.
  • Đối với người tự học và tra cứu: Tài liệu là nguồn tham khảo kỹ thuật chuẩn xác về cách tổ chức con trỏ, giải quyết bài toán rò rỉ bộ nhớ và phân tích độ phức tạp thuật toán.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được biên soạn phục vụ trực tiếp cho sinh viên đại học đang theo học môn Cấu trúc Dữ liệu và Giải thuật tại các trường đại học kỹ thuật, cũng như kỹ sư phần mềm cần củng cố lại nền tảng giải thuật và kỹ năng quản lý bộ nhớ trong C++.

2. Cần kiến thức nền nào để học?

Người học cần nắm chắc ngôn ngữ lập trình C/C++, đặc biệt là các phần: thao tác con trỏ, cấp phát bộ nhớ động trên heap, lập trình hướng đối tượng cơ bản (class, constructor, destructor) và mẫu khuôn hình (Template).

3. Điểm khác biệt của giáo trình này so với các tài liệu khác là gì?

Tài liệu tích hợp song song ba cấp độ biểu diễn cho cùng một cấu trúc dữ liệu: mô hình khái niệm trừu tượng (ADT), giải thuật mã giả có tiền/hậu điều kiện chuẩn mực, và mã nguồn C++ hoàn chỉnh với cơ chế quản lý ngoại lệ và Template.

4. Làm sao để tự học nội dung này hiệu quả?

Người học nên học tuần tự theo bốn bước: (1) Đọc hiểu định nghĩa và cơ chế LIFO/FIFO; (2) Tự vẽ lại sơ đồ trạng thái con trỏ khi thêm/xóa phần tử; (3) Viết thuật toán bằng mã giả; (4) Tự hiện thực lại toàn bộ mã nguồn C++ mà không nhìn code mẫu, sau đó chạy thử nghiệm trong hàm main().

5. Có tài liệu bổ trợ nào kèm theo không?

Chương 6 nằm trong chuỗi bài giảng đầy đủ của môn học Cấu trúc Dữ liệu và Giải thuật (DSA) do TS. Nguyễn Hồ Mẫn Răng biên soạn, được bổ trợ bởi các chương trước về Danh sách tuyến tính và các chương tiếp theo về Cây (Tree), Đống (Heap), Giải thuật Tìm kiếm, Đồ thị (Graph) cùng hệ thống bài tập thực hành lập trình C++.

Kết luận

Bài giảng "Stacks and Queues" (Chương 6) trong giáo trình Cấu trúc Dữ liệu và Giải thuật của TS. Nguyễn Hồ Mẫn Răng (Đại học Bách khoa – ĐHQG TP.HCM) cung cấp nền tảng lý thuyết và kỹ năng thực hành hoàn chỉnh về hai cấu trúc dữ liệu tuyến tính hạn chế cơ bản là Ngăn xếp (Stack) và Hàng đợi (Queue). Việc phân tích chi tiết hai phương thức cài đặt bằng Danh sách liên kết và Mảng động giúp người học hiểu rõ bản chất quản lý bộ nhớ, kiểm soát con trỏ và tối ưu hóa hiệu năng tính toán.

Lộ trình học tập đề xuất cho sinh viên là hoàn thiện việc cài đặt các thao tác cơ bản và mở rộng của Stack/Queue, phân tích độ phức tạp Big-O, trước khi ứng dụng các cấu trúc này vào việc xây dựng giải thuật khử đệ quy, xử lý biểu thức và duyệt cấu trúc dữ liệu phi tuyến tính nâng cao.