Hàng đợi¶
Một hàng đợi (queue) là một cấu trúc dữ liệu tuyến tính tuân theo nguyên lý Vào trước Ra trước (First In, First Out - FIFO). Như tên gọi của nó, cấu trúc này mô phỏng cảnh mọi người xếp hàng: những người mới liên tục tham gia vào cuối hàng đợi, trong khi những người ở đầu hàng lần lượt rời đi.
Như được hiển thị trong hình bên dưới, chúng ta gọi đầu hàng đợi là đầu (front) và cuối hàng đợi là cuối (rear). Thao tác thêm một phần tử vào cuối hàng đợi được gọi là vào hàng đợi (enqueue), và thao tác loại bỏ phần tử ở đầu hàng đợi được gọi là ra hàng đợi (dequeue).
Các thao tác hàng đợi thông thường¶
Các thao tác thông thường trên một hàng đợi được hiển thị trong bảng dưới đây. Lưu ý rằng tên phương thức có thể khác nhau giữa các ngôn ngữ lập trình. Ở đây, chúng ta sử dụng cùng quy ước đặt tên như đối với ngăn xếp.
Bảng
| Phương thức | Mô tả | Độ phức tạp thời gian |
|---|---|---|
push() |
Vào hàng đợi, thêm phần tử vào cuối | \(O(1)\) |
pop() |
Ra hàng đợi, lấy phần tử đầu ra | \(O(1)\) |
peek() |
Truy cập phần tử đầu | \(O(1)\) |
Chúng ta có thể sử dụng trực tiếp các lớp hàng đợi do ngôn ngữ lập trình cung cấp:
from collections import deque
# Khởi tạo hàng đợi
# Trong Python, chúng ta thường sử dụng lớp deque làm hàng đợi
# Mặc dù queue.Queue() là lớp hàng đợi thuần túy, nhưng nó không thân thiện với người dùng nên không được khuyến nghị
que: deque[int] = deque()
# Vào hàng đợi (thêm phần tử vào cuối)
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)
# Truy cập phần tử đầu
front: int = que[0]
# Ra hàng đợi (lấy phần tử đầu ra)
pop: int = que.popleft()
# Lấy độ dài hàng đợi
size: int = len(que)
# Kiểm tra xem hàng đợi có trống không
is_empty: bool = len(que) == 0
/* Khởi tạo hàng đợi */
queue<int> queue;
/* Vào hàng đợi */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);
/* Truy cập phần tử đầu */
int front = queue.front();
/* Ra hàng đợi */
queue.pop();
/* Lấy độ dài hàng đợi */
int size = queue.size();
/* Kiểm tra xem hàng đợi có trống không */
bool empty = queue.empty();
/* Khởi tạo hàng đợi */
Queue<Integer> queue = new LinkedList<>();
/* Vào hàng đợi */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);
/* Truy cập phần tử đầu */
int peek = queue.peek();
/* Ra hàng đợi */
int pop = queue.poll();
/* Lấy độ dài hàng đợi */
int size = queue.size();
/* Kiểm tra xem hàng đợi có trống không */
boolean isEmpty = queue.isEmpty();
/* Khởi tạo hàng đợi */
Queue<int> queue = new();
/* Vào hàng đợi */
queue.Enqueue(1);
queue.Enqueue(3);
queue.Enqueue(2);
queue.Enqueue(5);
queue.Enqueue(4);
/* Truy cập phần tử đầu */
int peek = queue.Peek();
/* Ra hàng đợi */
int pop = queue.Dequeue();
/* Lấy độ dài hàng đợi */
int size = queue.Count;
/* Kiểm tra xem hàng đợi có trống không */
bool isEmpty = queue.Count == 0;
/* Khởi tạo hàng đợi */
// Trong Go, sử dụng list làm hàng đợi
queue := list.New()
/* Vào hàng đợi */
queue.PushBack(1)
queue.PushBack(3)
queue.PushBack(2)
queue.PushBack(5)
queue.PushBack(4)
/* Truy cập phần tử đầu */
peek := queue.Front()
/* Ra hàng đợi */
pop := queue.Front()
queue.Remove(pop)
/* Lấy độ dài hàng đợi */
size := queue.Len()
/* Kiểm tra xem hàng đợi có trống không */
isEmpty := queue.Len() == 0
/* Khởi tạo hàng đợi */
// Swift không có lớp hàng đợi tích hợp sẵn, có thể dùng Array làm hàng đợi
var queue: [Int] = []
/* Vào hàng đợi */
queue.append(1)
queue.append(3)
queue.append(2)
queue.append(5)
queue.append(4)
/* Truy cập phần tử đầu */
let peek = queue.first!
/* Ra hàng đợi */
// Vì đây là mảng nên removeFirst có độ phức tạp O(n)
let pool = queue.removeFirst()
/* Lấy độ dài hàng đợi */
let size = queue.count
/* Kiểm tra xem hàng đợi có trống không */
let isEmpty = queue.isEmpty
/* Khởi tạo hàng đợi */
// JavaScript không có hàng đợi tích hợp sẵn, có thể dùng Array làm hàng đợi
const queue = [];
/* Vào hàng đợi */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);
/* Truy cập phần tử đầu */
const peek = queue[0];
/* Ra hàng đợi */
// Cấu trúc bên dưới là mảng nên shift() có độ phức tạp thời gian O(n)
const pop = queue.shift();
/* Lấy độ dài hàng đợi */
const size = queue.length;
/* Kiểm tra xem hàng đợi có trống không */
const empty = queue.length === 0;
/* Khởi tạo hàng đợi */
// TypeScript không có hàng đợi tích hợp sẵn, có thể dùng Array làm hàng đợi
const queue: number[] = [];
/* Vào hàng đợi */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);
/* Truy cập phần tử đầu */
const peek = queue[0];
/* Ra hàng đợi */
// Cấu trúc bên dưới là mảng nên shift() có độ phức tạp thời gian O(n)
const pop = queue.shift();
/* Lấy độ dài hàng đợi */
const size = queue.length;
/* Kiểm tra xem hàng đợi có trống không */
const empty = queue.length === 0;
/* Khởi tạo hàng đợi */
// Trong Dart, lớp Queue là một hàng đợi hai đầu (deque) và cũng có thể dùng làm hàng đợi
Queue<int> queue = Queue();
/* Vào hàng đợi */
queue.add(1);
queue.add(3);
queue.add(2);
queue.add(5);
queue.add(4);
/* Truy cập phần tử đầu */
int peek = queue.first;
/* Ra hàng đợi */
int pop = queue.removeFirst();
/* Lấy độ dài hàng đợi */
int size = queue.length;
/* Kiểm tra xem hàng đợi có trống không */
bool isEmpty = queue.isEmpty;
/* Khởi tạo hàng đợi hai đầu (deque) */
// Trong Rust, sử dụng deque làm hàng đợi thông thường
let mut deque: VecDeque<u32> = VecDeque::new();
/* Vào hàng đợi */
deque.push_back(1);
deque.push_back(3);
deque.push_back(2);
deque.push_back(5);
deque.push_back(4);
/* Truy cập phần tử đầu */
if let Some(front) = deque.front() {
}
/* Ra hàng đợi */
if let Some(pop) = deque.pop_front() {
}
/* Lấy độ dài hàng đợi */
let size = deque.len();
/* Kiểm tra xem hàng đợi có trống không */
let is_empty = deque.is_empty();
/* Khởi tạo hàng đợi */
val queue = LinkedList<Int>()
/* Vào hàng đợi */
queue.offer(1)
queue.offer(3)
queue.offer(2)
queue.offer(5)
queue.offer(4)
/* Truy cập phần tử đầu */
val peek = queue.peek()
/* Ra hàng đợi */
val pop = queue.poll()
/* Lấy độ dài hàng đợi */
val size = queue.size
/* Kiểm tra xem hàng đợi có trống không */
val isEmpty = queue.isEmpty()
# Khởi tạo hàng đợi
# Hàng đợi tích hợp sẵn của Ruby (Thread::Queue) không có phương thức peek và duyệt, có thể dùng Array làm hàng đợi
queue = []
# Vào hàng đợi
queue.push(1)
queue.push(3)
queue.push(2)
queue.push(5)
queue.push(4)
# Truy cập phần tử đầu
peek = queue.first
# Ra hàng đợi
# Lưu ý rằng vì đây là mảng nên Array#shift có độ phức tạp thời gian O(n)
pop = queue.shift
# Lấy độ dài hàng đợi
size = queue.length
# Kiểm tra xem hàng đợi có trống không
is_empty = queue.empty?
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%E9%98%9F%E5%88%97%0A%20%20%20%20%23%20%E5%9C%A8%20Python%20%E4%B8%AD%EF%BC%8C%E6%88%91%E4%BB%AC%E4%B8%80%E8%88%AC%E5%B0%86%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97%E7%B1%BB%20deque%20%E7%9C%8B%E4%BD%9C%E9%98%9F%E5%88%97%E4%BD%BF%E7%94%A8%0A%20%20%20%20%23%20%E8%99%BD%E7%84%B6%20queue.Queue%28%29%20%E6%98%AF%E7%BA%AF%E6%AD%A3%E7%9A%84%E9%98%9F%E5%88%97%E7%B1%BB%EF%BC%8C%E4%BD%86%E4%B8%8D%E5%A4%AA%E5%A5%BD%E7%94%A8%0A%20%20%20%20que%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%20que.append%281%29%0A%20%20%20%20que.append%283%29%0A%20%20%20%20que.append%282%29%0A%20%20%20%20que.append%285%29%0A%20%20%20%20que.append%284%29%0A%20%20%20%20print%28%22%E9%98%9F%E5%88%97%20que%20%3D%22,%20que%29%0A%0A%20%20%20%20%23%20%E8%AE%BF%E9%97%AE%E9%98%9F%E9%A6%96%E5%85%83%E7%B4%A0%0A%20%20%20%20front%20%3D%20que%5B0%5D%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%0A%20%20%20%20%23%20%E5%85%83%E7%B4%A0%E5%87%BA%E9%98%9F%0A%20%20%20%20pop%20%3D%20que.popleft%28%29%0A%20%20%20%20print%28%22%E5%87%BA%E9%98%9F%E5%85%83%E7%B4%A0%20pop%20%3D%22,%20pop%29%0A%20%20%20%20print%28%22%E5%87%BA%E9%98%9F%E5%90%8E%20que%20%3D%22,%20que%29%0A%0A%20%20%20%20%23%20%E8%8E%B7%E5%8F%96%E9%98%9F%E5%88%97%E7%9A%84%E9%95%BF%E5%BA%A6%0A%20%20%20%20size%20%3D%20len%28que%29%0A%20%20%20%20print%28%22%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%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%28que%29%20%3D%3D%200%0A%20%20%20%20print%28%22%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¶
Để triển khai một hàng đợi, chúng ta cần một cấu trúc dữ liệu cho phép thêm các phần tử ở một đầu và loại bỏ các phần tử ở đầu kia. Cả danh sách liên kết và mảng đều đáp ứng yêu cầu này.
Triển khai bằng Danh sách liên kết¶
Như được hiển thị trong hình dưới đây, chúng ta có thể coi "nút đầu" (head node) và "nút đuôi" (tail node) của danh sách liên kết lần lượt là "đầu" và "cuối" của hàng đợi, với quy tắc các nút chỉ có thể được thêm vào cuối và loại bỏ ở đầu.
Dưới đây là mã nguồn ví dụ để triển khai một hàng đợi sử dụng danh sách liên kết:
Triển khai bằng Mảng¶
Xóa phần tử đầu tiên trong một mảng có độ phức tạp thời gian là \(O(n)\), điều này làm cho thao tác ra hàng đợi không hiệu quả. Tuy nhiên, chúng ta có thể sử dụng phương pháp khéo léo sau đây để tránh vấn đề này.
Chúng ta có thể sử dụng một biến front để trỏ đến chỉ số của phần tử đầu và duy trì một biến size để ghi lại độ dài của hàng đợi. Chúng ta định nghĩa rear = front + size, tính toán vị trí ngay sau phần tử cuối.
Dựa trên thiết kế này, khoảng hợp lệ chứa các phần tử trong mảng là [front, rear - 1]. Các phương pháp triển khai cho các thao tác khác nhau được hiển thị trong hình bên dưới:
- Thao tác vào hàng đợi: Gán phần tử đầu vào cho chỉ số
rearvà tăngsizethêm 1. - Thao tác ra hàng đợi: Chỉ cần tăng
frontthêm 1 và giảmsizeđi 1.
Như bạn có thể thấy, cả hai thao tác vào hàng đợi và ra hàng đợi đều chỉ yêu cầu một bước tính toán, với độ phức tạp thời gian là \(O(1)\).
Bạn có thể nhận ra một vấn đề: khi chúng ta liên tục vào hàng đợi và ra hàng đợi, cả front và rear đều dịch chuyển sang phải. Khi chúng chạm tới cuối mảng, chúng không thể tiếp tục di chuyển. Để giải quyết vấn đề này, chúng ta có thể coi mảng đó là một mảng vòng (circular array) với đầu và đuôi được kết nối với nhau.
Đối với một mảng vòng, chúng ta cần để front hoặc rear quay về đầu mảng khi chúng vượt quá điểm cuối. Quy luật tuần hoàn này có thể được triển khai bằng cách sử dụng phép chia lấy dư (modulo operation), như được hiển thị trong đoạn mã dưới đây:
Hàng đợi được triển khai ở trên vẫn có những hạn chế: độ dài của nó là bất biến. Tuy nhiên, vấn đề này không khó giải quyết. Chúng ta có thể thay thế mảng bằng một mảng động để giới thiệu cơ chế mở rộng. Độc giả quan tâm có thể thử tự triển khai điều này.
Các kết luận so sánh cho hai cách triển khai này nhất quán với kết luận của ngăn xếp và sẽ không được lặp lại ở đây.
Các ứng dụng điển hình của Hàng đợi¶
- Đơn hàng thương mại điện tử. Sau khi người mua đặt hàng, các đơn hàng sẽ được thêm vào một hàng đợi, và hệ thống sau đó sẽ xử lý các đơn hàng trong hàng đợi theo thứ tự của chúng. Trong các đợt khuyến mãi lớn, lượng đơn hàng khổng lồ được tạo ra trong thời gian ngắn và tính đồng thời cao (high concurrency) trở thành một thách thức lớn mà các kỹ sư cần giải quyết.
- Các tác vụ cần xử lý. Bất kỳ tình huống nào cần thực hiện tính năng "đến trước, phục vụ trước" (first come, first served), chẳng hạn như hàng đợi tác vụ của máy in hoặc hàng đợi gọi món của nhà hàng, đều có thể duy trì thứ tự xử lý một cách hiệu quả bằng cách sử dụng hàng đợi.