Chuyển tới nội dung chính

Deque & bộ đệm vòng

Bạn sẽ học được gì

Hai biến thể mạnh mẽ: deque (hàng đợi hai đầu) cho thêm/xóa ở cả hai đầu đều O(1), và bộ đệm vòng (circular buffer) — hàng đợi kích thước cố định tự ghi đè cái cũ nhất.

1. Deque — hàng đợi hai đầu​

Deque (double-ended queue, đọc là "đẹc") cho phép thêm/xóa ở cả đầu lẫn cuối, tất cả O(1). Nó là "siêu tập" của cả stack lẫn queue.

   thêm/xóa ◀──┐                   ┌──▶ thêm/xóa
               │                   │
         ┌─────┴─┬───────┬───────┬─┴─────┐
         │  10   │  20   │  30   │  40   │
         └───────┴───────┴───────┴───────┘
          đầu (left)              cuối (right)
Đang tải trình chạy code…

Dùng deque làm gì? Vì làm được cả hai đầu O(1): dùng làm stack, làm queue, làm sliding window (Trụ 4), hàng undo/redo, lịch sử duyệt web (tiến/lùi).

2. Bộ đệm vòng (circular buffer)​

Hàng đợi kích thước cố định N. Khi đầy mà thêm tiếp → ghi đè phần tử cũ nhất. Con trỏ chạy vòng quanh mảng (dùng phép chia lấy dư % N).

N = 4, đã ghi 5,6,7,8 rồi ghi tiếp 9:
        ┌────┬────┬────┬────┐
        │ 9  │ 6  │ 7  │ 8  │     9 ghi đè 5 (cũ nhất)
        └────┴────┴────┴────┘
           ▲
        vị trí ghi tiếp = (chỉ_số + 1) % N

Dùng khi: chỉ cần giữ N mục gần nhất — log gần đây, N tin nhắn cuối, dữ liệu cảm biến theo thời gian thực, bộ đệm âm thanh/video.

3. Chạy debug: bộ đệm vòng ghi đè​

Bộ đệm cỡ 3. Bước qua việc ghi 5 phần tử — để ý con trỏ pos chạy vòng và cái cũ bị đè:

🐞 Bộ đệm vòng cỡ 3, ghi 1,2,3,4,5Bước 1/6
1buf = [None, None, None]   # N = 3
2pos = 0
3def ghi(x):
4  buf[pos] = x
5  pos = (pos + 1) % 3     # chay vong
Biến tại bước này
buf[_, _, _]
pos0
👉 Đệm rỗng, pos = 0.

4. Cài deque làm circular buffer dễ nhất​

Trong Python, deque(maxlen=N) chính là bộ đệm vòng — tự bỏ phần tử cũ khi đầy:

Đang tải trình chạy code…

5. Mẫu nhận diện​

  • Cần thêm/xóa cả hai đầu O(1) → deque.
  • Cần giữ N mục gần nhất, tự quên cái cũ → bộ đệm vòng (deque(maxlen=N)).
  • Sliding window (Trụ 4) thường dùng deque.

6. 🎮 Trò chơi: Deque & buffer​

🎮 Deque & bộ đệm vòngCâu 1/4· Điểm 0· 🔥 0

Deque = hai đầu O(1). Circular buffer = cố định N, đè cái cũ nhất.

Con trỏ bộ đệm vòng chạy vòng bằng phép?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Deque khác queue thường ở chỗ?
2. Bộ đệm vòng dùng khi nào?
3. deque(maxlen=N) khi đầy và append thêm sẽ?

8. Hoàn thành​

…

☑️ Tiếp theo: 2.3.4 — Ứng dụng stack & queue.