Hướng giải của Mô Phỏng Deque Cơ Bản

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu mô phỏng cấu trúc dữ liệu Deque (Double-ended Queue). Trong C++, thư viện chuẩn đã hỗ trợ sẵn cấu trúc std::deque hiệu quả với các thao tác thêm/bớt ở hai đầu có độ phức tạp thời gian là \(O(1)\).

Ta chỉ cần sử dụng các phương thức có sẵn:

  • push_front(x): Thêm vào đầu.
  • push_back(x): Thêm vào cuối.
  • pop_front(): Xóa ở đầu (cần kiểm tra empty()).
  • pop_back(): Xóa ở cuối (cần kiểm tra empty()).
  • front(): Lấy phần tử ở đầu (cần kiểm tra empty()).
  • back(): Lấy phần tử ở cuối (cần kiểm tra empty()).

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu hóa vào ra nhanh
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    if (!(cin >> q)) return 0;

    deque<int> dq;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            dq.push_front(x);
        } else if (t == 2) {
            int x;
            cin >> x;
            dq.push_back(x);
        } else if (t == 3) {
            if (!dq.empty()) {
                dq.pop_front();
            }
        } else if (t == 4) {
            if (!dq.empty()) {
                dq.pop_back();
            }
        } else if (t == 5) {
            if (dq.empty()) {
                cout << -1 << "\n";
            } else {
                cout << dq.front() << "\n";
            }
        } else if (t == 6) {
            if (dq.empty()) {
                cout << -1 << "\n";
            } else {
                cout << dq.back() << "\n";
            }
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.