Bake_WP空間

6-4八皇后演算法

  八皇后問題也是一種常見的堆疊應用實例。在西洋棋中的皇后可以在沒有限定一步走幾格的前提下，對其盤中的其他棋子直吃、橫吃及對角斜吃(左斜吃或右斜吃皆可)，只要後放入的新皇后，再放入前必須考慮所放置直線方向、橫線方向或對角線方向是否已被放置就皇后，否則就會被先放入的舊皇后吃掉。
  利用這個觀念，我們可以將其應用在4*4的棋盤，就稱為4-皇后問題；應用在8*8的棋盤，就稱為8-皇后問題。應用在N*N的棋盤，就稱為N-皇后問題。要解決N-皇后問題(在此我們以8-皇后為例)，首先當於棋盤中置入一新皇后，且這個位置不被先前放置的皇后吃掉，則將此新皇后的位置存入堆疊。
   但若欲放置新皇后的該行(或該列)的8個位置，都沒有辦法放置新皇后(亦即

6-3古老的河內塔演算法

  法國數學家Lucas在1883年介紹了一個十分經典的河內塔Tower of Hanoli智力遊戲，是典型使用遞迴式與堆疊觀念來解決問題的範例，內容是說在古印度神廟，廟中有三根木樁，天神希望和尚們把某些數量大小不同的圓盤，由第一個木樁全部移動到第三個木樁。

  更精確來說，河內塔問題可以這樣形容：假設有A、B、C三個木樁和n個大小均不同的套環Disc，由小到大編號為1,2,3,...n，編號越大直徑越大。開始的時候，n個套環套進A木樁上，現在希望找到將A木樁上的套環藉著B木樁當中間橋樑，全部移到C木樁上最少次數的方法。不過在搬動時還必須遵守下列規則：

1.直徑較小的套環永遠置於直徑較大的套環上。
2.套還可任意弟由一個木樁移到其他的木樁上。
3.每一次僅能移動一個套環，而且只能從最上面的套環開始移動。

  現在我們考慮n=1~3的狀況，以圖示方式為大家示範處理河內塔問題的步驟：

結論：移動了2@2-1=3次，盤子移動的次序為1,2,1(此處為盤子次序)
步驟：1->2，1->3，2->3(此處為木樁次序)

結論：移動了2@3-1=7次，盤子移動的次序為1,2,1,3,1,2,1(盤子次序)。
步驟為1->3，1->2，3->2，1->3，2->1，2->3，1->3(木樁次序)

  當有4個盤子時，我們實際操作後(在此不作圖說明)，盤子移動的次序為121312141214121，而移動木樁的順序為1->2，1->3，2->3，1->2，3->1，3->2，1->2，1->3，2->3，2->1，3->1，2->3，1->2，1->3，2->3，而移動次數為2@4-1=15。
  當n不大時，各位可以逐步用圖示解決，但n的值較大時，那就十分傷腦筋了。事實上，我們可以得到一個結論，例如當有n個盤子時，可將河內塔問題歸納成三個步驟：

1.將n-1個盤子，從木樁移動到木樁2。
2.將第n個最大盤子，從木樁1移動到木樁3。
3.將n-1個盤子，從木樁2移動到木樁3。

由上圖中，應該發現河內塔問題是非常適合以遞迴式與堆疊來解決。因為它滿足了遞迴的兩大特性1.有反覆執行的過程、2.有停止的出口。以下則以遞迴式來表示河內塔遞迴函數的演算法。

var hanoi=(n, p1, p2, p3)=>{
         if (n==1) //遞迴出口
                         process.stdout.write(‘套環從 ‘+p1+ ‘移到 ‘+p3+’\n’);
         else {
                         hanoi(n-1, p1, p3, p2);
                         process.stdout.write(‘套環從 ‘+p1+’ 移到 ‘+p3+’\n’);
                         hanoi(n-1, p2, p1, p3);
             }
}

JS          haoni.js

var hanoi=(n, p1, p2, p3)=> {
	if (n==1) //遞迴出口
		process.stdout.write('套環從'+p1+'移到 '+p3+'\n');
	else {
		hanoi(n-1, p1, p3, p2);
		process.stdout.write('套環從 '+p1+'移到' +p3+'\n');
		hanoi(n-1, p2, p1, p3);
	}
}
const prompt = require('prompt-sync')();
const j= parseInt(prompt('請輸入所移動套環數量：'));
hanoi(j,1,2,3);

PHP          haoni.php

$n=3;
echo "您所輸入的N是{$n}<br>";
haoni($n,1,2,3);

function haoni ($j, $p1, $p2, $p3){

	switch ($j){
		case 1;
		  	echo "套環從{$p1}移到{$p3}<br>";
		    break;
		default:
			haoni($j-1,$p1, $p3, $p2);
		  	echo "套環從{$p1}移到{$p3}<br>";
		  haoni($j-1,$p2, $p1, $p3);
	}

}

        堆疊結構在電腦中的應用相當廣泛，時常被用來解決電腦的問題，例如前面所談到的遞迴呼叫、副程式的呼叫，至於在日常生活中的應用也隨處可以看到，例如大樓電梯、貨架上的貨品等等，都是類似堆疊的資料結構原理。
        佇列在電腦領域的應用也相當廣泛，例如計算機的模擬simulation、CPU的工作排程Job Scheduling、線上同時周邊作業系統的應用與圖形走訪得先廣後深搜尋法BFS。由於堆疊與佇列都是抽象資料型態Abstract Data Type,ADT，本章終將為各位介紹相關演算法。
         堆疊在程式設計領域中，包含以下兩種設計方式，分別為陣列結構與鏈結串列結構。

6-1陣列實作堆疊輕鬆學

         以陣列結構來製作堆疊的好處是製作與設計的演算法都相當簡單，但因為如果堆疊本身是變動的話，大小並無法事先規劃宣告，太大時浪費空間，太小則不夠使用。

相關演算法如下

//判斷是否空堆疊
var isEmpy=()=>{
  if (top==-1)
    return true;
  else
    return false;
}
//將指定的資料存入堆疊
var push=(data)=>{
  if (top>=MAXSTACK-1)
    process.stdout.write('堆疊已滿，無法再加入');
  else {
    top +=1;
    stack[top]=data; //將資料存入堆疊
  }
}
//從堆疊取出資料
var pop=()=>{
  if (isEmpty())
    process.stdout.write('堆疊是空');
  else {
    process.stdout.write('彈出的元素為： '+stack[top]+'\n');
    top=top-1;
  }
}

JS            array_stack.js

const MAXSTACK=100; //定義最大堆疊容量
stack=[]; //堆疊的陣列宣告
top=-1; //堆疊的頂端

//判斷是是否為空堆疊
var isEmpty=()=>{
	if(top==-1)
		return true;
	else
		return false;
}

//將指定的資料存入堆疊
var push=(data)=> {
	if (top>=MAXSTACK-1)
		process.stdout.write('堆疊已滿，無法再加入');
	else {
		top +=1;
		stack[top]=data;//將資料存入堆疊
	}
}

//從堆疊取出資料
var pop=()=> {
	if (isEmpty())
		process.stdout.write('堆疊是空');
	else {
		process.stdout.write('彈出的元素為：'+stack[top]+'\n');
		top=top-1;
	}
}

//主程式
i=2;
count=0;
const prompt = require('prompt-sync')();
while(true) {
	const i = parseInt(prompt('要推入堆疊，請輸入1，彈出則輸入0，停止操作則輸入-1：'));
	if (i==-1)
		break;
	else if (i==1) {
		const value = parseInt(prompt('請輸入元素值：'));
		push(value);
	}
	else if (i==0)
		pop();
}

process.stdout.write('========================\n');

if (top<0)
	process.stdout.write('\n 堆疊是空的\n');
else {
	i=top;
	while (i>=0) {
		process.stdout.write('堆疊彈出的順序為：'+stack[i]+'\n');
		count +=1;
		i =i-1;
	}
}
process.stdout.write('=====================================\n');

PHP          array_stack.php

6-2鏈結串列實作堆疊

        使用鏈結串列來製作堆疊的優點是隨時可以動態改變串列長度，能有效利用記憶體資源，不過缺點是設計時，演算法較為複雜。

相關演算法如下：

class Node {    //堆疊鏈結點的宣告
    constructor() {
        this.data=0;  //堆疊資料的宣告
        this.next=null;  //堆疊中用來指向下一個節點
     }
}
top=null;
var isEmpty=()=> {
    if(top===null)
       return true;
    else
       return false;
}
//將指定的資料存入堆疊
var push=(data)=> {
    new_add_node=new Node();
    new_add_node.data=data; //將傳入的值指定為節點的內容
    new_add_node.next=top; //將新節點指向堆疊的頂端
    top=new_add_node;  //新節點成為堆疊的頂端
}
//從堆疊取出資料
var pop=()=> {
    if (isEmpty()) {
        process.studout.write('===目前為空堆疊====\n');
        return -1;
    }
    else {
        ptr=top;  //指向堆疊的頂端
        top=top.next;  //將堆疊頂端的指標指向下一個節點
        temp=ptr.data;  //取出堆疊的資料
        return temp;  //將從堆疊取出的資料回傳給主程式
     }
}

class Node {    //堆疊鏈結節點的宣告
    constructor() {
        this.data=0;    //堆疊資料的宣告
        this.next=null; //堆疊中用來指向下一個節點
    }
}
top=null;
var isEmpty=()=> {
    if(top==null)
        return true;
    else
        return false;
}
//將指定的資料存入堆疊
var push=(data)=> {    
    new_add_node=new Node();
    new_add_node.data=data; //將傳入的值指定為節點的內容
    new_add_node.next=top;  //將新節點指向性堆疊的頂端
    top=new_add_node;       //新節點成為堆疊的頂端
}
//從堆疊取出資料
var pop=()=> {
    if (isEmpty()) {
        process.stdout.write('===目前為空堆疊===\n');
        return -1;
    }
    else {
        ptr=top;        //指向堆疊的頂端
        top=top.next;   //將堆疊頂端的指標指向下一個節點
        temp=ptr.data;  //取出堆疊資料
        return temp;    //將從堆疊取出的資料回傳給主程式
    }
}
// 主程式
const prompt = require('prompt-sync') ();
while (true) {
    const i = parseInt(prompt('要推入堆疊，請輸入1，彈出則輸入0，停止操作則輸入-1： '));
    if (i==-1)
        break;
    else if (i==1) {
        const value = parseInt(prompt('請輸入元素值：'));
        push(value);
    }   
    else if (i==0)
        process.stdout.write('彈出的元素為'+pop()+'\n');
}
process.stdout.write('===========================\n');
while (!isEmpty())    //將資料陸續從頂端彈出
    process.stdout.write('堆疊彈出的順序為：'+pop()+'\n');
process.stdout.write('===========================\n');

 JS           list_strack.js

5-3-3單向鏈結串列刪除節點

在單向鏈結型態的資料結構中，如果要在串列中刪除一個節點，如同一列火車拿掉原有的車廂，依據所刪除節點的位置有三種不同的情形：

演算法如下：

top=head;
head=head.next;

演算法如下：

ptr.next=tail;
ptr.next=null;

演算法如下：

Y=ptr.next;
ptr.next=Y.next;

class employee{
        constructor() {
               this.num=0;
               this.salary=0;
               this.name=”;
               this.next=null;
        }
}

JS          del_node.js

class employee{
	constructor(){
		this.num=0;
		this.salary=0;
		this.name='';
		this.next=null;
	}
}

var del_ptr=(head,ptr)=>{   //刪除節點副程式
	top=head;
	if (ptr.num==head.num) {  //[情形1]：刪除點在串列首
		head=head.next;
		process.stdout.write('已刪除第' +ptr.num+' 號員工 姓名：'+ptr.
			name+' 薪資：'+ptr.salary);
	}
	else {
		while (top.next!=ptr)  //找到刪除點的前一個位置
			top=top.next;
		if(ptr.next==null) {   //刪除在串列尾的節點
			top.next=null;
			process.stdout.write('已刪除第'+ptr.num+' 號員工 姓名：'+ptr.
				name+' 薪資：'+ptr.salary+'\n');
		}
		else{
			top.next=ptr.next;
			process.stdout.write('已刪除第 '+ptr.num+' 號員工 姓名：'+ptr.
				name+' 薪資：' +ptr.salary+'\n');
		}		
	}
	return head;
}

findword=0;
namedata=['Allen','Scott','Mary','John','Mark','Ricky',
		  'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
		[1012,42660],[1014,25676],[1018,44145],[1043,52182],
		[1031,32769],[1037,21100],[1041,32196],[1046,25776]];
process.stdout.write('員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n');
process.stdout.write('--------------------------------------------------\n');

for(i=0; i<3; i++) {
	for (j=0; j<4; j++)
		process.stdout.write(data[j*3+i][0]+ '\t'+data[j*3+i][1]+'\t');
	console.log();
}

head=new employee(); //建立串列首
if(!head) {
	console.log('Error!! 記憶體配置失敗！！');
	return;
}
head.num=data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;

ptr=head;
for (i=1; i<12; i++) { //建立串列
	newnode=new employee();
	newnode.next=null;
	newnode.num=data[i][0];
	newnode.name=namedata[i];
	newnode.salary=data[i][1];
	newnode.next=null;
	ptr.next=newnode;
	ptr=ptr.next;
}
const prompt = require('prompt-sync')();
while(true)  {
	const findword = parseInt(prompt('請輸入要刪除的員工編號，要結束刪除過程，請輸入-1：'));
	if (findword==-1)  //迴圈中斷條件
		break;
	else {
		ptr=head;
		find=0;
		while (ptr!=null) {
			if (ptr.num==findword){
				ptr=del_ptr(head,ptr);
				find=find+1;
				head=ptr;
			}
			ptr=ptr.next;
		}
		if (find==0)
			process.stdout.write('//////////沒有找到///////////\n');
	}
}
ptr=head;
process.stdout.write('\t座號\t  姓名\t成績\n');  //列印剩餘串列資料
process.stdout.write('\t======================\n');  
while (ptr!=null)  {
	process.stdout.write('\t['+ptr.num+' ]\t[ '+ptr.name+' ]\t[ '
		+ptr.salary+']\n');
	ptr=ptr.next;
}

5-3-4單向鏈結串列的反轉

看完了節點的刪除及插入後，各位可以發現在這種具有方向性的鏈結串列結構中增刪節點是相當容易的一件事。而要從頭到尾印整個串列似乎也不難，不過如果要反轉過來列印就真的需要某些技巧了。我們知道在鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。請看下圖說明：

演算法如下：

class employee{
    constructor() {
     this.num=0;
     this.salary=0;
     this.name='';
     this.next=null;
    }
}
var invert=(x)=> { //x為串列的開始指標
     p=x;    //將p指向串列的開頭
     q=null; //q是p的前一個節點
     while (p!=null) {
        r=q;       //將r接到q之後
        q=p;       //將q接到p之後
        p=p.next   //p移到下一個節點
        q.next=r;  //q連結到之前的節點
     }
     return q;
}

JS          rev_node.js

class employee {
	constructor() {
		this.num=0;
		this.salary=0;
		this.name='';
		this.next=null;
	}
}

findword=0;
namedata=['Allen','Scott','Marry','John','Mark','Ricky',
			'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
		[1012,42660],[1014,25676],[1018,44145],[1043,52182],
		[1031,32769],[1037,21100],[1041,32196],[1046,25776]];

head = new employee();//建立串列首
if(!head) {
	console.log('Error!! 記憶體配置失敗！！');
	return;
}
head.num =data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;

ptr=head;

for(i=1; i<12; i++){  //建立串列
	newnode=new employee();
	newnode.next=null;
	newnode.num=data[i][0];
	newnode.name=namedata[i];
	newnode.salary=data[i][1];
	newnode.next=null;
	ptr.next=newnode;
	ptr=ptr.next;
}

ptr=head;
i=0;
process.stdout.write('原始員工串列節點資料：\n');
while (ptr !=null) { //列印串列資料
	process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
							+ptr.salary+'] -> ');
	i=i+1;
	if (i>=3) { //三個元素為一列
		console.log();
		i=0;
	}
	ptr=ptr.next;
}

ptr=head;
before=null;
process.stdout.write('\n反轉後串列節點資料：\n');
while (ptr!=null) { //串列反轉，利用三指標
	last=before;
	before=ptr;
	ptr=ptr.next;
	before.next=last;
}
ptr=before;
while (ptr!=null) {
	process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
							+ptr.salary+'] ->');
	i=i+1;
	if (i>=3) { //三個元素為一列
		console.log();
		i=0;
	}
	ptr=ptr.next;
}

PHP  陣列 函數

array_pop() 刪除陣列最後一個元素。
array_push() 將一個或多個元素加入末端。
array_reverse() 以相反的順序返回陣列。
array_shift() 刪除首個元素。
array_slice() 刪除指定位置的元素，返回陣列。