Chào ace, bài này chúng ta sẽ tìm hiểu về Cấu trúc dữ liệu Deque trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Deque hay Double Ended Queue là một phiên bản suy rộng của cấu trúc dữ liệu Queue mà cho phép thực hiện chèn thêm phần tử mới và xóa phần tử, ở cả hai đầu của hàng đợi.
Nội dung chính
1. Các thao tác xử lý dữ liệu trên Deque
Về cơ bản, 4 thao tác căn bản sau sẽ được thực hiện trên cấu trúc dữ liệu Deque:
– insertFront(): Chèn thêm một phần tử mới vào đầu Deque
– insertLast(): Chèn thêm một phần tử mới vào cuối Deque
– deleteFront(): Xóa đi một phần tử nằm ở đầu Deque
– deleteLast(): Xóa đi một phần tử nằm ở cuối Deque
Ngoài các thao tác căn bản ở trên, thì các thao tác xử lý dữ liệu sau đây cũng được hỗ trợ trên Deque:
– getFront(): Lấy ra phần tử nằm ở đầu Deque
– getRear(): Lấy ra phần tử nằm ở cuối Deque
– isEmpty(): Kiểm tra xem liệu rằng Deque có trống hay không
– isFull() Kiểm tra xem liệu rằng Deque đã đầy chưa.
2. Các ứng dụng của Deque
Bởi vì cấu trúc dữ liệu Deque hỗ trợ cả các thao tác xử lý dữ liệu liên quan đến Stack – Ngăn xếp và Queue – Hàng đợi, nên nó (cấu trúc dữ liệu Deque) có thể được sử dụng như cả hai (tức là Deque có thể được sử dụng như là Stack hoặc Queue đều được). Cấu trúc dữ liệu Deque cho phép xử lý dữ liệu ở cả hai đầu của hàng đợi với độ phức tạp O(1), điều này rất hữu ích trong các ứng dụng nhất định.
Ngoài ra, các vấn đề liên quan đến việc các phần tử cần phải được xóa bỏ và/hoặc được chèn thêm vào ở cả hai đầu của hàng đợi, đều có thể được giải quyết một cách hiệu quả bằng cách sử dụng Deque. Để thấy được điều này, các bạn có thể tham khảo trong các link sau:
– Giải quyết vấn đề tìm giá trị lớn nhất của các mảng con có kích thước cụ thể:
– 0-1 BFS (Tìm đường đi ngắn nhất trong một đồ thị có trọng số nhị phân):
– Tìm đường đi theo hình vòng tròn đầu tiên mà đi qua tất cả các máy bơm xăng:
3. Deque được tích hợp sẵn trong các ngôn ngữ lập trình
C++ STL có cung cấp sẵn Deque thông qua thư viện std::deque và Java thì cung cấp thông qua interface Deque, ngoài ra Python cũng hỗ trợ sẵn Deque.
4. Cài đặt Deque
Cấu trúc dữ liêu Deque có thể được cài đặt bằng cách sử dụng Doubly Linked List – Danh sách liên kết kép hoặc Circular array – Mảng vòng. Trong cả hai phương pháp trên, chúng ta đều có thể cài đặt tất cả các thao tác xử lý dữ liệu trên Deque với độ phức tạp về thời gian là O(1).
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ...)){kind=link}