Editorial for stack: Truy vấn với ngăn xếp

Hiểu bài toán

Bài toán mô phỏng hoạt động của một ngăn xếp (stack) với các truy vấn cơ bản. Bạn bắt đầu với một ngăn xếp rỗng và xử lý T truy vấn:

1. 1 n: Đẩy phần tử n vào đỉnh ngăn xếp.
2. 2: Lấy ra phần tử ở đỉnh ngăn xếp (bỏ qua nếu ngăn xếp rỗng).
3. 3: In ra phần tử ở đỉnh ngăn xếp mà không lấy ra. Nếu rỗng, in 'Empty!'. Giới hạn: T ≤ 10^5, giá trị n ≤ 10^9.

Các cách tiếp cận

Cách Mảng tĩnh (Static Array)

#include <stdio.h>

int data[100005];
int top = 0;

void push(int n) {
    data[top++] = n;
}

void pop() {
    if (top > 0) top--;
}

int peek() {
    if (top == 0) return -1;
    return data[top - 1];
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int n; scanf("%d", &n);
            push(n);
        } else if (type == 2) {
            pop();
        } else {
            int val = peek();
            if (val == -1) printf("Empty!\n");
            else printf("%d\n", val);
        }
    }
    return 0;
}

• Time Complexity: O(T)
• Space Complexity: O(T)

Sử dụng một mảng tĩnh data để lưu trữ các phần tử và biến top để chỉ số của phần tử đầu tiên trống. Các thao tác Push, Pop, Peek đều truy cập trực tiếp vào mảng qua chỉ số top nên rất nhanh (O(1)). Với T ≤ 10^5, mảng cỡ 10^5 phần tử là đủ dung lượng. Đây là cách cài đặt hiệu quả nhất về mặt hiệu năng.

Cách Cấu trúc liên kết (Linked List)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* top = NULL;

void push(int n) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = n;
    newNode->next = top;
    top = newNode;
}

void pop() {
    if (top != NULL) {
        Node *temp = top;
        top = top->next;
        free(temp);
    }
}

int peek() {
    if (top == NULL) return -1;
    return top->data;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int n; scanf("%d", &n);
            push(n);
        } else if (type == 2) {
            pop();
        } else {
            int val = peek();
            if (val == -1) printf("Empty!\n");
            else printf("%d\n", val);
        }
    }
    // Giải phóng bộ nhớ trong contest thường không cần thiết, nhưng tốt cho thực tế
    while (top != NULL) pop();
    return 0;
}

• Time Complexity: O(T)
• Space Complexity: O(T)

Sử dụng danh sách liên kết đơn. Mỗi nút lưu giá trị và con trỏ tới nút kế tiếp (nút ở đỉnh hiện tại). Push tạo nút mới và cập nhật head. Pop giải phóng nút head và chuyển head sang next. Cách này linh hoạt về bộ nhớ nhưng có chi phí hệ thống cao hơn do phải cấp phát động (malloc) và truy xuất bộ nhớ không liên tục (cache miss).

Cách Mảng động (Vector)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    vector<int> st;

    while (t--) {
        int type;
        cin >> type;
        if (type == 1) {
            int n; cin >> n;
            st.push_back(n);
        } else if (type == 2) {
            if (!st.empty()) st.pop_back();
        } else {
            if (st.empty()) cout << "Empty!\n";
            else cout << st.back() << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(T)
• Space Complexity: O(T)

Sử dụng thư viện chuẩn C++ (vector) để xử lý mảng động tự động. push_back thêm vào cuối, pop_back xóa ở cuối, back lấy phần tử cuối. Đây là cách viết ngắn gọn nhất, an toàn về bộ nhớ, và rất phổ biến trong lập trình thi đấu C++.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Cấu trúc dữ liệu Stack (Ngăn xếp) có đặc điểm LIFO (Last In First Out) - Vào sau, Ra trước.
• Thao tác với đỉnh stack (Push, Pop, Peek) đều có độ phức tạp thời gian O(1).
• Với số lượng truy vấn lớn (10^5), việc tối ưu hóa I/O (ví dụ: dùng scanf/printf ở C hoặc ios_base::sync_with_stdio(false) ở C++) là cần thiết để tránh trễ thời gian.

Lỗi thường gặp

• Quên kiểm tra stack rỗng trước khi thực hiện Pop hoặc Peek (trừ khi bài toán yêu cầu xử lý đặc biệt).
• Biến top hoặc con trỏ head trỏ sai địa chỉ sau khi Pop phần tử cuối cùng.
• Sử dụng mảng quá nhỏ so với giới hạn truy vấn (ví dụ mảng 10005 trong khi T có thể lên tới 100000).