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

Tài liệu học tập "Chapter 5: Stacks and Queues" thuộc học phần Cấu trúc dữ liệu và Giải thuật (Data Structures and Algorithms - DSA) do ThS. Lương Thế Nhân và TS. Trần Giang Sơn biên soạn, phục vụ công tác giảng dạy tại Khoa Khoa học và Kỹ thuật Máy tính (Faculty of Computer Science and Engineering), Trường Đại học Bách khoa – Đại học Quốc gia TP.HCM (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ò nền tảng, cung cấp các nguyên lý tổ chức dữ liệu bộ nhớ và thiết kế giải thuật tối ưu.

Mục tiêu học tập của giáo trình được chuẩn hóa thông qua hệ thống chuẩn đầu ra (Learning Outcomes) từ L.1 đến L.6:

  • L.1: Phác họa và phân biệt các khái niệm về danh sách mảng (array list), danh sách liên kết (linked list bao gồm liên kết đơn, liên kết đôi, đa liên kết), ngăn xếp (stack), hàng đợi (queue) và hàng đợi vòng (circular queue).
  • L.2: Biểu diễn cấu trúc lưu trữ và phân tích thuật toán bằng mã giả (pseudocode); ứng dụng ký hiệu Big-O để đánh giá độ phức tạp tính toán cho các cấu trúc điều khiển cơ bản (tuần tự, rẽ nhánh, vòng lặp).
  • L.3: Liệt kê và mô tả chi tiết các phương thức xử lý cần thiết của danh sách, ngăn xếp và hàng đợi dưới dạng mã giả chuẩn hóa.
  • L.4: Cài đặt hoàn chỉnh các cấu trúc danh sách, ngăn xếp, hàng đợi bằng ngôn ngữ C/C++; xây dựng các cài đặt đệ quy cho danh sách, cây (tree), đống (heap), thuật toán tìm kiếm (searching) và đồ thị (graphs).
  • L.5: Ứng dụng danh sách, ngăn xếp và hàng đợi vào bài toán thực tế; phân tích để lựa chọn cấu trúc lưu trữ phù hợp (danh sách liên kết so với mảng).
  • L.6: Phân tích độ phức tạp và thiết kế chương trình thực nghiệm nhằm đánh giá hiệu năng thực tế của các phương thức được cài đặt.

Giáo trình được cấu trúc khoa học từ lý thuyết mô hình trừu tượng (Abstract Data Types), nguyên lý vận hành logic, thuật toán mã giả đến mã nguồn C++ hoàn chỉnh và các ca kiểm thử biên. Điểm đặc sắc của tài liệu là phương pháp đối chiếu trực tiếp giữa mô hình ý niệm (conceptual model) và mô hình vật lý (physical memory model), kết hợp cơ chế xử lý lỗi hệ thống trong quản lý bộ nhớ.

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

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

Nội dung trọng tâm của tài liệu tập trung vào cấu trúc dữ liệu danh sách tuyến tính có giới hạn (Restricted Linear List) với chủ đề Ngăn xếp (Stack) và Hàng đợi (Queue):

  1. Khái niệm danh sách tuyến tính (Linear List Concepts):

    • General list: Cấu trúc danh sách không áp đặt giới hạn đối với các thao tác truy xuất; dữ liệu có thể được chèn hoặc xóa tại bất kỳ vị trí nào trong danh sách.
    • Restricted list: Cấu trúc danh sách có kiểm soát nghiêm ngặt; các thao tác chèn và xóa chỉ được phép thực hiện tại các vị trí đầu mút (ends) của danh sách.

  2. Cấu trúc dữ liệu Ngăn xếp (Stack Definition):

    • Ngăn xếp chứa các phần tử kiểu $T$ là một chuỗi hữu hạn các phần tử kiểu $T$, trong đó mọi thao tác chèn (insertions) và xóa (deletions) đều bị giới hạn ở một đầu duy nhất gọi là đỉnh (top).
    • Vận hành theo nguyên lý LIFO (Last In - First Out): Phần tử cuối cùng được đưa vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp.

  3. Các thao tác cơ bản và mở rộng trên Stack:

    • Khởi tạo (createStack/Constructor): Thiết lập ngăn xếp rỗng, gán con trỏ đỉnh top = NULL (với danh sách liên kết) hoặc chỉ mục top = -1 (với mảng) và số lượng phần tử count = 0.
    • Thao tác Push: Đưa một phần tử mới lên đỉnh ngăn xếp. Khi bộ nhớ không còn khả năng cấp phát hoặc mảng đầy, hệ thống rơi vào trạng thái tràn ngăn xếp (Stack Overflow).
    • Thao tác Pop: Xóa phần tử tại vị trí đỉnh và trả về giá trị dữ liệu cho bên gọi. Nếu ngăn xếp không có phần tử, hệ thống rơi vào trạng thái cạn ngăn xếp (Stack Underflow).
    • Thao tác Top/GetStackTop/getTop: Truy xuất và đọc giá trị của phần tử tại đỉnh mà không làm thay đổi hay xóa phần tử đó khỏi cấu trúc dữ liệu.
    • Các thao tác bổ trợ: 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 thời (GetSize/getSize), giải phóng toàn bộ ngăn xếp (Clear/destroyStack), sao chép ngăn xếp (Clone), và xuất dữ liệu ra màn hình (Print2Console).

  4. Hiện thực hóa bằng Danh sách liên kết (Linked-list implementation):

    • Cấu trúc nút (Node): Gồm thành phần dữ liệu data (kiểu dữ liệu trừu tượng ItemType) và con trỏ next trỏ tới nút kế tiếp.
    • Cấu trúc quản lý (Stack metadata): Gồm biến nguyên count đếm số phần tử và con trỏ top quản lý nút đỉnh.
    • Cơ chế cập nhật: Thao tác Push cấp phát nút mới pNew, liên kết pNew->next = top, cập nhật top = pNew và tăng count. Thao tác Pop trỏ con trỏ tạm dltPtr = top, chuyển top = top->next, giảm count, giải phóng vùng nhớ delete dltPtr. Cơ chế áp dụng đồng nhất cho cả trường hợp ngăn xếp đã có phần tử và ngăn xếp rỗng.

  5. Hiện thực hóa bằng Mảng (Array-based implementation):

    • Sử dụng mảng động storage = new int[capacity] với kích thước sức chứa xác định và biến số nguyên top lưu chỉ mục của phần tử trên cùng.
    • Trạng thái rỗng được định nghĩa khi top == -1; trạng thái đầy xảy ra khi top == capacity - 1.
    • Thao tác push tăng top lên 1 và gán giá trị vào storage[top]; thao tác pop trích xuất storage[top] và giảm top đi 1; tích hợp cơ chế ném ngoại lệ (throw string()) khi xảy ra Overflow hoặc Underflow.

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: Định nghĩa hình thức về ngăn xếp và hàng đợi độc lập với cấu trúc bộ nhớ vật lý.
  • Nguyên lý quản trị bộ nhớ động và con trỏ: Cơ chế cấp phát (new), hủy thu hồi bộ nhớ (delete/recycle), quản lý con trỏ tránh rò rỉ bộ nhớ (memory leak) trong C++.
  • Phân tích độ phức tạp giải thuật: Ứng dụng ký hiệu Big-O để đánh giá chi phí thời gian $O(1)$ của các thao tác Push, Pop, Top trên cả hai mô hình cài đặt.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Lập trình hướng đối tượng kết hợp C++ Templates (template <class ItemType>, template <class List_ItemType>), viết mã nguồn cấu trúc dữ liệu tổng quát tái sử dụng được cho nhiều kiểu dữ liệu.
  • Kỹ năng phân tích logic: Nhận diện, mô hình hóa và xử lý triệt để các trạng thái biên của cấu trúc dữ liệu (Overflow, Underflow, ngăn xếp rỗng, ngăn xếp có một phần tử).
  • Kỹ năng lập trình hệ thống: Chuyển đổi chính xác từ giải thuật mã giả (với tiền điều kiện Pre và hậu điều kiện Post) sang mã nguồn C++ có kiểm soát lỗi và ngoại lệ.

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

Giáo trình áp dụng phương pháp sư phạm tích hợp đa tầng, kết nối chặt chẽ giữa khái niệm lý thuyết, trực quan hóa giải thuật và thực hành lập trình:

  1. Mô hình trực quan hóa trạng thái: Mỗi thao tác trên ngăn xếp đều được minh họa bằng sơ đồ chuyển đổi trạng thái (Before/After):

    • Minh họa thao tác Push thành công khi tạo nút mới và chuyển dời con trỏ top.
    • Minh họa tình huống Push thất bại do tràn bộ nhớ (Overflow) với trạng thái ngăn xếp không thay đổi.
    • Minh họa thao tác Pop thành công thông qua việc chuyển dịch top và thu hồi dltPtr.
    • Minh họa thao tác Pop thất bại khi ngăn xếp rỗng (Underflow).
    • Minh họa thao tác Top trích xuất dữ liệu mà giữ nguyên cấu trúc ngăn xếp.

  2. Biểu diễn giải thuật bằng mã giả chuẩn tắc: Tất cả các hàm (createStack, pushStack, popStack, stackTop, destroyStack, isEmpty) đều được định nghĩa với cấu trúc hình thức:

    • Pre (Tiền điều kiện): Xác định tính hợp lệ của tham chiếu cấu trúc metadata và dữ liệu đầu vào.
    • Post (Hậu điều kiện): Xác định trạng thái của cấu trúc dữ liệu và giá trị trả về sau khi thực thi.
    • Giá trị trả về (Return): Quy chuẩn trả về true/false hoặc mã trạng thái để phản ánh kết quả thao tác.

  3. Thực hành lập trình và kiểm thử: Tài liệu cung cấp mã nguồn hoàn chỉnh cho hàm thực thi mẫu main() để sinh viên kiểm chứng chuỗi thao tác:

    Stack<int> *myStack = new Stack<int>();
myStack->Push(7);
myStack->Push(9);
myStack->Push(10);
myStack->Push(8);
myStack->Print2Console();
myStack->Pop(val);
myStack->Print2Console();
delete myStack;

    Phương pháp này yêu cầu người học tự xây dựng các ca kiểm thử, in kết quả ra màn hình console và chủ động kiểm tra việc thu hồi bộ nhớ động qua phương thức Clear() và toán tử delete.

Điểm nổi bật và tính học thuật

  • Tính quy chuẩn trong biểu diễn mã giả: Hệ thống mã giả trong giáo trình không viết tùy ý mà tuân thủ định dạng chặt chẽ với các từ khóa cấu trúc (ref stack <metadata>, val data <dataType>, recycle(dltPtr)), giúp sinh viên nắm vững nguyên lý thiết kế giải thuật trước khi phụ thuộc vào cú pháp của một ngôn ngữ lập trình cụ thể.
  • Hiện thực hóa hoàn chỉnh bằng C++ Template: Thay vì dừng lại ở các kiểu dữ liệu nguyên thủy (int, float), bài giảng xây dựng các lớp mẫu Stack<List_ItemType> và cấu trúc nút mẫu Node<ItemType>. Cách tiếp cận này đáp ứng tiêu chuẩn lập trình generic hiện đại trong công nghệ phần mềm.
  • Làm rõ tính tương đương trong thao tác biên: Giáo trình chỉ rõ bản chất kỹ thuật: việc chèn phần tử vào ngăn xếp rỗng không có sự khác biệt về mã lệnh so với việc chèn vào ngăn xếp đã có phần tử (top ban đầu mang giá trị NULL được gán trực tiếp cho pNew->next, tạo thành danh sách liên kết một phần tử). Tương tự, thao tác xóa phần tử duy nhất cũng đưa con trỏ top về lại NULL một cách tự nhiên.
  • Tính hệ thống trong chương trình đào tạo: Nội dung chương 5 được liên kết chặt chẽ với bức tranh tổng thể của học phần DSA: kết nối cấu trúc tuyến tính (List, Stack, Queue) với các cấu trúc dữ liệu phi tuyến (Tree, Heap, Graph) và các kỹ thuật giải thuật nâng cao (Recursion, Searching, Big-O Complexity Analysis).

Bảng so sánh hai mô hình cài đặt Stack

Tiêu chí phân tích Cài đặt bằng Danh sách liên kết (Linked-list) Cài đặt bằng Mảng (Array-based)
Cấu trúc lưu trữ Các nút phân tán (Node) chứa data và con trỏ next Mảng các phần tử liên tục storage[capacity]
Quản lý đỉnh (Top) Con trỏ Node* top trỏ vào nút đầu danh sách Biến chỉ mục số nguyên int top
Giới hạn kích thước Động, chỉ phụ thuộc vào dung lượng bộ nhớ khả dụng Cố định bởi tham số capacity khởi tạo
Nguy cơ lỗi Tràn bộ nhớ hệ thống khi không thể new Node Tràn ngăn xếp (top == capacity - 1)
Chi phí bộ nhớ phụ Tốn thêm bộ nhớ cho trường con trỏ next tại mỗi nút Có thể dư thừa vùng nhớ mảng nếu không dùng hết
Xử lý trạng thái rỗng top == NULL hoặc count == 0 top == -1
Độ phức tạp Push/Pop $O(1)$ $O(1)$

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

  • Sinh viên bậc Đại học: Sinh viên năm thứ nhất và năm thứ hai theo họ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.
  • Điều kiện tiên quyết: Người học cần hoàn thành học phần Nhập môn Lập trình và Lập trình Nâng cao; nắm vững ngôn ngữ C/C++, cấu trúc điều khiển cơ bản (tuần tự, rẽ nhánh, vòng lặp), con trỏ, mảng động và nguyên lý cấp phát/giải phóng bộ nhớ.
  • Giảng viên chuyên ngành: Sử dụng làm đề cương bài giảng chuẩn, tài liệu hướng dẫn thực hành phòng máy và khung tham chiếu để xây dựng đề thi đánh giá chuẩn đầu ra môn Cấu trúc dữ liệu và Giải thuật.
  • Người tự học và nghiên cứu: Tài liệu phục vụ kỹ sư phần mềm muốn ôn tập nền tảng khoa học máy tính, chuẩn bị cho các kỳ đánh giá kỹ thuật hoặc tối ưu hóa thuật toán hệ thống.

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 thiết kế cho sinh viên đại học khối ngành Công nghệ Thông tin, Khoa học Máy tính và Kỹ thuật Máy tính đang học môn Cấu trúc dữ liệu và Giải thuật, cũng như lập trình viên cần củng cố kiến thức nền tảng về tổ chức bộ nhớ.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi học?

Người học cần nắm vững kỹ thuật lập trình C/C++, đặc biệt là con trỏ (pointers), cấp phát bộ nhớ động (new/delete), cấu trúc struct/class, cơ chế mẫu (templates) và các cấu trúc điều khiển cơ bản.

3. Điểm khác biệt cốt lõi giữa hai phương pháp cài đặt Stack là gì?

Cài đặt bằng danh sách liên kết không bị giới hạn cứng về số lượng phần tử nhưng tốn chi phí bộ nhớ cho con trỏ next ở mỗi nút; cài đặt bằng mảng tối ưu về không gian lưu trữ trực tiếp nhưng bị giới hạn bởi capacity cố định và có nguy cơ phát sinh lỗi Stack Overflow khi mảng đầy.

4. Làm thế nào để tự học hiệu quả theo nội dung tài liệu?

Người học nên phân tích sơ đồ chuyển đổi trạng thái, viết lại giải thuật mã giả có kiểm tra điều kiện Pre/Post, sau đó tự hiện thực hóa bằng C++ Template và xây dựng hàm kiểm thử bao phủ toàn bộ các trường hợp biên (ngăn xếp rỗng, ngăn xếp đầy, chèn và xóa liên tiếp).

5. Ngoài Stack và Queue, học phần còn bao gồm những nội dung nào?

Theo chuẩn đầu ra (Outcomes L.1 - L.6), học phần bao quát hệ thống cấu trúc dữ liệu toàn diện gồm: Array list, Linked list (đơn, đôi, đa liên kết), Circular queue, Tree, Heap, các thuật toán tìm kiếm (Searching), Đồ thị (Graphs) và phân tích độ phức tạp Big-O.

Kết luận

Tài liệu Chapter 5: Stacks and Queues của tác giả Lương Thế Nhân và Trần Giang Sơn cung cấp khung kiến thức chuẩn xác và toàn diện về hai cấu trúc dữ liệu danh sách giới hạn cơ bản. Thông qua việc kết hợp giữa lý thuyết hình thức, mã giả chuẩn mực và cài đặt C++ Template chi tiết, tài liệu đáp ứng đầy đủ các yêu cầu học thuật khắt khe của chương trình đào tạo kỹ sư công nghệ thông tin.

Lộ trình học tập đề xuất: Nắm vững khái niệm danh sách tuyến tính và nguyên lý LIFO/FIFO $\rightarrow$ Phân tích thuật toán mã giả và xử lý trạng thái biên $\rightarrow$ Cài đặt và kiểm thử mã nguồn C++ cho cả hai mô hình Danh sách liên kết và Mảng $\rightarrow$ Mở rộng phân tích độ phức tạp Big-O và phát triển các cấu trúc dữ liệu nâng cao (Tree, Heap, Graph).