陣列實作佇列
以陣列結構實作佇列的好處是在演算法算很簡單,但跟堆疊不同之處是需要兩種動作:加入與刪除,假設front指向佇列的前端,rear向佇列的尾端,缺點在於無法事先規劃宣告。
先宣告一個有限容量的陣列
1.開始時將front與rear都預設為-1,當front=rear時,則為空佇列。
事件說明 | front | rear | Q(0) | Q(1) | Q(2) | Q(3) |
---|---|---|---|---|---|---|
空佇列Q | -1 | -1 |
2.加入dataA,front=-1,rear=0,每加入一個元素,將rear值加入1:
| 空佇列Q | -1 | -1 | dataA | | | | | —| — | — | — | — | — | — |
3.加入dataB、dataC,front=-1,rear=2:
| 加入dataB、dataC | -1 | 1 | dataA | dataB | dataC | | | —| — | — | — | — | — | — |
4.取出dataA,front=0,rear=2,每取出一個元素,將front值加1:
| 加入dataA | 0 | 2 | | dataB | dataC | | | —| — | — | — | — | — | — |
5.加入dataD,front=0,rear=3,此時當rear=MAXSIZE-1,表示佇列已滿。
| 加入dataD | 0 | 3 | | dataB | dataC | dataD | | —| — | — | — | — | — | — |
6.取出dataB,front=1,rear=3。
| 加入dataB | 1 | 3 | | | dataC | dataD | | —| — | — | — | — | — | — |
鏈結串列實作佇列
佇列能以陣列方式來做以外,也可用鏈結串列來做佇列。在宣告佇列類別中,除了和佇列類別中相關的方法外,還必須指向佇列前端以及尾端的指標front和rear。
這邊用學生姓名及成績的結構來建立佇列串列:
struct Student {
name: String,
score: i32,
}
struct Queue {
front: Option<Box<Student>>,
rear: Option<*mut Student>,
}
在佇列中加入新節點,就是加入串列的尾端,刪除節點就是將串列最前端的節點刪除。
// 將學生加到末端
fn enqueue(&mut self, student: Student) {
let new_node = Box::new(QueueNode {
student,
next: None,
});
let raw_node = Box::into_raw(new_node);
if self.is_empty() {
self.front = Some(unsafe { Box::from_raw(raw_node) });
self.rear = Some(raw_node);
} else {
unsafe {
(*self.rear.unwrap()).next = Some(Box::from_raw(raw_node));
self.rear = Some(raw_node);
}
}
}
// 將前端的刪除
fn dequeue(&mut self) -> Option<Student> {
if self.is_empty() {
None
} else {
let old_front = self.front.take().unwrap();
let student = old_front.student;
self.front = old_front.next;
if self.front.is_none() {
self.rear = None;
}
Some(student)
}
}
當在4X4或者8X8的棋盤就變4皇后或8皇后問題。首先當棋盤中置入一個新皇后,且這個位置不會被先前放置的皇后吃掉,就將這個新皇后的位置存入堆疊。
但是放置新皇后的該行的8個位置(以8皇后為例),都沒有辦法放置新皇后(一放入任何一個位置,就會被先前放置的舊皇后吃掉)。必須由堆疊中取出前一個皇后的位置,並於該行或該列中重新尋找另一個新的位置放置,再將該位置存入堆疊中,這就是回朔演算法的應用。
N皇后的解就是配合堆疊及回朔兩種演算法概念,以逐行或逐列找新皇后位置(如果找不到,則回朔到前一行找尋前一個皇后的另一個位置)的方式,來尋找N皇后問題的其中一組解。
4皇后堆疊內容
4皇后其中一組解
8皇后堆疊內容
8皇后其中一組解
範例:
取8皇后問題解決方法:
總共會有92種不同解,如果合併掉那些旋轉跟對稱可以得到的解的話,那只有12個獨立解。