5.2.1 Stack và LIFO

Một ngăn xếp (stack) là một cấu trúc được phát triển để lưu trữ dữ liệu theo một cách đặc biệt. Hãy tưởng tượng một ngăn xếp đựng đồng xu. Bạn không thể đặt một đồng xu bất cứ nơi nào khác ngoài đỉnh của ngăn xếp. Tương tự như vậy, bạn không thể lấy một đồng xu ra khỏi ngăn xếp từ bất cứ nơi nào khác ngoài đình của ngăn xếp. Nếu bạn muốn lấy đồng xu ở đáy, bạn phải lấy ra tất cả các đồng xu đang nằm trên nó.

Tên thay thế cho một stack (nhưng chỉ trong thuật ngữ IT, tất nhiên) là LIFO. Đây là một chữ viết tắt mô tả hành vi của ngăn xếp, LIFO là “Last In – First Out”, có nghĩa là “Vào cuối cùng thì ra đầu tiên”. Đồng xu được cho vào ngăn xếp cuối cùng sẽ được lấy ra đầu tiên.

Stack là một đối tượng có hai hoạt động cơ bản được đặt theo tên “push” (đặt một phần tử mới vào đầu stack) và “pop” (lấy ra một phần tử từ đầu stack). Chúng ta sẽ cần phải sử dụng các stack trong nhiều thuật toán cổ điển.

Hãy thử xây dựng một stack bằng C++. Nó sẽ là một stack rất đơn giản. Nó chỉ lưu các giá trị int.

Chúng tôi sẽ chỉ cho bạn cách thực hiện theo hai cách tiếp khác nhau: hướng thủ tục và hướng đối tượng.

Hãy bắt đầu với phương pháp hướng thủ tục.

Trước tiên, chúng ta phải quyết định làm thế nào để lưu trữ các giá trị int sẽ được cho vào stack. Chúng tôi khuyên bạn nên sử dụng phương pháp đơn giản nhất, đó là sử dụng một mảng cho công việc này. Chúng ta giả định rằng sẽ không có hơn 100 giá trị trên stack cùng một lúc. Chúng ta cũng giả sử rằng phần tử ở chỉ số 0 nằm ở đáy ngăn xếp. Stack được khai báo ở bên dưới →