Giới thiệu về cấu trúc dữ liệu Deque
Trong hai bài viết trước đây về Monotonic Stack, tôi đã chia sẻ về cách sửa dụng stack một cách hiệu quả để tìm giá trị nhỏ/lớn gần nhất trong một dãy số. Tiếp nối chuỗi series về cấu trúc dữ liệu và thuật toán tối ưu, trong bài viết này, chúng ta sẽ cùng đi sâu vào Deque (Double-Ended Queue) – một cấu trúc dữ liệu linh hoạt được dùng rất nhiều trong các bài toán sliding window.
Deque (Double-Ended Queue) là một cấu trúc dữ liệu cho phép:
- Chèn (push) phần tử vào đầu hoặc cuối.
- Xóa (pop) phần tử ở đầu hoặc cuối.
Khác với stack (chỉ làm việc với 1 đầu) hay queue (chỉ vào 1 đầu, ra 1 đầu), deque linh hoạt hơn.
Các thao tác cơ bản trên cấu trúc dữ liệu Deque
- PushFront(x): Thêm phần tử
x
vào đầu trước - PushBack(x): Thêm phần tử
x
vào đầu sau - PopFront(): Xóa phần tử ở đầu trước
- PopBack(): Xóa phần tử cuối và trả về giá trị
- Front(): Truy cập phần tử đầu (không xóa)
- Back(): Truy cập phần tử cuối (không xóa)
- Empty(): Kiểm tra Deque có rỗng không
- Size(): Trả về số phần tử trong Deque

Trong Go, ta có thể dùng container/list
để giả lập deque hoặc viết một struct tuỳ chỉnh.
Dưới đây là một ví dụ deque tự cài đặt dể hiểu rõ tương tác (lưu ý cách implement)
package main
import (
"container/list"
"fmt"
)
type Deque struct {
data *list.List
}
func NewDeque() *Deque {
return &Deque{data: list.New()}
}
func (d *Deque) PushFront(val int) {
d.data.PushFront(val)
}
func (d *Deque) PushBack(val int) {
d.data.PushBack(val)
}
func (d *Deque) PopFront() int {
if d.data.Len() == 0 {
panic("PopFront on empty deque")
}
front := d.data.Front()
d.data.Remove(front)
return front.Value.(int)
}
func (d *Deque) PopBack() int {
if d.data.Len() == 0 {
panic("PopBack on empty deque")
}
back := d.data.Back()
d.data.Remove(back)
return back.Value.(int)
}
func (d *Deque) Front() int {
if d.data.Len() == 0 {
panic("Front on empty deque")
}
return d.data.Front().Value.(int)
}
func (d *Deque) Back() int {
if d.data.Len() == 0 {
panic("Back on empty deque")
}
return d.data.Back().Value.(int)
}
func (d *Deque) Empty() bool {
return d.data.Len() == 0
}
func (d *Deque) Size() int {
return d.data.Len()
}
Tính năng | Stack | Queue | Deque |
---|---|---|---|
Chèn đầu | ❌ | ❌ | ✅ |
Chèn cuối | ✅ | ✅ | ✅ |
Xóa đầu | ❌ | ✅ | ✅ |
Xóa cuối | ✅ | ❌ | ✅ |
Tính linh hoạt | Thấp | Trung bình | Cao |
Ứng dụng cấu trúc dữ liệu Deque trong thuật toán
Deque thường được dùng trong nhiều thuật toán tối ưu, đặc biệt là các bài toán cần giữ trạng thái linh hoạt với cửa sổ trượt (sliding window) hoặc hai đầu vào/ra.
Một số ví dụ ứng dụng
- Thuật toán tối ưu hóa Sliding Window Maximum: Dùng Deque để giữ chỉ số các phần tử có thể là max trong cửa sổ, đạt O(n).
- Thuật toán BFS 0-1 (Biến thể của thuật toán BFS): Áp dụng trong đồ thị có trọng số 0 và 1, giúp tìm đường đi ngắn nhất hiệu quả.
- Kiểm tra Palindrome: Vì có thể duyệt từ hai đầu nên dễ dàng so sánh các ký tự đối xứng.
- Thiết kế trình duyệt: Quản lý lịch sử tiến/lùi như một Deque.
- Điều phối tiến trình (Scheduling): Một số hệ điều hành sử dụng Deque để lên lịch tiến trình.
Lời kết
Deque là một cấu trúc dữ liệu đầy sức mạnh và linh hoạt, không chỉ hữu ích trong những thao tác đơn giản mà còn là chìa khóa để giải quyết nhiều bài toán thuộc dạng tối ưu. Để giữa vững nền tảng giải thuật, hãy chắc chắn rằng bạn đã nắm vững deque và cách dùng nó trong những tình huống thực tế.
Deque trở nên cực kỳ hữu ích trong bài toán Sliding Window Maximum hoặc Minimum. Giả sử bản muốn tìm max/min trong mỗi cửa sổ kích thước k
trên một dãy số. Bình thường cách duyệt bruteforce tốn O(nk). Nhưng với deque, ta có thể tối ưu xuống O(n).
Trong bài viết tiếp theo, tôi sẽ giải thích chi tiết cách dùng deque để xử lý Sliding Window Maximum và chứng minh tính đúng đắn về hiệu quả. Hãy theo dõi phần sau: Sliding Window Maximum – Cách dùng Deque để tối ưu và chứng minh.