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<Long>, với đỉnh là cuối list:

// Main.java
void main() {
    var history = new PriceHistory();
    history.push(5000);
    history.push(5500);
    history.push(6000);
    System.out.println(history.pop());    // 6000
    System.out.println(history.peek());   // 5500
}

// PriceHistory.java
import java.util.ArrayList;
import java.util.List;

class PriceHistory {
    private final List<Long> items =
        new ArrayList<>();

    public void push(long price) {
        items.add(price);
    }

    public long pop() {
        return items.remove(items.size() - 1);
    }

    public long peek() {
        return items.get(items.size() - 1);
    }
}

• Đỉnh là cuối list, vì thêm và xoá ở cuối ArrayList là O(1), không phải dời phần tử nào (bài Array và List bên trong).
• remove(i) xoá phần tử ở vị trí i và trả về chính phần tử đó.
• 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).

Java có sẵn ArrayDeque với đúng ba method push, pop, peek.

var history = new ArrayDeque<Integer>();
history.push(5000);
history.push(5500);
history.push(6000);
System.out.println(history.pop());
System.out.println(history.peek());

Thử ngay

Dùng ArrayDeque của Java để lưu lịch sử thao tác:

// Main.java
void main() {
    var undo = new ArrayDeque<String>();
    undo.push("Sửa giá Bút bi");
    undo.push("Xoá Vở");
    undo.push("Thêm Thước");

    System.out.println(undo.pop());
    System.out.println(undo.pop());
    System.out.println(undo.peek());
    System.out.println(undo.size());
}

Đ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, ArrayDeque ném NoSuchElementException. Riêng peek khi rỗng không ném lỗi mà trả về null.

// SAI — bấm Hoàn tác khi chưa làm gì là lỗi
var undo = new ArrayDeque<String>();
System.out.println(undo.pop());

// ĐÚNG — kiểm tra isEmpty() trước khi pop
var undo = new ArrayDeque<String>();
if (!undo.isEmpty()) {
    System.out.println(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 isEmpty() trước khi pop hoặc peek.