Editorial for queue: Truy vấn với hàng đợi

Hiểu bài toán

Bài toán yêu cầu mô phỏng một hàng đợi (queue) với các thao tác cơ bản: thêm vào cuối (enqueue), loại bỏ khỏi đầu (dequeue), và xem phần tử đầu tiên (peek). Có T truy vấn, mỗi truy vấn là một trong ba loại: 1 n (đẩy n vào cuối), 2 (lấy ra khỏi đầu), hoặc 3 (in ra phần tử đầu). Nếu hàng đợi rỗng khi thực hiện thao tác 2 hoặc 3, thao tác 2 không làm gì cả và thao tác 3 in ra 'Empty!'. Với T lên tới 10^5, cần một cách tiếp cận hiệu quả về thời gian và bộ nhớ.

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

Cách Mô phỏng bằng Linked List (Con trò)

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

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

typedef struct {
    Node *front;
    Node *rear;
} Queue;

void push(Queue *q, int n) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = n;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

void pop(Queue *q) {
    if (q->front == NULL) return;
    Node *temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
}

int peek(Queue *q) {
    if (q->front == NULL) return -1; // -1 indicates empty
    return q->front->value;
}

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

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

Cách tiếp cận này sử dụng danh sách liên kết (Linked List) để triển khai hàng đợi. Mỗi phần tử là một node chứa giá trị và con trỏ tới node tiếp theo. Hàng đợi lưu trữ con trỏ tới node đầu (front) và node cuối (rear).

• Thêm vào cuối (type 1): Tạo node mới, gắn vào sau node cuối cùng (rear), cập nhật rear. Nếu rỗng thì cả front và rear đều trỏ tới node mới. Thời gian O(1).
• Lấy ra đầu (type 2): Lưu node đầu vào biến temp, di chuyển front lên node tiếp theo, giải phóng bộ nhớ của temp. Nếu queue rỗng thì không làm gì. Thời gian O(1).
• Xem đầu (type 3): Trả về giá trị của node front. Nếu rỗng trả về -1 (hoặc xử lý in 'Empty!'). Thời gian O(1). Vì mỗi thao tác là O(1) và có T truy vấn, tổng thời gian là O(T). Phương pháp này linh hoạt về dung lượng nhưng có chi phí cấp phát bộ nhớ động.

Cách Mô phỏng bằng Mảng động (Cyclic Array)

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

#define MAX_SIZE 100005

int queue[MAX_SIZE];
int front = 0;
int rear = -1;
int count = 0;

void push(int n) {
    if (count == MAX_SIZE) return; // Should not happen based on constraints
    rear = (rear + 1) % MAX_SIZE;
    queue[rear] = n;
    count++;
}

void pop() {
    if (count == 0) return;
    front = (front + 1) % MAX_SIZE;
    count--;
}

int peek() {
    if (count == 0) return -1;
    return queue[front];
}

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)

Cách tiếp cận này sử dụng một mảng cố định để lưu trữ hàng đợi, sử dụng kỹ thuật 'Cyclic Queue' (Hàng đợi tuần hoàn). Hai biến front và rear chỉ vị trí.

• Thêm vào cuối (type 1): Tăng rear lên 1 (theo modulo kích thước mảng), gán giá trị vào queue[rear].
• Lấy ra đầu (type 2): Tăng front lên 1 (theo modulo).
• Xem đầu (type 3): Trả về queue[front]. Để kiểm tra xem hàng đợi có rỗng hay không, ta có thể dùng một biến đếm count hoặc so sánh front và rear. Phương pháp này có chi phí cấp phát bộ nhớ ít hơn Linked List (không cần tạo node mới cho mỗi phần tử) và truy cập bộ nhớ liên tục tốt hơn. Tuy nhiên, cần chú ý đến việc lặp lại chỉ số (modulo) và giới hạn kích thước mảng.

Cách Sử dụng biến chỉ số và mảng tĩnh

#include <stdio.h>

int q[100005];
int head = 0, tail = 0;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int cmd;
        scanf("%d", &cmd);
        if (cmd == 1) {
            int n;
            scanf("%d", &n);
            q[tail++] = n;
        } else if (cmd == 2) {
            if (head < tail) head++;
        } else {
            if (head == tail) printf("Empty!\n");
            else printf("%d\n", q[head]);
        }
    }
    return 0;
}

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

Đây là biến thể đơn giản nhất của mảng động, được thấy trong Solution 2 và 3. Ta dùng mảng tĩnh đủ lớn, head chỉ vị trí đầu, tail chỉ vị trí cuối cùng tiếp theo.

• Thêm vào (type 1): Gán q[tail] = n rồi tăng tail.
• Lấy ra (type 2): Nếu head < tail thì tăng head.
• Xem đầu (type 3): Nếu head == tail thì rỗng, ngược lại in q[head]. Phương pháp này rất nhanh và đơn giản để code. Nhược điểm là các phần tử đã lấy ra vẫn nằm trong mảng, nhưng với giới hạn T=10^5, mảng 100k phần tử là hoàn toàn chấp nhận được.

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

Bài học kinh nghiệm

• Hàng đợi (Queue) theo nguyên tắc FIFO (First In First Out) - Vào trước, Ra trước.
• Thao tác với hàng đợi cơ bản (đẩy vào, lấy ra, xem đầu) đều phải thực hiện trong thời gian O(1) để đảm bảo hiệu năng với số lượng truy vấn lớn.
• Mảng tĩnh hoặc động kết hợp với hai chỉ số đầu và cuối (hoặc biến đếm) là cách triển khai phổ biến và hiệu quả nhất trong lập trình thi đấu.

Lỗi thường gặp

• Quên kiểm tra hàng đợi rỗng trước khi thực hiện thao tác lấy ra hoặc xem phần tử đầu, dẫn đến lỗi truy cập ngoài vùng nhớ.
• Sử dụng Linked List nhưng quên giải phóng bộ nhớ (free) khi lấy phần tử ra có thể gây rò rỉ bộ nhớ (memory leak) trong các bài toán lớn.
• Nếu dùng mảng cyclic (vòng tròn), cần xử lý đúng phép chia lấy dư để các chỉ số quay lại đầu mảng khi đầy.