Ngăn xếp tổng quát

Thuộc phần Lập trình hướng đối tượng trong hành trình Rust của Coddy. Bài học 59 trên 61.

Thử thách

Dễ

Ngăn xếp là một cấu trúc dữ liệu cơ bản tuân theo nguyên tắc "Last In, First Out" (LIFO): phần tử được thêm vào sau cùng sẽ bị lấy ra đầu tiên. Hãy hình dung một chồng đĩa: bạn đặt đĩa lên trên cùng và lấy đĩa từ trên cùng.

Hãy xây dựng một cấu trúc dữ liệu Stack tổng quát có thể chứa phần tử thuộc bất kỳ kiểu dữ liệu nào! Ngăn xếp tuân theo nguyên tắc "Last In, First Out", giống như một chồng sách mà bạn chỉ có thể thêm hoặc lấy sách ở trên cùng.

Bạn sẽ sắp xếp code trong hai tệp:

stack.rs: Định nghĩa cấu trúc Stack<T> tổng quát, dùng Vec<T> bên trong để lưu trữ các phần tử. Triển khai ba phương thức: new để tạo ngăn xếp rỗng, push để thêm phần tử lên trên cùng và pop để lấy ra và trả về phần tử trên cùng (trả về Option<T> vì ngăn xếp có thể rỗng).
main.rs: Đưa module ngăn xếp vào và minh họa cách Stack hoạt động với các số nguyên. Tạo một ngăn xếp, thêm các số đã cho vào đó, sau đó lấy các phần tử ra và in từng phần tử. Dùng unwrap_or để xử lý Option mà pop trả về. Nếu ngăn xếp rỗng, dùng -1 làm giá trị mặc định.

Ngăn xếp cần hai thao tác thiết yếu:

push: thêm một phần tử lên trên cùng của ngăn xếp
pop: lấy ra và trả về phần tử trên cùng

Phương thức pop nên trả về Option<T> vì ngăn xếp có thể rỗng. Kiểu Vec đã có phương thức pop trả về Option<T>, bạn có thể tận dụng phương thức này trong phần triển khai.

Ngăn xếp của bạn sẽ hoạt động như sau: khi bạn thêm các giá trị 10, 20 và 30 (theo thứ tự đó), lấy phần tử ra ba lần sẽ cho kết quả 30, 20 và 10 (theo thứ tự ngược lại). Lần lấy thứ tư trên ngăn xếp rỗng sẽ trả về giá trị mặc định.

In mỗi giá trị được lấy ra trên một dòng riêng:

Ví dụ, với các đầu vào 5, 15 và 25:

Bạn sẽ nhận ba đầu vào: ba số nguyên cần thêm vào ngăn xếp (phân tích mỗi số thành i32). Sau khi thêm cả ba số, lấy phần tử ra bốn lần để minh họa cả trường hợp lấy phần tử thành công lẫn trường hợp ngăn xếp rỗng.

Tự làm thử

mod stack;

use stack::Stack;

fn main() {
    // Đọc ba số nguyên từ đầu vào
    let mut input1 = String::new();
    std::io::stdin().read_line(&mut input1).expect("Failed to read line");
    let num1: i32 = input1.trim().parse().expect("Invalid number");

    let mut input2 = String::new();
    std::io::stdin().read_line(&mut input2).expect("Failed to read line");
    let num2: i32 = input2.trim().parse().expect("Invalid number");

    let mut input3 = String::new();
    std::io::stdin().read_line(&mut input3).expect("Failed to read line");
    let num3: i32 = input3.trim().parse().expect("Invalid number");

    // TODO: Tạo một Stack mới

    // TODO: Push ba số vào ngăn xếp (theo thứ tự num1, num2, num3)

    // TODO: Pop bốn lần và in ra từng kết quả
    // Dùng unwrap_or(-1) để xử lý trường hợp ngăn xếp rỗng
}