Ngăn xếp

Khái niệm cơ bản

Nguyên tắc hoạt động của ngăn xếp là vào sau - ra trước (LIFO).

Cài đặt

// Mô phỏng ngăn xếp bằng mảng
int stackArray[N];
int topIndex = 0;

// Làm rỗng ngăn xếp khi cần thiết
while (!isEmpty()) {
    pop();
}

// Sử dụng vector để mô phỏng ngăn xếp
vector<int> st;
st.push_back(value);   // Thêm phần tử vào đỉnh
st.pop_back();         // Loại bỏ phần tử ở đỉnh
st.back();             // Truy cập phần tử ở đỉnh

// Khi so sánh với phần tử đỉnh, có thể xảy ra nhiều lần lấy ra -> dùng vòng lặp while
while (!st.empty() && condition) {
    st.pop_back();
}

Dạng bài thường gặp

1. Bài toán khử cặp (Pair Matching)

Loại bài này yêu cầu kiểm tra sự tương ứng giữa các ký hiệu đối xứng như dấu ngoặc hoặc chuyển đổi biểu thức tiền tố/hậu tố.

• P4387 – Kiểm tra dãy thao tác hợp lệ trên ngăn xếp
• P1449 – Tính giá trị biểu thức hậu tố
• UVA673 – Kiểm tra dấu ngoặc cân bằng
• LeetCode 735 – Va chạm tiểu hành tinh

2. Ngăn xếp đơn điệu

Một ngăn xếp được gọi là đơn điệu nếu các phần tử từ đáy lên đỉnh tạo thành một dãy tăng/giảm nghiêm ngặt.

Lưu ý: Thứ tự quan trọng hơn tên gọi tăng hay giảm.

Ứng dụng chính

• Tìm phần tử đầu tiên bên trái lớn hơn hiện tại
• Tìm phần tử đầu tiên bên phải nhỏ hơn hiện tại
• V.v…

Chiến lược thực hiện

(Giả sử ngăn xếp tăng dần từ đáy đến đỉnh):

• Nếu phần tử mới lớn hơn đỉnh ngăn xếp → thêm trực tiếp
• Ngược lại → liên tục loại bỏ các phần tử ở đỉnh cho đến khi thỏa điều kiện

Ví dụ minh họa

• P5788: Tìm phần tử đầu tiên phía sau lớn hơn mỗi phần tử trong mảng

// Duyệt từ cuối về đầu
for (int i = n; i >= 1; i--) {
    while (!stk.empty() && a[stk.top()] <= a[i])
        stk.pop();
    result[i] = stk.empty() ? -1 : stk.top();
    stk.push(i);
}

• LeetCode 42: Bài toán hứng nước mưa

Hàng đợi

Nguyên lý hoạt động

Hàng đợi tuân theo nguyên tắc vào trước - ra trước (FIFO).

Cài đặt

// Mô phỏng hàng đợi bằng mảng
int queueArray[N];
int frontPointer = 0, rearPointer = 0;

Các dạng mở rộng

1. Hàng đợi đơn điệu

Tương tự ngăn xếp đơn điệu nhưng ít phổ biến hơn, chủ yếu phục vụ tối ưu hóa thuật toán như quy hoạch động.

2. Hàng đợi ưu tiên

Phần tử được lấy ra dựa trên mức độ ưu tiên thay vì thứ tự nhập. Thường cài đặt thông qua cấu trúc heap (max-heap hoặc min-heap).

Ví dụ áp dụng

• P1996 – Bài toán Josephus

// Tạo vòng lặp bằng cách đẩy phần tử đầu về cuối
for (int i = 1; i < k; ++i) {
    q.push(q.front());
    q.pop();
}
cout << q.front() << ' ';
q.pop();