Stack

Nhân viên sửa giá ba lần rồi bấm "Hoàn tác". Việc bị huỷ phải là lần sửa gần nhất, bấm tiếp thì tới lần trước đó. Cấu trúc làm đúng việc này là stack, và bạn đã gặp nó ở call stack của bài Đệ quy.

Khái niệm

🥞 Stack (ngăn xếp): danh sách chỉ thêm và lấy ở một đầu gọi là đỉnh, phần tử vào sau cùng được lấy ra trước tiên (LIFO: last in, first out).

Ví dụ

Tự viết một stack nhỏ lưu giá bằng List<decimal>, với đỉnh là cuối list:

var history = new PriceHistory();
history.Push(5000m);
history.Push(5500m);
history.Push(6000m);
Console.WriteLine(history.Pop());    // 6000
Console.WriteLine(history.Peek());   // 5500

class PriceHistory
{
    private readonly List<decimal> _items =
        new List<decimal>();

    public void Push(decimal price)
    {
        _items.Add(price);
    }

    public decimal Pop()
    {
        decimal top = _items[_items.Count - 1];
        _items.RemoveAt(_items.Count - 1);
        return top;
    }

    public decimal Peek()
    {
        return _items[_items.Count - 1];
    }
}

• Đỉnh là cuối list, vì thêm và xoá ở cuối List<T> là O(1), không phải dời phần tử nào (bài Array và List bên trong).
• Pop trả về 6000 là giá thêm sau cùng. Peek sau đó thấy 5500.
• Chọn đỉnh là đầu list thì mỗi lần Pop phải dời cả list, thành O(n).

.NET có sẵn Stack<T> với đúng ba method Push, Pop, Peek.

var history = new Stack<int>();
history.Push(5000);
history.Push(5500);
history.Push(6000);
Console.WriteLine(history.Pop());
Console.WriteLine(history.Peek());

Thử ngay

Dùng Stack<T> của .NET để lưu lịch sử thao tác:

var undo = new Stack<string>();
undo.Push("Sửa giá Bút bi");
undo.Push("Xoá Vở");
undo.Push("Thêm Thước");

Console.WriteLine(undo.Pop());
Console.WriteLine(undo.Pop());
Console.WriteLine(undo.Peek());
Console.WriteLine(undo.Count);

Đoán trước khi chạy: bốn dòng in ra là gì?

Thêm Thước
Xoá Vở
Sửa giá Bút bi
1

Lỗi hay gặp

Pop khi stack rỗng. Không còn gì để lấy, Stack<T> ném InvalidOperationException với lời nhắn Stack empty.

// SAI — bấm Hoàn tác khi chưa làm gì là lỗi
var undo = new Stack<string>();
Console.WriteLine(undo.Pop());

// ĐÚNG — kiểm tra Count trước khi Pop
var undo = new Stack<string>();
if (undo.Count > 0)
{
    Console.WriteLine(undo.Pop());
}

Tóm tắt

• Stack thêm và lấy ở cùng một đầu: vào sau ra trước (LIFO).
• Push, Pop, Peek đều O(1) (Push là trung bình).
• Dùng cho hoàn tác và call stack.
• Kiểm tra Count trước khi Pop hoặc Peek.