Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5 - Stack và Queue (CO2003)

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ả. 93 trang.

• Đề tài: Data Structure And Algorithms Cấu Trúc Dữ Liệu Và Thuật Toán Ch05 Stack Queue

Mục lục chi tiết

• 5. CHƯƠNG 5: NGĂN XẾP VÀ HÀNG ĐỢI (STACK VÀ QUEUE)
• 5.1. Các thao tác cơ bản của Stack
• 5.2. Cài đặt Stack
• 5.2.1. Cài đặt bằng danh sách liên kết (Linked-list implementation)
• 5.2.2. Cài đặt bằng mảng (Array-based stack implementation)
• 5.3. Ứng dụng của Stack
• 5.4. Các thao tác cơ bản của Queue
• 5.5. Cài đặt Queue
• 5.6. Ứng dụng của Queue

Tóm tắt

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ớ.

Nội dung chính

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

Tài liệu bài giảng Data Structure and Algorithms (mã môn học: CO2003), cụ thể là Chapter 5: Stack and Queue, được biên soạn bởi TS. Nguyễn Đức Dũng (Duc Dung Nguyen, PhD. - Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa TP.HCM - HCMUT). Môn học Cấu trúc dữ liệu và Giải thuật giữ vị trí nền tảng cốt lõi trong chương trình đào tạo kỹ sư ngành Khoa học Máy tính và Kỹ thuật Máy tính, cung cấp các nguyên lý tổ chức dữ liệu và thiết kế thuật toán xử lý dữ liệu có hiệu năng tối ưu.

Mục tiêu học tập của học phần (Learning Outcomes) được chuẩn hóa từ L.1 đến L.6:

• L.1: Mô tả các khái niệm về danh sách mảng (array list), danh sách liên kết (linked list đơn, đô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ữ bằng mã giả (pseudocode) cho các cấu trúc danh sách, ngăn xếp và hàng đợi.
• L.3: Liệt kê và mô tả bằng mã giả các phương thức thao tác cần thiết trên danh sách, ngăn xếp và hàng đợi.
• L.4: Cài đặt hoàn chỉnh danh sách, ngăn xếp và hàng đợi bằng ngôn ngữ C/C++.
• L.5: Ứng dụng danh sách, ngăn xếp, hàng đợi để giải quyết bài toán thực tế; phân tích và lựa chọn hình thức cài đặt phù hợp (mảng hay danh sách liên kết).
• L.6: Phân tích độ phức tạp thuật toán bằng ký hiệu Big-O, xây dựng chương trình thực nghiệm để đánh giá hiệu năng và triển khai các thuật toán đệ quy trên cấu trúc danh sách, cây (tree), heap, tìm kiếm và đồ thị (graph).

Bài giảng tiếp cận theo trình tự logic chặt chẽ: xuất phát từ lý thuyết phân loại danh sách tuyến tính, trực quan hóa cấu trúc dữ liệu qua sơ đồ hoạt động, mô hình hóa giải thuật bằng mã giả và kết thúc bằng việc hiện thực hóa qua ngôn ngữ C++ với kỹ thuật lập trình mẫu (template).

---

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

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

Tài liệu Chương 5 tập trung vào hai cấu trúc dữ liệu trừu tượng tuyến tính dạng hạn chế (restricted linear lists) với các phân đoạn nội dung chính:

1. Các thao tác cơ bản trên ngăn xếp (Basic operations of Stacks): Phân biệt giữa danh sách tổng quát (General list - không hạn chế vị trí thao tác) và danh sách hạn chế (Restricted list - chỉ thao tác tại các đầu mút). Định nghĩa cấu trúc Stack hoạt động theo nguyên lý LIFO (Last In - First Out).
2. Cài đặt ngăn xếp (Implementation of Stacks): Triển khai ngăn xếp bằng hai phương pháp lưu trữ: danh sách liên kết đơn (Linked-list implementation) và mảng động (Array-based implementation).
3. Ứng dụng của ngăn xếp (Applications of Stack): Khảo sát các bài toán ứng dụng ngăn xếp trong tính toán biểu thức, quản lý bộ nhớ hàm và giải thuật đệ quy.
4. Các thao tác cơ bản trên hàng đợi (Basic operations of Queues): Định nghĩa cấu trúc Queue hoạt động theo nguyên lý FIFO (First In - First Out) và hàng đợi vòng (Circular queue).
5. Cài đặt hàng đợi (Implementation of Queue): Cài đặt cấu trúc lưu trữ và các hàm giao tiếp cho hàng đợi dựa trên mảng và danh sách liên kết.
6. Ứng dụng của hàng đợi (Applications of Queue): Ứng dụng trong điều phối tiến trình, bộ đệm dữ liệu và giải thuật duyệt đồ thị theo chiều rộng (BFS).

Trong toàn bộ chương trình môn học CO2003, nội dung Chương 5 đóng vai trò cầu nối chuyển tiếp từ cấu trúc dữ liệu tuyến tính cơ bản (Array, Linked List) sang các cấu trúc dữ liệu phi tuyến tính phức tạp hơn ở các chương tiếp theo như Cây (Tree), Cây ưu tiên (Heap) và Đồ thị (Graph).

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

• Cơ chế LIFO (Last In - First Out): Phần tử được nạp vào cuối cùng sẽ là phần tử đầu tiên được lấy ra khỏi cấu trúc. Mọi thao tác chèn và xóa đều bị giới hạn tại một vị trí duy nhất gọi là đỉnh ngăn xếp (top).
• Cấu trúc dữ liệu trừu tượng (ADT) của Stack:
  • Thao tác cơ sở: Push (nạp phần tử vào đỉnh), Pop (lấy và loại bỏ phần tử ở đỉnh), Top / GetStackTop (truy xuất giá trị phần tử ở đỉnh mà không thay đổi ngăn xếp).
  • Thao tác mở rộng: IsEmpty (kiểm tra ngăn xếp rỗng), IsFull (kiểm tra ngăn xếp đầy), GetSize (đếm số lượng phần tử hiện có), Clear / destroyStack (hủy toàn bộ phần tử và giải phóng bộ nhớ).
  • Kiểm soát trạng thái lỗi: Lỗi tràn ngăn xếp (Stack Overflow) khi thực hiện Push vào ngăn xếp đã đầy dung lượng; lỗi rỗng ngăn xếp (Stack Underflow) khi thực hiện Pop hoặc Top trên ngăn xếp không chứa phần tử.
• Mô hình tổ chức bộ nhớ:
  • Mô hình liên kết (Linked-list): Lưu trữ động phân tán thông qua cấu trúc nút Node gồm trường data và con trỏ next. Trạng thái ngăn xếp được quản trị thông qua con trỏ đỉnh top và biến đếm kích thước count.
  • Mô hình mảng tuần tự (Array-based): Lưu trữ vùng nhớ liên tục thông qua mảng động storage với chỉ số quản lý top (khởi tạo ở giá trị -1) và giới hạn kích thước tối đa capacity.

Kỹ năng phát triển

• Kỹ năng thiết kế mã giả: Xây dựng giải thuật chuẩn tắc độc lập với ngôn ngữ lập trình, xác định rõ điều kiện tiên quyết (Pre-condition) và kết quả hậu nghiệm (Post-condition) cho từng hàm (createStack, pushStack, popStack, stackTop, destroyStack, isEmpty).
• Kỹ năng lập trình hệ thống bằng C++:
  • Ứng dụng kỹ thuật generic programming thông qua template <class ItemType> để xây dựng cấu trúc dữ liệu tổng quát cho mọi kiểu dữ liệu.
  • Quản lý vòng đời đối tượng và bộ nhớ động thông qua Constructor, Destructor, các toán tử new, delete và delete[].
  • Cài đặt cơ chế kiểm soát ngoại lệ bằng cách phát sinh chuỗi thông báo lỗi (throw string("Stack is overflow"), throw string("Stack is empty")).
• Kỹ năng phân tích hiệu năng: Sử dụng ký hiệu Big-O để đánh giá độ phức tạp thuật toán của các thao tác cơ bản ($O(1)$ cho Push, Pop, Top, IsEmpty trên cả hai mô hình cài đặt).

---

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

Tài liệu áp dụng phương pháp sư phạm đa tầng (multi-tiered pedagogical framework), kết hợp giữa biểu diễn hình học, giải thuật hình thức và triển khai mã nguồn:

1. Khái niệm và cơ chế hoạt động: Phân tích bản chất của cấu trúc tuyến tính hạn chế so với danh sách tổng quát.
2. Trực quan hóa qua sơ đồ trạng thái: Sử dụng các hình vẽ minh họa từng bước dịch chuyển con trỏ và biến đổi cấu trúc:
   • Figure 1 & 2: Trạng thái Push thành công và Push Overflow.
   • Figure 3 & 4: Trạng thái Pop thành công và Pop Underflow.
   • Figure 5 & 6: Trạng thái Top thành công và Top Underflow.
3. Mô hình hóa bằng mã giả chuẩn tắc: Định nghĩa giải thuật với các tham số truyền tham chiếu (ref stack, ref dataOut) hoặc truyền giá trị (val data).
4. Hiện thực hóa mã nguồn C++: Cung cấp cấu trúc lớp hoàn chỉnh (template <class List_ItemType> class Stack và class ArrayStack).
5. Thực thi và đánh giá kết quả: Minh họa qua hàm main() với các thao tác nạp dữ liệu tuần tự (Push(7), Push(9), Push(10), Push(8)), in kiểm tra qua console (Print2Console()), rút trích phần tử (Pop()) và giải phóng đối tượng.

---

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

• Tính tổng quát hóa cao (Generic Programming): Việc ứng dụng mẫu lớp (Class Templates) trong C++ giúp các cấu trúc Node và Stack có khả năng tái sử dụng linh hoạt với nhiều kiểu dữ liệu nguyên thủy hoặc đối tượng phức tạp mà không cần chỉnh sửa mã nguồn cốt lõi.
• So sánh đối chiếu trực tiếp hai kiến trúc lưu trữ:

Tiêu chí so sánh	Cài đặt bằng danh sách liên kết (Stack)	Cài đặt bằng mảng (ArrayStack)
Cơ chế cấp phát	Động từng nút (new Node) khi gọi Push	Khối liên tục cố định theo capacity
Giới hạn dung lượng	Phụ thuộc bộ nhớ khả dụng của hệ thống	Bị giới hạn cứng bởi tham số capacity
Chi phí bộ nhớ phụ	Tốn thêm bộ nhớ cho con trỏ next ở mỗi node	Không tốn con trỏ, nhưng có thể lãng phí mảng chưa dùng hết
Độ phức tạp Push/Pop	$O(1)$	$O(1)$
Hiện tượng tràn dữ liệu	Xảy ra khi hệ thống hết bộ nhớ khả dụng	Xảy ra khi chỉ số top == capacity - 1

• Quản trị an toàn bộ nhớ: Mã nguồn bài giảng cung cấp đầy đủ giải thuật dọn dẹp bộ nhớ trong hàm hủy (~Stack(), ~ArrayStack(), hàm Clear()), duyệt tuần tự từng nút để thu hồi tài nguyên tránh rò rỉ bộ nhớ (memory leaks).

---

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

• Sinh viên đại học: Sinh viên năm thứ 2 chuyên ngành Khoa học Máy tính, Kỹ thuật Máy tính, Hệ thống Thông tin, Kỹ thuật Phần mềm tham gia học phần Cấu trúc dữ liệu và Giải thuật (CO2003).
• Yêu cầu kiến thức tiên quyết (Prerequisites):
  • Nắm vững kiến thức lập trình cơ bản và nâng cao với ngôn ngữ C/C++.
  • Hiểu rõ cơ chế quản lý con trỏ (pointers), địa chỉ vùng nhớ, phân vùng Heap/Stack và cấp phát động (new/delete).
  • Nắm được các cấu trúc điều khiển cơ bản (tuần tự, rẽ nhánh, lặp) và phương pháp đánh giá thời gian chạy bằng ký hiệu hàm toán học.
• Giảng viên và người nghiên cứu: Sử dụng làm đề cương bài giảng chuẩn, khung thực hành bài tập lớn (assignments/labs) và làm tài liệu tham khảo để xây dựng các giải thuật nâng cao.

---

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

1. Tài liệu này phù hợp với đối tượng nào?

Tài liệu được biên soạn phục vụ sinh viên khối ngành Công nghệ thông tin và Kỹ thuật máy tính tại Trường Đại học Bách Khoa TP.HCM (mã môn CO2003) cùng những người học cần nắm vững bản chất cài đặt cấu trúc dữ liệu mức hệ thống.

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

Người học cần hoàn thành học phần Nhập môn lập trình / Kỹ thuật lập trình C++, nắm vững cú pháp struct/class, kỹ thuật truyền tham chiếu, thao tác con trỏ và quản trị bộ nhớ động.

3. Ngăn xếp cài đặt bằng danh sách liên kết và mảng khác nhau như thế nào?

Cài đặt bằng danh sách liên kết cho phép mở rộng kích thước linh hoạt theo bộ nhớ hệ thống nhưng tốn thêm bộ nhớ lưu con trỏ next. Cài đặt bằng mảng tối ưu về định vị ô nhớ cục bộ nhưng đòi hỏi phải xác định kích thước capacity cố định trước khi khởi tạo.

4. Phương pháp tự học nội dung này như thế nào để đạt hiệu quả cao?

Người học nên kết hợp đọc hiểu sơ đồ trạng thái (Figures 1–6), viết lại giải thuật bằng mã giả, sau đó tự tay lập trình lại các lớp Stack và ArrayStack trên C++, kiểm thử đầy đủ các trường hợp biên như ngăn xếp rỗng hoặc ngăn xếp đầy.

5. Những thao tác cơ bản nào bắt buộc phải có của cấu trúc Stack?

Các thao tác bắt buộc gồm: khởi tạo ngăn xếp (Stack() / createStack), chèn phần tử vào đỉnh (Push), rút phần tử khỏi đỉnh (Pop), xem phần tử ở đỉnh (GetStackTop / Top), kiểm tra rỗng (IsEmpty) và giải phóng ngăn xếp (Clear / Destructor).

---

Kết luận

Bài giảng Chapter 5: Stack and Queue thuộc môn học Data Structure and Algorithms [CO2003] của Trường Đại học Bách Khoa TP.HCM cung cấp đầy đủ nền tảng lý thuyết và kỹ năng cài đặt thực tế cho hai cấu trúc dữ liệu tuyến tính hạn chế chuẩn tắc.

Việc nắm vững cơ chế vận hành LIFO/FIFO, kỹ thuật mã hóa C++ Template và kỹ năng phân tích thuật toán qua Big-O là bước chuẩn bị bắt buộc để người học tiếp cận các chủ đề tiếp theo trong chương trình đào tạo gồm Cấu trúc Cây (Binary Trees, AVL Trees), Hàng đợi ưu tiên (Heap), Giải thuật tìm kiếm và Cấu trúc Đồ thị (Graphs).

Trích đoạn nội dung tài liệu

Data Structure and Algorithms [CO2003] Chapter 5 - Stack and Queue Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Faculty of Computer Science and Engineering Hochiminh city University of Technology Contents 1. Basic operations of Stacks 2. Implementation of Stacks 3.

Applications of Stack 4. Basic operations of Queues 5. Implementation of Queue a. Applications of Queue Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 1/86 L.1 - Depict the following concepts: (a) array list and linked list, including single link and double links, and multiple links; (b) stack; and (c) queue and circular queue.2 - Describe storage structures by using pseudocode for: (a) array list and linked list, including single link and double links, and multiple links; (b) stack; and (c) queue and circular queue.3 - List necessary methods supplied for list, stack, and queue, and describe them using pseudocode.4 - Implement list, stack, and queue using C/C++. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 2/86 L.5 - Use list, stack, and queue for problems in real-life, and choose an appropriate implementation type (array vs.6 - Analyze the complexity and develop experiment (program) to evaluate the efficiency of methods supplied for list, stack, and queue.4 - Develop recursive implementations for methods supplied for the following structures: list, tree, heap, searching, and graphs.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion). Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 3/86 Basic operations of Stacks General list: e No restrictions on which operation can be used on the list. e No restrictions on where data can be inserted/deleted. Restricted list: e Only some operations can be used on the list. e Data can be inserted/deleted only at the ends of the list.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 4/86 Linear list concepts Linear lists Restricted | | FIFO LIFO Unordered§ | Ordered (queue) (stack) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 5/86 Definition ⁄ A stack of elements of type T is a finite sequence of elements of T, in which all insertions and deletions are restricted to one end, called the top. Stack is a Last In - First Out (LIFO) data structure.

LIFO: The last item put on the stack is the first item that can be taken off. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 6/86 asic operations of Stacks Basic operations: e Construct a stack, leaving it empty. e Push an element: put a new element on to the top of the stack.

e Pop an element: remove the top element from the top of the stack. e Top an element: retrieve the top element. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 7/86 Basic operations of Stacks Extended operations: e Determine whether the stack is empty or not.

e Determine whether the stack is full or not. e Find the size of the stack. e Clear the stack to make it empty. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 8/86 Basic operations of Stacks: Push Push Data | [SS | Top pi | mm fC] E—] Cd Stack Stack Figure 1: Successful Push operation Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 9/86 Basic operations of Stacks: Push Overflow Data Stack Figure 2: Unsuccessful Push operation. Stack remains unchanged. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 10 / 86 Basic operations of Stacks: Pop ES ong Top | E— ——> LÍ Top CO Cd Stack Stack Figure 3: Successful Pop operation Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 11/86 ic operations of Stacks: Pop Underflow Top Stack Figure 4: Unsuccessful Pop operation. Stack remains unchanged. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 12/86 Basic operations of Stacks: Top Siack Top Eee Top | L—— 1 Top Crs |C— tL] Lo] Stack Stack Figure 5: Successful Top operation. Stack remains unchanged.