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

Chuyên khảo toán học phân tích Data structure and algorithms cấu trúc dữ liệu và thuật toán ch05 stack queue, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Đề 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ớ.

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. rere Duc Dung Nguyen, PhD. Contact: [e-mail]| Data Structure and Algorithms [CO2003] 13 / 86 ic operations of Stacks: Top Underflow Top Stack Figure 6: Unsuccessful Top operation.

Stack remains unchanged. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 14/86 Implementation of Stacks Linked-list implementation Stack structure top Top|L —_] L5 lMƒE>_ 1= «= JUL Conceptual Physical rer: Duc Dung Nguyen, PhD.vn| Data Structure and Algorithms [CO2003] 15 / 86 Linked-list implementation Stack structure count top Stack node structure data next Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] stack count <integer> top <node pointer> end stack node data <dataType> next <node pointer> end node Data Structure and Algorithms [CO2003] 16 / 86 Linked-list implementation in C++ template <class ltemType> struct Node { ItemType data; Node<ItemType> *next; ti Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 17 / 86 Linked-list implementation in C++ template <class List ltemType> class Stack { public: Stack (); ~Stack(); void Push(List ItemType dataln); int Pop(List_ ItemType &dataOut ); int GetStackTop(List_ItemType &dataOut); void Clear(); int IsEmpty(); int GetSize(); Stack<List_ItemType>* Clone(); void Print2Console(); private: Node<List_ItemType>* top; int count; ti Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 18 / 86 Create an empty Linked Stack Before After ? ? 0 count top count top (no stack) (empty stack) rer: Duc Dung Nguyen, PhD.vn| Data Structure and Algorithms [CO2003] 19 / 86 eate an empty Linked Stack Algorithm createStack(ref stack <metadata>) Initializes the metadata of a stack Pre: stack is a metadata structure of a stack Post: metadata initialized stack.top = null return End createStack Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 20 / 86 Create an empty Linked Stack template <class List ltemType> Stack<List_ItemType >::Stack(){ is—>top = NULL; —>count = 0; template <class List ltemType> Stack<List_ItemType >::~ Stack (){ this—>Clear(); } Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 21 / 86 Push data into a Linked Stac Before After oC] BC Bore data next Cd data / next stacl stacl : uA L: ]EÍl le] count top data / next count top data / next ⁄ˆ L [seen] DI [sen] Di data next data next 1.

Allocate memory for the new node and set up data. Update pointers: e Point the new node to the top node (before adding the new node). e Point top to the new node. Update count Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 22 / 86 Push data into a Linked Stack Algorithm pushStack(ref stack <metadata>, val data <dataType>) Inserts (pushes) one item into the stack Pre: stack is a metadata structure to a valid stack data contains value to be pushed into the stack Post: data have been pushed in stack Return true if successful; false if memory overflow Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 23 / 86 Push data into a Linked Stack if stack full then | success = false else allocate (pNew) pNew -> data = data pNew -> next = stack.top = pNew stack.count + 1 success = true end return success End pushStack Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 24 / 86 Push data into a Linked Stack template <class List ltemType> void Stack<List_ItemType >::Push (List_ItemType value){ Node<List_ItemType>* pNew = new Node<List_ItemType >(); pNew—>data = value; pNew—>next this —>top; this—>top = pNew; this —>count++; Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 25 / 86 Push data into a Linked Stac e Push is successful when allocation memory for the new node is successful.

e There is no difference between push data into a stack having elements and push data into an empty stack (top having NULL value is assigned to pNew->next: that’s corresponding to a list having only one element). Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 26 / 86 Pop Linked Stack Before After ar [Bs Ja next data ⁄ˆ next count top data count top data next data__next data Lo (ver) next 1. dltPtr holds the element on the top of the stack.

top points to the next element. Decrease count by 1. Lecturer: Duc Dung Nguyen, PhD.vn| Data Structure and Algorithms [CO2003] 27 / 86 Pop Linked Stack AIgorithm popStack(ref stack <metadata>, ref dataOut <dataType>) Pops the item on the top of the stack and returns it to caller Pre: stack is a metadata structure to a valid stack dataOut is to receive the popped data Post: data have been returned to caller Return true if successful; false if stack is empty Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 28 / 86 Pop Linked Stack if stack empty then | success = false else ditPtr = stack.top dataOut = stack.top -> data stack.top -> next stack.count - 1 recycle(dltPtr) success = true end return success End popStack Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 29 / 86 Pop Linked Stack template <class List ltemType> int Stack<List_ItemType >::Pop (List_ItemType &dataOut){ if (this—>GetSize() = 0) return 0; Node<List_ItemType>* dIltPtr = this—>top; dataOut = dltPtr->data; t —>top = ditPtr—>next; this —>count —-; delete ditPtr; return 1; Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]| Data Structure and Algorithms [CO2003] 30 / 86 Pop Linked Stack e Pop is successful when the stack is not empty. e There is no difference between pop an element from a stack having elements and pop the only-one element in the stack (d1tPtr->next having NULL value is assigned to top: that’s corresponding to an empty stack). Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 31/86 AIgorithm stackTop(ref stack <metadata>, ref dataOut <dataType>) Retrieves the data from the top of the stack without changing the stack Pre: stack is a metadata structure to a valid stack dataOut is to receive top stack data Post: data have been returned to caller Return true if successful; false if stack is empty Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 32/86 if stack empty then | success = false else dataOut = stack.top -> data success = true end return success End stackTop Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 33 / 86 Stack Top template <class List ltemType> int Stack<List_ItemType >::GetStackTop (List_ItemType &dataOut){ if (this->GetSize() = 0) return 0; dataOut = this—>top—>data; return 1; Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 34/86 Algorithm destroyStack(ref stack <metadata>) Releases all nodes back to memory Pre: stack is a metadata structure to a valid stack Post: stack empty and all nodes recycled Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail]] Data Structure and Algorithms [CO2003] 35 / 86 if stack not empty then while stack.top not null do temp = stack.top -> next recycle(temp) end end stack.count = 0 return End destroyStack Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 36 / 86 Destroy Stack template <class List ltemType> void Stack<List_ItemType >::Clear() { Node<List_ItemType>* temp; while (this—>top != NULL){ temp = this—>top; this—>top = this—>top—>next ; delete temp; } this—>count = 0; Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail]] Data Structure and Algorithms [CO2003] 37 / 86 mpty Linked Stack Algorithm isEmpty(ref stack <metadata>) Determines if the stack is empty Pre: stack is a metadata structure to a valid stack Post: return stack status Return true if the stack is empty, false otherwise if count = 0 then | Return true else | Return false end End isEmpty Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hemut.