書名：《圖說演算法-使用C#》
作者：吳燦銘、胡昭民
所讀版本：博碩文化
數組實作Stack
public class ArrayStack
{
int[] stack;
int top; //頂端索引
public ArrayStack(int size)
{
stack = new int[size];
top = -1; //實例化後默認頂端索引為-1（無元素）
}
public bool Push(int data)
{
if (top >= stack.Length) { return false; } //判斷Stack是否已經滿了
stack[++top] = data;//索引+1，把數據入堆
return true;
}
public bool IsEmpty()
{
return top == -1;
}
public int Pop()
{
if (IsEmpty()) { return -1; } //判斷Stack是否為空
return stack[top--]; //把數據出堆，索引-1
}
}
鏈表實作Stack
public class LinkedListStack
{
public Node front; //指向堆的底端
public Node rear; //指向堆的頂端
public bool IsEmpty()
{
return front == null;
}
public void OutputStack()
{
Node curr = front;
while(curr != null)
{
Console.Write(curr.val + " ");
curr = curr.next;
}
Console.WriteLine();
}
public void Push(int data)
{
Node newNode = new Node(data);
if (IsEmpty())
{
front = newNode;
rear = newNode;
}
else
{
rear.next = newNode;
rear = newNode;
}
}
public void Pop()
{
Node target;
if (IsEmpty()) { return; }
target = front;
if(target == rear) //只有一個元素
{
front = null;
rear = null;
}
else
{
while(target.next != rear)
{
target = target.next;
}
target.next = rear.next;
rear = target;
}
}
}
河內塔算法
假設有A, B, C三個木樁和n個大小不一的套環，由小到大的編號為1~n，編號越大，直徑越大。開始的時候，n個套環套在A木樁上。
直徑較小的套環永遠置於直徑較大的套環上。
套環可任意地由任何一個木樁移到其他的木樁上。
每一次僅能移動一個套環，而且只能從最上面的套環開始移動。
當有n個盤子時，河內塔的移動步驟
將n – 1個盤子從木樁1移動到木樁2
將n個最大盤子，從木樁1移動到木樁3
將n-1 個盤子，從木樁2移動到木樁3
public static void Hanoi(int n, int p1, int p2, int p3)
{
if(n == 1)
{
Console.WriteLine($"Plate Moved From {p1} To {p3}");
}
else
{
Hanoi(n - 1, p1, p3, p2);
Console.WriteLine($"Plate Moved From {p1} To {p3}");
Hanoi(n - 1, p2, p1, p3);
}
}
八皇后算法
在一個8*8棋盤內，置入一個皇后，確保這個位置不會被先前放置的皇后吃掉（直、橫、斜沒有其他皇后），就將這個皇后存入Stack。
當放置新皇后的該行的8個位置都沒有辦法放置新皇后，就從Stack取出上一個皇后的位置，並在那行找一個新的位置放置皇后，然後再將該位置存入Stack中（BackTracking）。
static int solutionCnt = 0;
public static int TotalQueens()
{
int[,] chessBoard = new int[8, 8];
BackTrack(chessBoard, 0);
return solutionCnt;
}
static void BackTrack(int[,] chessBoard, int currRow)
{
//Loop Column of chessBoard
for (int col = 0; col < 8; col++)
{
if (chessBoard[currRow, col] == 0) //Placable
{
chessBoard[currRow, col] = 1; //Place Queen
SetAttackRange(chessBoard, currRow, col, 1); //Set Attack Range
if(currRow + 1 == 8)
{
//Current Combination Confirmed
solutionCnt++;
}
else
{
//Move To Next Row
BackTrack(chessBoard, currRow + 1);
}
//Remove Queen
chessBoard[currRow, col] = 0;
SetAttackRange(chessBoard, currRow, col, -1);
}
}
}
//標記攻撃範圍
static void SetAttackRange(int[,] chessBoard, int row, int col, int change)
{
//縱橫
for (int i = 0; i < 8; i++)
{
if (i != col) { chessBoard[row, i] += change; }
if (i != row) { chessBoard[i, col] += change; }
}
//斜
//Top Left
int y = row - 1;
int x = col - 1;
while (y >= 0 && x >= 0) { chessBoard[y--, x--] += change; }
//Top Right
y = row - 1;
x = col + 1;
while (y >= 0 && x < 8) { chessBoard[y--, x++] += change; }
//Bottom Left
y = row + 1;
x = col - 1;
while(y < 8 && x >= 0) { chessBoard[y++, x--] += change;}
//Bottom Right
y = row + 1;
x = col + 1;
while(y < 8 && x < 8) { chessBoard[y++, x++] += change; }
}
數組實作Queue
public class ArrayQueue
{
int[] queue;
int front;
int rear;
public ArrayQueue(int size)
{
queue = new int[size];
front = -1;
rear = -1;
}
public bool Enqueue(int data)
{
if(rear + 1 == queue.Length) { return false; }
queue[++rear] = data;
return true;
}
public int Dequeue()
{
if(rear > front)
{
front++;
int output = queue[front];
queue[front] = 0;
return output;
}
return -1;
}
}
鏈表實作Queue
public class LinkedListQueue
{
public Node front;
public Node rear;
public LinkedListQueue()
{
front = null;
rear = null;
}
public bool Enqueue(int data)
{
Node newNode = new Node(data);
if(front == null)
{
front = newNode;
}
else
{
rear.next = newNode;
}
rear = newNode;
return true;
}
public int Dequeue()
{
if (front == null) { return -1; }
int value = front.val;
if (front == rear) { rear = null; }
front = front.next;
return value;
}
}
雙向Queue
前後兩端都可以輸入/取出
加入及取出時，指標往Queue的中央移動
public class DoublyLinkedListQueue
{
public Node front;
public Node rear;
public DoublyLinkedListQueue()
{
front = null;
rear = null;
}
//Only Insert Front Head
public bool Enqueue(int data)
{
Node newNode = new Node(data);
if(rear == null)
{
front = newNode;
}
else
{
rear.next = newNode;
}
rear = newNode;
return true;
}
//Dequeue From Both Sides
public int Dequeue(bool isFront)
{
int value;
Node tmp;
Node start;
if(front != null && isFront)
{
value = front.val;
front = front.next;
return value;
}
else if(rear != null && !isFront)
{
start = front; //save ref of front;
value = rear.val;
tmp = front;
//track to the node before rear node
while(front.next != rear && front.next != null)
{
front = front.next;
tmp = front;
}
front = start;
//set new rear
rear = tmp;
//Dequeue Last Node
if(front.next == null || rear.next == null)
{
front = null;
rear = null;
}
return value;
}
else
{
return -1;
}
}
}
優先Queue
HPOF（Highest Priority Out First）rather than FIFO
為每一個元素賦予優先權，加入元素時任意加入，最高優先權者最先輸出