[Buổi 16][Hàng đợi & Hàng đợi hai đầu][HW] Bài 3: Bộ đệm hai đầu
Bộ đệm hai đầu
Bối cảnh và bài toán
Một bộ đệm hỗ trợ thêm/xóa và đọc dữ liệu ở cả hai đầu. Hệ thống nhận chuỗi lệnh trực tuyến; các lệnh đọc/xóa khi bộ đệm rỗng phải trả về EMPTY.
Yêu cầu
Mô phỏng chính xác các lệnh.
Input
- Dòng 1: số lệnh
q. - Mỗi dòng sau là một trong
PUSH_FRONT x,PUSH_BACK x,POP_FRONT,POP_BACK,FRONT,BACK.
Output
Với mỗi lệnh POP/FRONT/BACK, in giá trị liên quan hoặc EMPTY.
Ràng buộc
1 <= q <= 10^5|x| <= 10^9
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 30% | q <= 100 | 01–03 |
| S2 | 30% | q <= 5000 | 04–06 |
| S3 | 40% | Không có ràng buộc bổ sung | 07–10 |
Ví dụ 1
Input
6
PUSH_BACK 3
PUSH_FRONT 1
FRONT
BACK
POP_FRONT
POP_BACK
Output
1
3
1
3
Giải thích. Deque lần lượt là [3], [1,3], rồi các truy vấn/xóa lấy đúng hai đầu.
Ví dụ 2
Input
2
POP_FRONT
BACK
Output
EMPTY
EMPTY
Giải thích. Không có phần tử trong bộ đệm.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M05-B16-HW03 |
| Buổi | B16 |
| Loại bài | HOMEWORK |
| Mức độ khó | Dễ (Easy) |
| Thời gian làm bài khuyến nghị | 25 phút |
| Time limit | 1 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++11 trở lên |
Nguồn: FULLHOUSE DEV – Self-generated.
Comments