Hàng đợi hai đầu¶
Trong một hàng đợi, chúng ta chỉ có thể loại bỏ các phần tử từ đầu hoặc thêm các phần tử ở cuối. Như được hiển thị trong hình bên dưới, một hàng đợi hai đầu (double-ended queue - deque) cung cấp tính linh hoạt cao hơn, cho phép thêm hoặc loại bỏ các phần tử ở cả hai đầu.
Các thao tác hàng đợi hai đầu thông thường¶
Các thao tác thông thường trên một hàng đợi hai đầu được hiển thị trong bảng dưới đây. Tên phương thức cụ thể phụ thuộc vào ngôn ngữ lập trình được sử dụng.
Bảng
| Phương thức | Mô tả | Độ phức tạp thời gian |
|---|---|---|
push_first() |
Thêm phần tử vào đầu | \(O(1)\) |
push_last() |
Thêm phần tử vào cuối | \(O(1)\) |
pop_first() |
Loại bỏ phần tử đầu | \(O(1)\) |
pop_last() |
Loại bỏ phần tử cuối | \(O(1)\) |
peek_first() |
Truy cập phần tử đầu | \(O(1)\) |
peek_last() |
Truy cập phần tử cuối | \(O(1)\) |
Tương tự, chúng ta có thể sử dụng trực tiếp các lớp hàng đợi hai đầu do ngôn ngữ lập trình cung cấp:
from collections import deque
# Khởi tạo hàng đợi hai đầu
deq: deque[int] = deque()
# Vào hàng đợi hai đầu
deq.append(2) # Thêm vào cuối
deq.append(5)
deq.append(4)
deq.appendleft(3) # Thêm vào đầu
deq.appendleft(1)
# Truy cập các phần tử
front: int = deq[0] # Phần tử đầu
rear: int = deq[-1] # Phần tử cuối
# Ra hàng đợi hai đầu
pop_front: int = deq.popleft() # Ra hàng đợi từ đầu
pop_rear: int = deq.pop() # Ra hàng đợi từ cuối
# Lấy độ dài hàng đợi hai đầu
size: int = len(deq)
# Kiểm tra xem hàng đợi hai đầu có trống không
is_empty: bool = len(deq) == 0
/* Khởi tạo hàng đợi hai đầu */
deque<int> deque;
/* Vào hàng đợi hai đầu */
deque.push_back(2); // Thêm vào cuối
deque.push_back(5);
deque.push_back(4);
deque.push_front(3); // Thêm vào đầu
deque.push_front(1);
/* Truy cập các phần tử */
int front = deque.front(); // Phần tử đầu
int back = deque.back(); // Phần tử cuối
/* Ra hàng đợi hai đầu */
deque.pop_front(); // Ra hàng đợi từ đầu
deque.pop_back(); // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
int size = deque.size();
/* Kiểm tra xem hàng đợi hai đầu có trống không */
bool empty = deque.empty();
/* Khởi tạo hàng đợi hai đầu */
Deque<Integer> deque = new LinkedList<>();
/* Vào hàng đợi hai đầu */
deque.offerLast(2); // Thêm vào cuối
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3); // Thêm vào đầu
deque.offerFirst(1);
/* Truy cập các phần tử */
int peekFirst = deque.peekFirst(); // Phần tử đầu
int peekLast = deque.peekLast(); // Phần tử cuối
/* Ra hàng đợi hai đầu */
int popFirst = deque.pollFirst(); // Ra hàng đợi từ đầu
int popLast = deque.pollLast(); // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
int size = deque.size();
/* Kiểm tra xem hàng đợi hai đầu có trống không */
boolean isEmpty = deque.isEmpty();
/* Khởi tạo hàng đợi hai đầu */
// Trong C#, sử dụng LinkedList làm hàng đợi hai đầu
LinkedList<int> deque = new();
/* Vào hàng đợi hai đầu */
deque.AddLast(2); // Thêm vào cuối
deque.AddLast(5);
deque.AddLast(4);
deque.AddFirst(3); // Thêm vào đầu
deque.AddFirst(1);
/* Truy cập các phần tử */
int peekFirst = deque.First.Value; // Phần tử đầu
int peekLast = deque.Last.Value; // Phần tử cuối
/* Ra hàng đợi hai đầu */
deque.RemoveFirst(); // Ra hàng đợi từ đầu
deque.RemoveLast(); // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
int size = deque.Count;
/* Kiểm tra xem hàng đợi hai đầu có trống không */
bool isEmpty = deque.Count == 0;
/* Khởi tạo hàng đợi hai đầu */
// Trong Go, sử dụng list làm hàng đợi hai đầu
deque := list.New()
/* Vào hàng đợi hai đầu */
deque.PushBack(2) // Thêm vào cuối
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3) // Thêm vào đầu
deque.PushFront(1)
/* Truy cập các phần tử */
front := deque.Front() // Phần tử đầu
rear := deque.Back() // Phần tử cuối
/* Ra hàng đợi hai đầu */
deque.Remove(front) // Ra hàng đợi từ đầu
deque.Remove(rear) // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
size := deque.Len()
/* Kiểm tra xem hàng đợi hai đầu có trống không */
isEmpty := deque.Len() == 0
/* Khởi tạo hàng đợi hai đầu */
// Swift không có lớp hàng đợi hai đầu tích hợp sẵn, có thể dùng Array làm hàng đợi hai đầu
var deque: [Int] = []
/* Vào hàng đợi hai đầu */
deque.append(2) // Thêm vào cuối
deque.append(5)
deque.append(4)
deque.insert(3, at: 0) // Thêm vào đầu
deque.insert(1, at: 0)
/* Truy cập các phần tử */
let peekFirst = deque.first! // Phần tử đầu
let peekLast = deque.last! // Phần tử cuối
/* Ra hàng đợi hai đầu */
// Khi sử dụng mảng mô phỏng, popFirst có độ phức tạp O(n)
let popFirst = deque.removeFirst() // Ra hàng đợi từ đầu
let popLast = deque.removeLast() // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
let size = deque.count
/* Kiểm tra xem hàng đợi hai đầu có trống không */
let isEmpty = deque.isEmpty
/* Khởi tạo hàng đợi hai đầu */
// JavaScript không có hàng đợi hai đầu tích hợp sẵn, chỉ có thể sử dụng Array làm hàng đợi hai đầu
const deque = [];
/* Vào hàng đợi hai đầu */
deque.push(2);
deque.push(5);
deque.push(4);
// Lưu ý rằng vì đây là mảng nên unshift() có độ phức tạp thời gian O(n)
deque.unshift(3);
deque.unshift(1);
/* Truy cập các phần tử */
const peekFirst = deque[0];
const peekLast = deque[deque.length - 1];
/* Ra hàng đợi hai đầu */
// Lưu ý rằng vì đây là mảng nên shift() có độ phức tạp thời gian O(n)
const popFront = deque.shift();
const popBack = deque.pop();
/* Lấy độ dài hàng đợi hai đầu */
const size = deque.length;
/* Kiểm tra xem hàng đợi hai đầu có trống không */
const isEmpty = size === 0;
/* Khởi tạo hàng đợi hai đầu */
// TypeScript không có hàng đợi hai đầu tích hợp sẵn, chỉ có thể sử dụng Array làm hàng đợi hai đầu
const deque: number[] = [];
/* Vào hàng đợi hai đầu */
deque.push(2);
deque.push(5);
deque.push(4);
// Lưu ý rằng vì đây là mảng nên unshift() có độ phức tạp thời gian O(n)
deque.unshift(3);
deque.unshift(1);
/* Truy cập các phần tử */
const peekFirst: number = deque[0];
const peekLast: number = deque[deque.length - 1];
/* Ra hàng đợi hai đầu */
// Lưu ý rằng vì đây là mảng nên shift() có độ phức tạp thời gian O(n)
const popFront: number = deque.shift() as number;
const popBack: number = deque.pop() as number;
/* Lấy độ dài hàng đợi hai đầu */
const size: number = deque.length;
/* Kiểm tra xem hàng đợi hai đầu có trống không */
const isEmpty: boolean = size === 0;
/* Khởi tạo hàng đợi hai đầu */
// Trong Dart, Queue được định nghĩa là một hàng đợi hai đầu
Queue<int> deque = Queue<int>();
/* Vào hàng đợi hai đầu */
deque.addLast(2); // Thêm vào cuối
deque.addLast(5);
deque.addLast(4);
deque.addFirst(3); // Thêm vào đầu
deque.addFirst(1);
/* Truy cập các phần tử */
int peekFirst = deque.first; // Phần tử đầu
int peekLast = deque.last; // Phần tử cuối
/* Ra hàng đợi hai đầu */
int popFirst = deque.removeFirst(); // Ra hàng đợi từ đầu
int popLast = deque.removeLast(); // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
int size = deque.length;
/* Kiểm tra xem hàng đợi hai đầu có trống không */
bool isEmpty = deque.isEmpty;
/* Khởi tạo hàng đợi hai đầu */
let mut deque: VecDeque<u32> = VecDeque::new();
/* Vào hàng đợi hai đầu */
deque.push_back(2); // Thêm vào cuối
deque.push_back(5);
deque.push_back(4);
deque.push_front(3); // Thêm vào đầu
deque.push_front(1);
/* Truy cập các phần tử */
if let Some(front) = deque.front() { // Phần tử đầu
}
if let Some(rear) = deque.back() { // Phần tử cuối
}
/* Ra hàng đợi hai đầu */
if let Some(pop_front) = deque.pop_front() { // Ra hàng đợi từ đầu
}
if let Some(pop_rear) = deque.pop_back() { // Ra hàng đợi từ cuối
}
/* Lấy độ dài hàng đợi hai đầu */
let size = deque.len();
/* Kiểm tra xem hàng đợi hai đầu có trống không */
let is_empty = deque.is_empty();
/* Khởi tạo hàng đợi hai đầu */
val deque = LinkedList<Int>()
/* Vào hàng đợi hai đầu */
deque.offerLast(2) // Thêm vào cuối
deque.offerLast(5)
deque.offerLast(4)
deque.offerFirst(3) // Thêm vào đầu
deque.offerFirst(1)
/* Truy cập các phần tử */
val peekFirst = deque.peekFirst() // Phần tử đầu
val peekLast = deque.peekLast() // Phần tử cuối
/* Ra hàng đợi hai đầu */
val popFirst = deque.pollFirst() // Ra hàng đợi từ đầu
val popLast = deque.pollLast() // Ra hàng đợi từ cuối
/* Lấy độ dài hàng đợi hai đầu */
val size = deque.size
/* Kiểm tra xem hàng đợi hai đầu có trống không */
val isEmpty = deque.isEmpty()
# Khởi tạo hàng đợi hai đầu
# Ruby không có hàng đợi hai đầu tích hợp sẵn, chỉ có thể sử dụng Array làm hàng đợi hai đầu
deque = []
# Vào hàng đợi hai đầu
deque << 2
deque << 5
deque << 4
# Lưu ý rằng vì đây là mảng nên Array#unshift có độ phức tạp thời gian O(n)
deque.unshift(3)
deque.unshift(1)
# Truy cập các phần tử
peek_first = deque.first
peek_last = deque.last
# Ra hàng đợi hai đầu
# Lưu ý rằng vì đây là mảng nên Array#shift có độ phức tạp thời gian O(n)
pop_front = deque.shift
pop_back = deque.pop
# Lấy độ dài hàng đợi hai đầu
size = deque.length
# Kiểm tra xem hàng đợi hai đầu có trống không
is_empty = size.zero?
Trực quan hóa mã nguồn
https://pythontutor.com/render.html#code=from%20collections%20import%20deque%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%0A%20%20%20%20deq%20%3D%20deque%28%29%0A%0A%20%20%20%20%23%20%E5%85%83%E7%B4%A0%E5%85%A5%E9%98%9F%0A%20%20%20%20deq.append%282%29%20%20%23%20%E6%B7%BB%E5%8A%A0%E8%87%B3%E9%98%9F%E5%B0%BE%0A%20%20%20%20deq.append%285%29%0A%20%20%20%20deq.append%284%29%0A%20%20%20%20deq.appendleft%283%29%20%20%23%20%E6%B7%BB%E5%8A%A0%E8%87%B3%E9%98%9F%E9%A6%96%0A%20%20%20%20deq.appendleft%281%29%0A%20%20%20%20print%28%22%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%20deque%20%3D%22,%20deq%29%0A%0A%20%20%20%20%23%20%E8%AE%BF%E9%97%AE%E5%85%83%E7%B4%A0%0A%20%20%20%20front%20%3D%20deq%5B0%5D%20%20%23%20%E9%98%9F%E9%A6%96%E5%85%83%E7%B4%A0%0A%20%20%20%20print%28%22%E9%98%9F%E9%A6%96%E5%85%83%E7%B4%A0%20front%20%3D%22,%20front%29%0A%20%20%20%20rear%20%3D%20deq%5B-1%5D%20%20%23%20%E9%98%9F%E5%B0%BE%E5%85%83%E7%B4%A0%0A%20%20%20%20print%28%22%E9%98%9F%E5%B0%BE%E5%85%83%E7%B4%A0%20rear%20%3D%22,%20rear%29%0A%0A%20%20%20%20%23%20%E5%85%83%E7%B4%A0%E5%87%BA%E9%98%9F%0A%20%20%20%20pop_front%20%3D%20deq.popleft%28%29%20%20%23%20%E9%98%9F%E9%A6%96%E5%85%83%E7%B4%A0%E5%87%BA%E9%98%9F%0A%20%20%20%20print%28%22%E9%98%9F%E9%A6%96%E5%87%BA%E9%98%9F%E5%85%83%E7%B4%A0%20%20pop_front%20%3D%22,%20pop_front%29%0A%20%20%20%20print%28%22%E9%98%9F%E9%A6%96%E5%87%BA%E9%98%9F%E5%90%8E%20deque%20%3D%22,%20deq%29%0A%20%20%20%20pop_rear%20%3D%20deq.pop%28%29%20%20%23%20%E9%98%9F%E5%B0%BE%E5%85%83%E7%B4%A0%E5%87%BA%E9%98%9F%0A%20%20%20%20print%28%22%E9%98%9F%E5%B0%BE%E5%87%BA%E9%98%9F%E5%85%83%E7%B4%A0%20%20pop_rear%20%3D%22,%20pop_rear%29%0A%20%20%20%20print%28%22%E9%98%9F%E5%B0%BE%E5%87%BA%E9%98%9F%E5%90%8E%20deque%20%3D%22,%20deq%29%0A%0A%20%20%20%20%23%20%E8%8E%B7%E5%8F%96%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%E7%9A%84%E9%95%BF%E5%BA%A6%0A%20%20%20%20size%20%3D%20len%28deq%29%0A%20%20%20%20print%28%22%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%E9%95%BF%E5%BA%A6%20size%20%3D%22,%20size%29%0A%0A%20%20%20%20%23%20%E5%88%A4%E6%96%AD%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%0A%20%20%20%20is_empty%20%3D%20len%28deq%29%20%3D%3D%200%0A%20%20%20%20print%28%22%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%20%3D%22,%20is_empty%29&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Triển khai Hàng đợi hai đầu *¶
Cách triển khai của hàng đợi hai đầu tương tự như của hàng đợi. Bạn có thể chọn danh sách liên kết hoặc mảng làm cấu trúc dữ liệu bên dưới.
Triển khai bằng Danh sách liên kết đôi¶
Xem lại phần trước, chúng ta đã sử dụng một danh sách liên kết đơn thông thường để triển khai hàng đợi vì nó cho phép xóa nút đầu một cách thuận tiện (tương ứng với ra hàng đợi) và thêm các nút mới sau nút đuôi (tương ứng với vào hàng đợi).
Đối với hàng đợi hai đầu, cả đầu và cuối đều có thể thực hiện thao tác vào hàng đợi và ra hàng đợi. Nói cách khác, hàng đợi hai đầu cũng cần triển khai các thao tác theo hướng ngược lại. Vì lý do này, chúng ta sử dụng một danh sách liên kết đôi (doubly linked list) làm cấu trúc dữ liệu bên dưới cho hàng đợi hai đầu.
Như hiển thị trong hình bên dưới, chúng ta coi các nút đầu và cuối của danh sách liên kết đôi lần lượt là đầu và cuối của hàng đợi hai đầu, triển khai tính năng thêm và loại bỏ các nút ở cả hai đầu.
Mã nguồn triển khai được hiển thị bên dưới:
Triển khai bằng Mảng¶
Như được hiển thị trong hình dưới đây, tương tự như triển khai hàng đợi dựa trên mảng, chúng ta cũng có thể sử dụng một mảng vòng để triển khai hàng đợi hai đầu.
Dựa trên cách triển khai hàng đợi, chúng ta chỉ cần thêm các phương thức "vào hàng đợi từ đầu" và "ra hàng đợi từ cuối":
Ứng dụng của Hàng đợi hai đầu¶
Hàng đợi hai đầu kết hợp logic của cả ngăn xếp và hàng đợi. Do đó, nó có thể triển khai tất cả các kịch bản ứng dụng của cả hai, đồng thời mang lại tính linh hoạt cao hơn.
Chúng ta biết rằng tính năng "hoàn tác" (undo) trong phần mềm thường được triển khai bằng ngăn xếp: hệ thống đẩy từng thao tác thay đổi vào ngăn xếp và sau đó thực hiện hoàn tác thông qua pop. Tuy nhiên, xem xét giới hạn tài nguyên hệ thống, phần mềm thường giới hạn số bước hoàn tác (ví dụ: chỉ cho phép lưu 50 bước). Khi độ dài ngăn xếp vượt quá 50, phần mềm cần thực hiện thao tác xóa ở đáy ngăn xếp (đầu hàng đợi). Nhưng ngăn xếp không thể triển khai tính năng này, vì vậy cần có một hàng đợi hai đầu để thay thế ngăn xếp. Lưu ý rằng logic cốt lõi của "hoàn tác" vẫn tuân theo nguyên lý LIFO của ngăn xếp; chỉ là hàng đợi hai đầu có thể triển khai một số logic bổ sung linh hoạt hơn.