Một số ứng dụng của CTDL Queue
Giới thiệu
Queue thực ra là một danh sách phần tử hay một mảng với một số tương tác đặc thù. Để dễ hình dung, bạn có thể tưởng tượng nó giống như một cái ống thông 2 đầu, bạn nhét các phần tử vào 1 đầu và lấy ra ở đầu kia. Điều này nghĩa là phần tử nào đưa vào trước thì nó sẽ bị gỡ ra trước (FIFO - Last In First Out). Hai phương thức chính của queue là enqueue và dequeue mô tả cho các hành động này
Enqueue(x): đưa phần tử x vào trong queue.
Dequeue(): lấy một phần tử ra khỏi queue
Ví dụ: Bạn có queue Q gồm các phần tử sắp thứ tự {a,b,c,d}. Nếu thực hiện Q.enqueue(z) thì Q={z,a,b,c,d} và nếu x=Q.dequeue() thì x sẽ mang giá trị là d và Q={z,a,b,c} vì phần tử d ở cuối đã bị gỡ bỏ.
Ứng dụng 1 - Xây dựng cây Merkle
Để tìm hiểu kỹ hơn cây Merkle là gì nếu bạn chưa rõ, bạn có thể vào bài viết này để tìm hiểu.
Thuật toán: Xây dựng cấu trúc cây Merkle từ danh sách các phần tử L
Cho Q = null
Enqueue tất cả phần tử của L vào Q
Lặp:
Nếu Q có dưới 2 phần tử: ngừng lặp
Gán leftNode = Q.dequeue()
Gán rightNode = Q.dequeue()
Gán parentNode = new Node(leftNode, rightNode)
Đưa parentNode vào Q: Q.enqueue(parentNode)
return Q[0] là phần tử đầu tiên của Q
Ứng dụng 2 - Tìm đường ngắn nhất trong bảng vuông
Tìm đường đi ngắn nhất (shortest path) từ start đến end như hình vẽ với điều kiện mỗi bước chỉ đi vào một trong 4 ô liền kề: trên, hoặc dưới, hoặc trái, hoặc phải. Đây là bài toán mà các bạn sẽ rất hay gặp trong khi làm các dòng arcade game như Lines, hoặc thậm chí một số loại game chiến thuật.
Thuật toán:
Giả định bản đồ M là mảng 2 chiều được đánh số 0 là ô có thể đi được và -1 là ô không đi được.
Cho queue Q={start}, và danh sách Checked ={}
Lặp:
Nếu Q rỗng thì ngừng => return null
Cho cell = Q.dequeue()
Nếu cell == end thì ngừng => return cell
Kiểm tra 4 ô xung quanh next = {trên, dưới, trái, phải} nếu là ô chưa xét (cell không nằm trong Checked) hoặc ô trống thì:
Đánh dấu next.previous = cell để sau này tra lại đường đi
Đưa vào queue Q.enqueue(next)
Đưa cell vào Checked
Nếu tìm được đường thì dựa vào con trỏ previous để in ra đường đi.
Demo
Ứng dụng 3 - Trò chơi chuyển chỗ
Một nhóm người chơi gồm hai đội A và B, mỗi đội n người ngồi trên một dãy ghế gồm 2n+1 ghế. Các thành viên của đội A ngồi cạnh nhau ở n ghế bên trái và các thành viên của đội B ngồi cạnh nhau ở n ghế bên phải, hai đội cách nhau bởi 1 ghế trống, được thể hiện như sau: AA..A-BB..B với “-“ tượng trưng cho ghế trống và mỗi chữ cái A, hoặc B tượng trưng cho một thành viên của đội tương ứng.
Mục tiêu của bạn là phải tìm cách đổi chỗ sao cho đạt được trạng thái mới là BB..B-AA..A (2 đội đổi vị trí cho nhau) với luật chơi là:
Mỗi lần đổi chỗ chỉ được đổi chỗ một thành viên vào ghế trống
Một người được đổi chỗ ngồi vào ghế trống nếu:
Anh ta ngồi sách cạnh với ghế trống, hoặc
Anh ta cách ghế trống bởi đúng một thành viên của đội kia
Ví dụ:
A-B => -AB => B-A
AA-BB => A-ABB => ABA-B => AB-AB => -BAAB => B-AAB => BA-AB => BABA- => BAB-A => B-BAA => BB-AA
Thuật toán:
Gọi trạng thái ban đầu AA..A-BB..B là initState và trạng thái kết thúc BB..B-AA..A là targetState
Cho queue Q = {initState}, và visited = {}
Lặp:
Gọi trạng thái hiện tại state = Q.dequeue()
Nếu state = targetState => return state
Gọi newStates là tập hợp tất cả các trạng thái có thể sinh ra từ state. Kiểm tra toàn bộ các phần tử của newStates:
Gọi newStates[i] là phần tử thứ i trong tập newStates
newStates[i].previousState = state
Nếu newStates[i] chưa nằm trong tập visited, đưa vào queue: Q.enqueue(newStates[i])
Đưa state vào visited
return null
Bạn có thể tham khảo code mẫu của mình dưới đây:
function solve(initState, targetState){
const queue = [];
const visited = new Set();
queue.push(initState);
visited.add(initState);
while (queue.length > 0){
const state = queue.shift();
if (state.state.join("") == targetState){
return state;
}
const newStates = state.generateNewStates();
for (let i=0; i<newStates.length; i++){
if (!visited.has(newStates[i].state.join(""))){
queue.push(newStates[i]);
}
}
visited.add(state.state.join(""));
}
}
const startState = new State(["A","A","A","A","A","A","_","B","B","B","B","B","B"]);
//const newStates = startState.generateNewStates();
//newStates.forEach(s => console.log(s.state));
let s = solve(startState, "BBBBBB_AAAAAA");
const solution = [];
while (s != null){
solution.push(s.state);
s = s.prev;
}
solution.reverse();
solution.forEach(s => console.log(s.join("")));
và đây là code của class State
class State {
constructor(state, prev = null){
this.state = state;
this.prev = prev;
}
generateNewStates(){
const newStates = [];
for (let i=0; i<this.state.length; i++){
if (this.state[i] == "_"){
if (i == 0) {
const newState = [...this.state];
newState[0] = this.state[1];
newState[1] = "_";
newStates.push(new State(newState, this));
break;
}
else if (i==this.state.length-1){
const newState = [...this.state];
newState[this.state.length-1] = this.state[this.state.length-2];
newState[this.state.length-2] = "_";
newStates.push(new State(newState, this));
break;
} else {
const newState1 = [...this.state];
newState1[i] = this.state[i+1];
newState1[i+1] = "_";
newStates.push(new State(newState1, this));
const newState2 = [...this.state];
newState2[i] = this.state[i-1];
newState2[i-1] = "_";
newStates.push(new State(newState2, this));
if (i-2 >=0 && this.state[i-2] != this.state[i-1]){
const newState3 = [...this.state];
newState3[i] = this.state[i-2];
newState3[i-2] = "_";
newStates.push(new State(newState3, this));
}
if (i+2 < this.state.length && this.state[i+2] != this.state[i+1]){
const newState4 = [...this.state];
newState4[i] = this.state[i+2];
newState4[i+2] = "_";
newStates.push(new State(newState4, this));
}
break;
}
}
}
return newStates;
}
}