Hàng đợi hai đầu (deque) là cấu trúc dữ liệu chứa 0 hoặc nhiều phần tử có cùng kiểu dữ liệu và được biểu diễn bằng một hàng có phần tử đầu (front) và phần tử cuối (last). Deque hỗ trợ 4 thao tác như sau:
Về ứng dụng, ta sẽ bổ sung thêm một số thao tác sau:
Hai thao tác lấy giá trị thật sự không cần thiết, bởi lấy giá trị phần tử đầu deque (peek front) tương đương với việc xóa đi phần tử đó (pop front) rồi lại thêm nó vào (push front), và tương tự với lấy giá trị phần tử cuối (peek last). Cũng như kiểm tra rỗng (Test empty) thật ra cũng chỉ là kiểm tra xem số lượng phần tử của deque có bằng 0 hay không.
Thuật ngữ deque là cách gọn ngắn tắt của double-ended queue (hàng đợi hai đầu). Sở dĩ là vì nó có thể thêm, bớt phần tử ở cả hai đầu; còn thuật ngữ queue ở đây là một lớp cấu trúc dữ liệu cho phép thêm, bớt phần tử (nhưng không thể tìm kiếm). Một phần tử được xem là đứng trước một phần tử khác nếu nó gần với phần tử đầu (front) hơn là phần tử còn lại; ngược, lại, một phần tử được xem là đứng sau một phần tử khác nếu nó xa với phần tử đầu (front) hơn là phần tử còn lại. Push một phần tử là thêm phần tử đó vào hàng đợi, pop đẩy ra một phần tử. Lưu ý rằng điểm đầu (front) và điểm cuối (last) là tương đương nhau, khi thay đổi toàn bộ điểm cuối và đầu trong giải thuật của chúng ta thì nó vẫn hoạt động tương tự như trước đó.
Khi sử dụng mảng để biển diễn deque, thì giá trị của deque sẽ được lưu giữ bằng những phần tử liên tiếp trong mảng. Tuy nhiên, đối vấn cách cài đặt này, thì nếu ta muốn đặt phần tử có chỉ số thấp nhất (front) luôn luôn cố định ở một chỉ số (ví dụ $0$ hoặc $1$), hay nói cách khác, chỉ số thấp nhất luôn là cố định thì: Khi ta muốn pop front (thêm phần tử phía trước vào đầu hàng đợi), ta sẽ phải tịnh tiến toàn bộ các phần tử về bên trái sao cho phần tử có chỉ số thấp nhất (front) sẽ lưu giá trị của phần tử tiếp theo (next) và tương tự với các phần tử còn lại. Cũng như đối với việc push front (thêm phần tử vào đầu hàng đợi), toàn bộ những phần tử hiện tại trong deque sẽ phải tịnh tiến về bên phải để phần tử chỉ số thấp nhất (front) sẽ lưu giá trị của phần tử vừa thêm vào, trong khi các phần tử còn lại sẽ lưu phần tử đứng trước. Thế nên, với cách cài đặt thế này, mỗi thao tác thực hiện sẽ tốn chi phí là $O(n)$ - với $n$ là số lượng phần tử hiện đang có của deque.
Tuy nhiên, để có thể thực hiện một số thuật toán quan trọng như BFS trong thời gian tuyến tính, các thao tác push, pop phải được thực hiện với chi phí là $O(1)$. Đối với vấn đề này, thay vì phải thay thế phần tử bị pop, ta chỉ đơn thuần thay đổi chỉ số của front, và khi push vào một phần tử, ta chỉ cần gán phần tử vào chỉ số liền kề với phần tử đứng đầu và thay đổi chỉ số của phần tử đầu. Tức là, ta chỉ cần quan tâm đến hai chỉ số của mảng, đầu (front) và cuối (back). Khi ta thêm một phần tử vào đầu (push front), ta chỉ cần giảm chỉ số đầu (front index) rồi gán phần tử ấy vào chỉ số mới. Ngược lại khi ta thêm một phần tử vào cuối (push back), ta chỉ cần tăng chỉ số đầu (back index) rồi gán phần tử ấy vào. Còn khi ta ta xóa một phần tử ở đầu (pop front), ta chỉ việc tăng chỉ số đầu, còn xóa phần tử ở cuối (pop back) thì ta sẽ giảm chỉ số cuối.
Hãy thử nghĩ xem, trong trường hợp ta thêm một phần tử vào đầu (push front), rồi lại xóa đi phần tử cuối (pop back), rồi thêm lại phần tử đầu (push front), … Tiếp tục như vậy, deque mà ta xây dựng vẫn luôn luôn chỉ có tối đa một phần tử, thế nhưng hai chỉ số đầu và chỉ số cuối lại tăng lên liên tục dẫn tới việc bị tràn giới hạn mảng. Để khắc phục vấn đề này, ta sẽ cho phép các chỉ số được xoay vòng (hàng đợi hai đầu xoay vòng). Thế nên, khi tăng chỉ số cực hạn lên, ta sẽ nhận được chỉ số cực tiểu và ngược lại, khi giảm chỉ số cực tiểu ta sẽ nhận được chỉ số cực đại. Việc này được thực hiện bằng cách sử dụng toán tử mod (modulo - %). Dưới đây sẽ là một cách cài đặt mẫu bằng mã giả:
cấu trúc deque
thủ tục construct(max_size)
gán A là một mảng có tối đa max_size+1 phần tử
gán N = max_size+1
gán first = 0
gán last = 0
thủ tục push_front(x)
first = (first - 1) mod N
A[first] = x
thủ tục push_back(x)
A[last] = x
last = (last + 1) mod N
hàm pop_front
return_val = A[first]
first = (first + 1) mod N
trả về return_val
hàm pop_back
last = (last - 1) mod N
trả về A[last]
hàm peek_front
trả về A[first]
hàm peek_back
trả về A[(last-1) mod N]
hàm size
trả về (last-first) mod N
thủ tục make_empty
last = firstcấu trúc deque
thủ tục construct
gán L là một danh sách rỗng
thủ tục push_front(x)
chèn x vào đầu của L
thủ tục push_back(x)
chèn x vào cuối L
hàm pop_front
xóa phần tử đầu của L, trả về giá trị của phần tử đó
hàm pop_back
xóa phần tử cuối của L, trả về giá trị của phần tử đó
hàm peek_front
trả về giá trị của phần tử đầu L
hàm peek_back
trả về giá trị của phần tử cuối L
hàm size
trả về kích thước của L
thủ tục make_empty
làm rỗng Ldeque nằm trong tiêu đề <deque>, là một cấu trúc dữ liệu có khả năng chứa mọi kiểu dữ liệu (cố định), và kiểu dữ liệu này xem được xem như một thông số mẫu. Do đó, ví dụ như deque<char> là một hàng đợi hai đầu chứa các ký tự. Cấu trúc dữ liệu này cho phép sử dụng các hàm sau: (lưu ý rằng T là kiểu dữ liệu mà hàng đợi đó lưu trữ)void push_front(const T& x): thêm x vào đầu deque.void push_back(const T& x): thêm x vào cuối deque.void pop_front(): xóa phần tử đầu khỏi deque.void pop_back(): xóa phần tử cuối khỏi deque.T& front(): trả về giá trị đầu deque.T& back(): trả về giá trị cuối deque.size_type size(): trả về số lượng phần tử hiện tại trong deque.bool empty(): trả về giá trị true nếu deque rỗng và ngược lại, false nếu deque có phần tử.void clear(): xóa toàn bộ phần tử trong deque.Ngoài ra, không giống như cấu trúc dữ liệu STD queue và stack, cấu trúc dữ liệu deque lưu địa chỉ của các phần tử một cách ngẫu nhiên: do đó, D[0] sẽ đại diện cho phần tử đứng đầu D, và tương tự như thế với các phần tử tiếp theo.
Cấu trúc dữ liệu deque nên dùng bất cứ khi nào mà nó có thể chứ đủ các phần tử cần thiết; bởi sử dụng nó sẽ nhanh và ít lỗi hơn so với việc bạn tự cài đặt lại. Trong khi đó, hầu như bạn không bao giờ phải đối mặt với một vấn đề gì mà STD deque vẫn không chạy đủ nhanh.
Lưu ý rằng thao tác pop được định nghĩa trong cấu trúc dữ liệu deque chỉ xóa đi phần tử đó nhưng không trả về giá trị của nó. Để lấy được giá trị của nó rồi xóa, ta sẽ thực hiện cả hai thao tác gọi front hoặc back và sau đó thì pop_front hoặc pop_back.
Các cấu trúc dữ liệu STD queue và stack, trừ khi bị ghi đè lên các đối số, thì chỉ là một phần của cấu trúc dữ liệu deque thôi. Bởi vì các tính chất của stack và queue chỉ là một phần của deque, nên ta có thể dễ dàng tạo ra nó bằng cách giới hạn những thao tác deque.