Cách Sử Dụng Double-ended Queue

Trong bài viết này, chúng ta sẽ khám phá double-ended queue (deque) – một cấu trúc dữ liệu trừu tượng (ADT) cho phép thêm và xóa phần tử từ cả hai đầu. Bài viết cung cấp 20 ví dụ sử dụng (mã giả) chính xác, cùng hướng dẫn chi tiết về định nghĩa, các thao tác, độ phức tạp thời gian, và các lưu ý quan trọng.

Phần 1: Hướng dẫn sử dụng double-ended queue và các lưu ý

1. Định nghĩa cơ bản của double-ended queue

Double-ended queue (deque) là một hàng đợi hai đầu, cho phép:

• Thêm phần tử vào đầu (insertFront).
• Thêm phần tử vào cuối (insertRear).
• Xóa phần tử khỏi đầu (deleteFront).
• Xóa phần tử khỏi cuối (deleteRear).

Ví dụ:

• Thêm 5 vào đầu: [5, …]
• Thêm 10 vào cuối: […, 10]
• Xóa phần tử ở đầu: [phần tử còn lại…]
• Xóa phần tử ở cuối: […phần tử còn lại]

2. Cách sử dụng double-ended queue

a. Các thao tác cơ bản

1. insertFront(value)
   Ví dụ: deque.insertFront(5) (Thêm 5 vào đầu deque.)
2. insertRear(value)
   Ví dụ: deque.insertRear(10) (Thêm 10 vào cuối deque.)
3. deleteFront()
   Ví dụ: deque.deleteFront() (Xóa phần tử ở đầu deque.)
4. deleteRear()
   Ví dụ: deque.deleteRear() (Xóa phần tử ở cuối deque.)
5. getFront()
   Ví dụ: firstElement = deque.getFront() (Lấy phần tử ở đầu deque.)
6. getRear()
   Ví dụ: lastElement = deque.getRear() (Lấy phần tử ở cuối deque.)
7. isEmpty()
   Ví dụ: if deque.isEmpty() then print(“Deque is empty”) (Kiểm tra deque có rỗng không.)
8. isFull()
   Ví dụ: if deque.isFull() then print(“Deque is full”) (Kiểm tra deque có đầy không.)

b. Biến thể và cách dùng trong câu (mã giả)

Thao tác	Mô tả	Độ phức tạp thời gian	Ví dụ (mã giả)
insertFront(value)	Thêm phần tử vào đầu deque	O(1) hoặc O(n) (tùy implementation)	Deque.insertFront(5)
insertRear(value)	Thêm phần tử vào cuối deque	O(1) hoặc O(n) (tùy implementation)	Deque.insertRear(10)
deleteFront()	Xóa phần tử khỏi đầu deque	O(1) hoặc O(n) (tùy implementation)	Deque.deleteFront()
deleteRear()	Xóa phần tử khỏi cuối deque	O(1) hoặc O(n) (tùy implementation)	Deque.deleteRear()

3. Một số ứng dụng thông dụng của double-ended queue

• Undo/Redo: Lưu trữ các thao tác trong một deque.
• Kiểm tra Palindrome: Sử dụng deque để kiểm tra chuỗi có phải Palindrome không.
• Lịch sử trình duyệt web: Lưu trữ các trang web đã truy cập trong một deque.

4. Lưu ý khi sử dụng double-ended queue

a. Ngữ cảnh phù hợp

• Khi cần thêm/xóa phần tử ở cả hai đầu.
• Khi thứ tự các phần tử quan trọng.
• Thay thế cho stack hoặc queue khi cần chức năng của cả hai.

b. Phân biệt với các cấu trúc dữ liệu khác

• Deque vs Queue:
  – Deque: Thêm/xóa ở cả hai đầu.
  – Queue: Thêm ở cuối, xóa ở đầu (FIFO).
• Deque vs Stack:
  – Deque: Thêm/xóa ở cả hai đầu.
  – Stack: Thêm/xóa ở một đầu (LIFO).

c. Lựa chọn Implementation

• Array-based Deque: Cần biết kích thước tối đa, truy cập nhanh.
• Linked-list-based Deque: Kích thước động, tốn bộ nhớ hơn.

5. Những lỗi cần tránh

1. Thực hiện thao tác trên deque rỗng: Kiểm tra `isEmpty()` trước.
2. Truy cập ngoài phạm vi khi sử dụng array-based deque: Kiểm tra `isFull()` trước khi thêm.
3. Quên cập nhật con trỏ (head/tail) khi sử dụng linked-list-based deque: Dẫn đến memory leak hoặc lỗi logic.

6. Mẹo để ghi nhớ và sử dụng hiệu quả

• Hình dung: Deque như một hàng đợi có thể “co giãn” ở cả hai đầu.
• Thực hành: Viết code các thao tác cơ bản với deque.
• Ứng dụng: Tìm hiểu các bài toán thực tế có thể giải bằng deque.

Phần 2: Ví dụ sử dụng double-ended queue (mã giả)

Ví dụ minh họa

1. Create a deque called ‘myDeque’. (Tạo một deque tên là ‘myDeque’.)
2. myDeque.insertFront(10). (Thêm 10 vào đầu deque.)
3. myDeque.insertRear(20). (Thêm 20 vào cuối deque.)
4. myDeque.insertFront(5). (Thêm 5 vào đầu deque.)
5. firstElement = myDeque.getFront(). (Lấy phần tử ở đầu deque.)
6. lastElement = myDeque.getRear(). (Lấy phần tử ở cuối deque.)
7. print(firstElement). (In ra phần tử đầu tiên.)
8. print(lastElement). (In ra phần tử cuối cùng.)
9. myDeque.deleteFront(). (Xóa phần tử ở đầu deque.)
10. myDeque.deleteRear(). (Xóa phần tử ở cuối deque.)
11. if myDeque.isEmpty() then print(“Deque is empty”). (Nếu deque rỗng thì in ra “Deque is empty”.)
12. myDeque.insertRear(30). (Thêm 30 vào cuối deque.)
13. secondElement = myDeque.getFront(). (Lấy phần tử ở đầu deque (lần thứ hai). )
14. print(secondElement). (In ra phần tử đầu tiên (lần thứ hai).)
15. myDeque.deleteFront(). (Xóa phần tử ở đầu deque (lần thứ hai).)
16. if myDeque.isEmpty() then print(“Deque is empty”). (Nếu deque rỗng thì in ra “Deque is empty” (lần thứ hai).)
17. myDeque.insertFront(40). (Thêm 40 vào đầu deque.)
18. myDeque.insertRear(50). (Thêm 50 vào cuối deque.)
19. myDeque.deleteFront(). (Xóa phần tử ở đầu deque (lần thứ ba).)
20. if myDeque.getFront() == 50 then print (“50 is at the front”) . (Nếu phần tử đầu tiên là 50 thì in ra “50 is at the front”.)